Wie wird der Wert zurückgegeben? - Rekursiver Algorithmus

Question

Mein Verstand ist nicht in der Lage zu verstehen, wie der Wert von diesem einfachen rekursiven Algorithmus zurückgegeben wird. Der Algorithmus ist wie folgt:

int fib(int n) 
{ 
    if (n <= 1) 
     return n; 

    return fib(n-1) + fib(n-2); 

} 

Ich frage mich, wie die Eingabe 5 dieser Funktion 5 zurückkehrt? Ich weiß, dass die fünfte Fibonacci-Zahl 5 ist, also ist dies die richtige Antwort, aber ich bin nicht sicher, wie diese Antwort aus dem obigen Code abgeleitet ist. Die ersten fünf Fibonacci-Zahlen: 1 1 2 3 5.

Von meinem begrenzten Verständnis denke ich, dass die Übergabe von 5 an diese Funktion 7 zurückgeben würde. Dies liegt daran, 5-1 = 4 und 5-2 = 3. Dann addieren Sie diese beiden Zahlen zusammen erhalte ich die einfache ganze Zahl 7. Hat das Sinn ergeben? Ich bin sicher, dass ich bereits jemanden verloren habe, der das liest, obwohl das sehr einfach ist. Wenn ich das lesen würde, wäre ich verloren.

Wenn ich einen Rekursionsbaum mache und die rekursiven Aufrufe von fib ab 5 zeige, sehe ich nicht, wie dies schließlich 5 zurückgibt, aber ich sehe alle Aufrufe der Funktion fib() bis schließlich 1 zurückgegeben wird Argument zu fib() ist 0 oder 1. Der Rekursionsbaum, den ich zeichnete, ist nur eine Kopie von der, die an diesem page gezeigt wird.

Kann mir dieser rekursive Algorithmus helfen?

Answer 1

Ok, lassen Sie uns die Rekursion eröffnen für fib(5)

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

fib(1) + fib(0) = 1 + 0 = 1 so fib(2) = 1 
fib(2) + fib(1) = 1 + 1 = 2 so fib(3) = 2 
fib(3) + fib(2) = 2 + 1 = 3 so fib(4) = 3 
fib(4) + fib(3) = 3 + 2 = 5 so fib(5) = 5 

Sie sind das richtig 5-1 = 4 und 5-2 = 3, aber das nur bedeutet, dass Sie fordern fib(4) + fib(3) = 5, die von 4 + 3 = 7 sehr unterschiedlich

Answer 2

Denken Sie an die Rückkehr als Rückgabe einer Zahl, und um diese Zahl zu bekommen, muss sie eine Funktion aufrufen und diese Funktion ausführen. Und es tut dies, bis es einen Grundfall erreicht, n = 0 oder 1, dann ruft es eine andere Funktion nicht auf, um eine Zahl zurückzugeben.

Answer 3

Hier ist meine Version des rekursiven Aufrufbaum:

fib(5) = fib(4)          + fib(3) 

     |           | 
     +--------------------------\     +-----------------\ 
     |       |     |     | 

     = fib(3)     + fib(2)   + fib(2)   + fib(1) 

     |       |     |     | 
     +-----------------\  +--------\  +--------\  | 
     |     |  |  |  |  |  | 

     = fib(2)   + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1 

     |     |  |  |  |  |  | 
     +--------\  |  |  |  |  |  | 
     |  |  |  |  |  |  |  | 

     = fib(1) + fib(0) + 1  + 1  + 0  + 1  + 0  + 1 

     |  |  |  |  |  |  |  | 
     |  |  |  |  |  |  |  | 
     |  |  |  |  |  |  |  | 

     = 1  + 0  + 1  + 1  + 0  + 1  + 0  + 1 

     = 5 

Answer 4

Wenn eine rekursive Funktion ein implizites s verwendet wird tack wird beibehalten, der die von jedem rekursiven Aufruf zurückgegebenen Werte verfolgt.

Lassen Sie uns jetzt Ihr Beispiel für gegebenen Wert von n betrachten = 5

>Processing fib(5)... Call fib(3) and fib(4). 
>Processing fib(3)... Call fib(1) and fib(2). 
>Processing fib(1)... Return 1! 
>Processing fib(2)... Return 1! 
>Processing fib(4)... Call fib(2) and fib(3). 
>Processing fib(2)... Return 1! 
>Processing fib(3)... Call fib(1) and fib(2). 
>Processing fib(1)... Return 1! 
>Processing fib(2)... Return 1! 
>5 is the 5th Fibonacci number 

Analyse: Das Programm fragt nach einer Zahl in Zeile 15 zu finden und ordnet diese Zahl zu zielen. Dann ruft er fib() mit dem Ziel auf. Die Ausführung verzweigt zur Funktion fib(), wo sie in Zeile 28 ihr Argument ausgibt.

Das Argument n wird getestet, um zu sehen, ob es in Zeile 30 gleich 1 oder 2 ist; Wenn ja, kehrt fib() zurück. Andernfalls gibt es die Summe der Werte zurück, die durch Aufrufen von fib() auf n-2 und n-1 zurückgegeben werden.

In dem Beispiel ist n 5, also wird fib (5) von main() aufgerufen. Die Ausführung springt zur Funktion fib(), und n wird in Zeile 30 auf einen Wert unter 3 getestet. Der Test schlägt fehl, so dass fib (5) die Summe der von fib (3) und fib (4) zurückgegebenen Werte zurückgibt. Das heißt, fib() wird auf n-2 (5 - 2 = 3) und n-1 (5 - 1 = 4) aufgerufen. fib (4) gibt 3 zurück und fib (3) gibt 2 zurück, sodass die endgültige Antwort 5 ist.

Da fib (4) in einem Argument übergeben wird, das nicht weniger als 3 ist, wird fib() erneut aufgerufen, diesmal mit 3 und 2. fib (3) ruft wiederum fib (2) und fib (1). Schließlich geben die Aufrufe von fib (2) und fib (1) beide 1 zurück, weil dies die Stoppbedingungen sind.