# Fibonacci endrekursiv darstellen



## peterini (13. Nov 2011)

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 (13. Nov 2011)

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


----------



## peterini (13. Nov 2011)

hat sich erledigt  ich habs hinbekommen


----------



## Marcinek (13. Nov 2011)

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 (14. Nov 2011)

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 (14. Nov 2011)

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);
    }
```


----------

