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

 

[Olivius]

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

Da die erste Fibonaccizahl (n = 0) 0 ist, müsste der Code eher so lauten:

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) {
    if(n == 0) return 0;
    return fib0(1, 1, 2, n - 1);
}

 

[Olivius]

Hoffe das hat geholfen

 

[Marinek]

Denke nach 14 Jahren wirst du hier keine Antwort des to bekommen

 

[KonradN]

Hoffe das hat geholfen

Da der Thread fast 14 Jahre alt ist, bezweifle ich, dass da noch wirkliches Interesse besteht ...

Da die erste Fibonaccizahl (n = 0) 0 ist,

Das sehe ich nicht so, Das wird zwar teilweise so gesehen, aber die original Definition ist nur für n > 0 definiert und n = 0 ist einfach nicht definiert. (Sprich: n ist eine Element aus den Natürlichen Zahlen, also N und nicht N0). Die typische Definition ist halt einfach:
f(n) = f(n-1) + f(n-2) | n > 2
f(1) = f(2) = 1

Man kann das umstellen um dann auch 0 und negative Zahlen (Also n ein Element der Ganzen Zahlen, Z) ermöglichen zu können, wie es https://de.wikipedia.org/wiki/Fibonacci-Folge zeigt. Das wird aber natürlich von Deinem Code nicht abgebildet.

Das ist zumindest mein Verständnis der Fibonacci Zahlen.

Edit: Wie immer zählt aber natürlich die Aufgabenstellung selbst. Je nach konkreter Aufgabenstellung ist dann klar geregelt, was zu implementieren ist.

 

[Olivius]

Hab hier auch ne Variante mit nur drei Parametern, wenn ihr der Meinung seid, dass Fibonacci erst bei 1 beginnt, dann tauscht die 0 beim fib0-Call durch eine 1 aus

    private static int fib0(int x, int y, int n) {
        if (n < 2) return y;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        if(n == 0) return 0;
        return fib0(0, 1,n);
    }

 

[Olivius]

Hab hier auch ne Variante mit nur drei Parametern, wenn ihr der Meinung seid, dass Fibonacci erst bei 1 beginnt, dann tauscht die 0 beim fib0-Call durch eine 1 aus

    private static int fib0(int x, int y, int n) {
        if (n < 2) return y;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        if(n == 0) return 0;
        return fib0(0, 1,n);
    }

Geht auch noch kürzer:

    private static int fib0(int x, int y, int n) {
        if (n < 1) return x;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        return fib0(0, 1, n);
    }

 

[Olivius]

Da der Thread fast 14 Jahre alt ist, bezweifle ich, dass da noch wirkliches Interesse besteht ...


Das sehe ich nicht so, Das wird zwar teilweise so gesehen, aber die original Definition ist nur für n > 0 definiert und n = 0 ist einfach nicht definiert. (Sprich: n ist eine Element aus den Natürlichen Zahlen, also N und nicht N0). Die typische Definition ist halt einfach:
f(n) = f(n-1) + f(n-2) | n > 2
f(1) = f(2) = 1

Man kann das umstellen um dann auch 0 und negative Zahlen (Also n ein Element der Ganzen Zahlen, Z) ermöglichen zu können, wie es https://de.wikipedia.org/wiki/Fibonacci-Folge zeigt. Das wird aber natürlich von Deinem Code nicht abgebildet.

Das ist zumindest mein Verständnis der Fibonacci Zahlen.

Edit: Wie immer zählt aber natürlich die Aufgabenstellung selbst. Je nach konkreter Aufgabenstellung ist dann klar geregelt, was zu implementieren ist.

Die Fibonaccifolge ist in der On-line encyclopedia of integer sequences mit der 0 gelistet (A000045)
Dies hat auch in der Verwendung der Folge mehrere Vorteile, die dort nachzulesen sind