Wie funktioniert diese Rekursion? Können Sie erklären, wie sie die Ausgabe erhalten haben?

Question

function fnum = fib(n) 
if (n == 1) || (n == 2) 
    fnum = 1; 
else 
    fnum = fib(n-1) + fib(n-2); 
end 

Können Sie erklären, wie jeder Schritt für den gegebenen Eingang ausgibt. Zum Beispiel gibt mir die Eingabe von 7, 13, 5 gibt mir 5, aber ich kann das nicht nachvollziehen. Ich würde Ihre Antwort sehr schätzen.

Answer 1

Wissen Sie, wie Fibonacci-Serie definiert ist? Diese Funktion implementiert das rekursiv.

längere Antwort

Fibonacci-Reihe ist definiert als

n(1) = 1 
n(2) = 1 
n(k+1) = n(k) + n(k-1) 

Also, wenn Sie 5 als Argument setzen, wird die Expansion

n(4+1) = n(4)+n(3) 
     = n(3)+n(2)+n(2)+n(1) 
     = n(2)+n(1)+1+1+1 
     = 1+1+1+1+1 
     = 5 

Ein viel einfacher Hinter umhüllen Methode ist Beginnen Sie mit dem ersten Index und fügen Sie die letzten beiden Begriffe hinzu, um zum nächsten zu gelangen.

1, 1, 2 < - (1 + 1), 3 < - (2 + 1), 5 < - (3 + 2), ...

Answer 2

Die Fibonnacci Serie als f(1) = 1, f(2) = 1 and for all n > 2, f(n) = f(n-1) + f(n-2) definiert ist

So, wenn Sie fib(1) aufrufen, gibt 1 das gleiche für fib(2) zurück. Aber wenn Sie fib(3) anrufen, gibt es fib(3-1) + fib(3-2) zurück, das fib(2) + fib(1) = 2 ist. Und dann, wenn Sie fib(4) aufrufen, gibt es fib(3) + fib(2) = (fib(2) + fib(1)) + fib(1) = 3 zurück. Und rekursiv ist die fibonnaci-Serie gleich 1, 1, 3, 5, 8, 13, 21, ...

Für den Code, wenn n ist anders als 1 oder 2, rufen Sie die Funktion fib rekursiv. Und wenn es gleich 1 oder 2 ist, wird 1 zurückgegeben.

Answer 3

Rekursion bedeutet im Grunde, dass die Funktion sich selbst aufruft.

Wenn wir Ihre Funktion für fib(3) folgen, werden Sie sehen, dass das, was es tut, aufrufen. Die Werte von diesen sind definiert und sind 1, so dass es 2 zurückgibt.

Wenn Sie es mit fib(4) aufrufen, wird es gehen und fib(3)+fib(2) berechnen. Sie wissen bereits, was fib(3) tut (siehe vorherigen Absatz), und wir haben bereits erwähnt, dass fib(2)1 zurückgibt.

Wenn Sie es mit fib(5) aufrufen, wird es gehen und fib(4)+fib(3) berechnen. Siehe vorherigen Absatz.

Dies ist eine sehr nützliche Art der Programmierung, da es eine sehr einfache Funktion ist, etwas zu berechnen, das wohl komplizierter ist. Das Wichtigste ist, dass Sie sicherstellen, dass jede rekursive Funktion starke Abbruchkriterien hat, sonst kann es für immer gehen!