Fibonacci endrekursiv darstellen

[peterini]

Hallo,
ich soll für meinen Informatik Leistungskurs aufm gymi die Fibonacci Funktion in endrekursiver art und weise darstellen. Ich steh total auf dem schlauch irgendwie. Auf die normale rekursionsfunktion von fibonacci komme ich recht simpel, aber auf die endrekursive funktion will ich einfach nicht kommen. könnt ihr mir bitte weiterhelfen?
danke im vorraus

 

[njans]

Wie sieht denn die nicht-Endrekursive Variante bei dir aus?

 

[peterini]

hat sich erledigt ich habs hinbekommen

 

[Marcinek]

Wie hast du es hinbekommen? - Geht das überhaupt?

Die nicht endrekursive ist klar

fib ( int x )
if (x < 2)
  return 1;
else return fib (x -1) + fib (x-2)

Der letzte Schritt wird nicht mehr durch die rekursion berechnet.

 

[musiKk]

Durch CPS sollte sich jeder rekursive Algorithmus in eine endrekursive Form umwandeln lassen.

Nebenbei: Kudos an die Schule. Bei uns war der Informatikkurs "etwas" simpler.

 

[fastjack]

vielleicht so:

    private static int fib0(int x, int y, int i, int n) {
        if (i > n)
            return y;
        else
            return fib0(y, x + y, i + 1, n);
    }
    public static int fib(int n) {
        return fib0(1, 1, 2, n);
    }