Fibonacci-Funktion Frage

Question

ich die Fibonacci-Folge zu berechnen und über diesen Code gestolpert, die ich viel gesehen:

int Fibonacci (int x) 
{ 
    if (x<=1) { 
     return 1; 
    } 
    return Fibonacci (x-1)+Fibonacci (x-2); 
} 

Was ich nicht verstehe ist, wie es funktioniert, vor allem die Rückkehr Teil am Ende : Ruft es die Fibonacci-Funktion erneut auf? Könnte mir jemand diese Funktion durchgehen?

Answer 1

Ja, die Funktion ruft sich selbst auf. Beispiel:

Fibonacci(4) 
= Fibonacci(3) + Fibonacci(2) 
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0)) 
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1) 
= ((1 + 1) + 1) + 2 
= (2 + 1) + 2 
= 3 + 2 
= 5 

Beachten Sie, dass die Fibonacci-Funktion hier 9 Mal aufgerufen wird. Im Allgemeinen hat die naive rekursive Fibonacci-Funktion exponential running time, was normalerweise eine schlechte Sache ist.

Answer 2

Dies ist ein klassisches Beispiel für eine recursive function, eine Funktion, die sich selbst aufruft.

Wenn Sie es sorgfältig zu lesen, werden Sie sehen, dass es selbst nennen, oder, recurse, immer und immer wieder, bis es den so genannten Basisfall erreicht, wenn x <= 1, an den es beginnt Punkt um "zurück zu verfolgen" und die berechneten Werte zusammenzufassen.

Der folgende Code druckt deutlich die Spur des Algorithmus aus:

public class Test { 

    static String indent = ""; 

    public static int fibonacci(int x) { 

     indent += " "; 
     System.out.println(indent + "invoked with " + x); 

     if (x <= 1) { 

      System.out.println(indent + "x = " + x + ", base case reached."); 
      indent = indent.substring(4); 

      return 1; 
     } 

     System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2)); 
     int retVal = fibonacci(x-1) + fibonacci(x-2); 
     System.out.println(indent + "returning " + retVal); 
     indent = indent.substring(4); 
     return retVal; 

    } 


    public static void main(String... args) { 
     System.out.println("Fibonacci of 3: " + fibonacci(3)); 
    } 
} 

Der Ausgang ist die folgende:

invoked with 3 
Recursing on 2 and 1 
    invoked with 2 
    Recursing on 1 and 0 
     invoked with 1 
     x = 1, base case reached. 
     invoked with 0 
     x = 0, base case reached. 
    returning 2 
    invoked with 1 
    x = 1, base case reached. 
returning 3 

Fibonacci of 3: 3 

Ein Baum Darstellung der Spur würde in etwa so aussehen

       fib 4 
       fib 3    +   fib 2 
    fib 2  + fib 1    fib 1 + fib 0 
fib 1 + fib 0   1     1  1 
    1  1 

Die wichtigen Teile, über die beim Schreiben rekursiver Funktionen nachgedacht wird, sind:

1. Achten Sie auf den Basisfall

Was passiert wäre, wenn wir if (x<=1) return 1; im Beispiel oben vergessen hatte?

2. Stellen Sie sicher, dass die rekursive Aufrufe irgendwie in Richtung der Basisfall verringern

Was passiert, wenn wir den Algorithmus aus Versehen fibonacci(x)+fibonacci(x-1);

Answer 3

Das ist eine klassische Funktion Rekursion zurück geändert passiert wäre. http://en.wikipedia.org/wiki/Recursive_function sollte Sie beginnen. Im Wesentlichen, wenn x kleiner als oder gleich 1 ist, gibt es 1 zurück. Andernfalls verringert es sich, wenn x bei jedem Schritt Fibonacci ausführt.

Answer 4

Ja, die Fibonacci-Funktion wird erneut aufgerufen, dies wird Rekursion genannt.

Genau wie Sie eine andere Funktion aufrufen können, können Sie die gleiche Funktion erneut aufrufen. Da der Funktionskontext gestapelt ist, können Sie die gleiche Funktion aufrufen, ohne die aktuell ausgeführte Funktion zu stören.

Beachten Sie, dass Rekursion schwierig ist, da Sie die gleiche Funktion möglicherweise wieder unendlich aufrufen und den Aufrufstapel füllen. Dieser Fehler wird "Stack Overflow" genannt (hier ist es!)

Answer 5

In C und die meisten anderen Sprachen, ist eine Funktion selbst erlaubt wie jede andere Funktion nur zu rufen. Dies wird Rekursion genannt.

Wenn es seltsam aussieht, weil es aus der Schleife anders ist, dass Sie schreiben würde, du hast Recht. Dies ist keine sehr gute Anwendung der Rekursion, da das Finden der n Fibonacci-Nummer doppelt so lange dauert wie das Auffinden der n -1th, was zu einer exponentiellen Laufzeit in n führt.

Iterieren über die Fibonacci-Sequenz, erinnert sich die vorherige Fibonacci-Nummer vor dem Weitergehen zum nächsten verbessert die Laufzeit zu linear in n, wie es sein sollte.

Rekursion selbst ist nicht so schlimm. Tatsächlich habe ich die Schleife gerade beschrieben (und jede Schleife) kann als eine rekursive Funktion implementiert werden:

int Fibonacci (int x, int a = 1, int p = 0) { 
    if (x == 0) return a; 
    return Fibonacci(x-1, a+p, a); 
} // recursive, but with ideal computational properties 

Answer 6

return Fibonacci (x-1) + Fibonacci (x-2);

Das ist furchtbar ineffizient. Ich schlage die folgende lineare Alternative vor:

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c) 
{ 
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c); 
} 

unsigned fibonacci(unsigned n) 
{ 
    return (n < 2) ? n : fibonacci(n, 0, 1, 1); 
} 

Die Fibonacci-Sequenz kann in funktionellen Sprachen kürzer ausgedrückt werden.

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci) 

> take 12 fibonacci 
[0,1,1,2,3,5,8,13,21,34,55,89] 

Answer 7

Da Ihre Frage C++ markiert ist, ich fühle mich gezwungen, darauf hinzuweisen, dass diese Funktion auch zur Compile-Zeit als Vorlage erreicht werden kann, sollten Sie ein Compiler-Variable haben, es zu benutzen mit.

template<int N> struct Fibonacci { 
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value; 
}; 
template<> struct Fibonacci<1> { 
    const static int value = 1; 
} 
template<> struct Fibonacci<0> { 
    const static int value = 1; 
} 

Schon eine Weile, seit ich solche geschrieben habe, so könnte es ein wenig raus sein, aber das sollte es sein.

Answer 8

Oder wenn Sie möchten mehr schnell, aber diese mehr Speicherplatz nutzen zu können.

int *fib,n; 
void fibonaci(int n) //find firs n number fibonaci 
{ 
fib= new int[n+1]; 
fib[1] = fib[2] = 1; 
for(int i = 3;i<=n-2;i++) 
    fib[i] = fib[i-1] + fib[i-2]; 
} 

und für n = 10 für exemple haben Sie: fib [1] FIB [2] FIB [3] FIB [4] FIB [5] fib [6] fib [7] fib [8 ] fib [9] fib [10] 1 1 2 3 5 8 13 21 34 55``