Optimieren der rekursiven Funktion der Fibonacci-Sequenz durch Erstellen eines Wrappers

Question

Es gibt ein Problem mit der rekursiven Definition der Fibonacci-Sequenz, wenn es um Effizienz geht. Es ist wie folgt definiert:

private fib(int n) { 
    if(n < 2) return n; 
    else return fib(n - 1) + fib(n-2); 
} 

Angenommen, wir rufen fib (5). Dies macht 1 Anruf zu fib (4), zwei Anrufe zu fib (3), drei Anrufe zu fib (2), fünf Anrufe zu fib (1) und drei Anrufe zu fib (0).

In seinem Buch

Programmierung Abstraktionen in Java von Eric Robert

Robert erwähnt, dass wir diese Effizienz Problem durch die Realisierung lösen können, dass die Fibonacci-Sequenz ist nur ein Spezialfall des additiveSequence(int n, int t0, int t1) Verfahrens . Grundsätzlich ist die Fibonacci-Sequenz nur eine additive Sequenz, die streng mit 0 und 1 beginnt. Es gibt eine unendliche Anzahl von Sequenzen, die mit der von Fibonacci ausgedrückten Rekursionsbeziehung übereinstimmen.

Der Autor löst die Effizienz Problem wie folgt:

private int fib(int n) { 
    return additiveSequence(n, 0, 1); 
} 

Also meine Fragen ist, durch die fib-Sequenz macht ein Wrapper für die allgemeinere additiveSequence Methode werden wir wirklich die Effizienz zu verbessern? Wäre nicht die Implementierung von additiveSequence genau dasselbe "Problem" in Bezug auf die Effizienz, die fib hatte, da es der gleichen genauen Wiederholungsbeziehung folgt?

Answer 1

Hier ist eine beispielhafte Implementierung eines Berechnungs additive Sequenz, wobei T _i = t _i-1 + t _i-2:

int additiveSequence(int n, int t0, int t1) { 
    if(n==0) return t0; 
    if(n==1) return t1; 
    return additiveSequence(n-1, t1, t0+t1); 
} 

Diese Methode liefert die n-ten Wert in der Serie. Arbeite durch einige Beispiele und du solltest dich davon überzeugen können, dass jedes t _i nur einmal berechnet wird. Vergleichen Sie das mit Ihrer naiv implementierten fib-Methode und Sie können sehen, warum dieser Ansatz viel schneller ist.

Die Fibonacci-Reihe ist diese Art der additiven Sequenz, mit den Startbedingungen t = 0 und t = 1. Es gibt nichts besonders Besonderes, außer der Tatsache, dass der offensichtliche Weg, es zu codieren ist eine arme. Der Autor geht davon aus, dass die Implementierung einen großen Unterschied in der Verarbeitungszeit macht. Es scheint jedoch nicht klar erklärt zu werden.