Ich gehe durch ein Programmierbuch und eines der Beispiele handelt von Fibonacci-Zahlen, und wie eine wiederkehrende Funktion die Fibonacci-Nummer für die n-te findet.
Der Code sieht so aus:
%Vor%Jetzt ist das nicht genau, weil ich von meinem Telefon tippe und ich verstehe, wie der Code funktioniert, er ruft sich selbst auf, bis er 1 zurückgibt, dann addiert er die Rückgabewerte, bis Sie die korrekte Fibonacci-Nummer haben für die Position in der Sequenz.
Ich brauche also keine Hilfe mit dem Code. Was ich brauche, ist zu verstehen, warum das funktioniert. Wie liefert das Hinzufügen aller Rückgaben die richtige Antwort?
Bitte erklären Sie mir, warum das funktioniert. Vielen Dank. Es treibt mich in den Wahnsinn.
Eine Fibonacci-Zahl ist definiert als die Summe der beiden vorhergehenden Fibonacci-Zahlen. Das ergibt folgendes:
%Vor%Also für die dritte Zahl (1 1 2 ) würden Sie das Ergebnis der Suche nach der vorherigen - dh der zweiten (1 1 2) Zahl nehmen und sie der Nummer vor der vorherigen - dh 1. ( 1 1 2) Nummer.
Sie müssen auch verstehen, dass das Programm den Wert der zwei vorhergehenden Zahlen berechnen muss, bevor es die Zahl berechnen kann, die Sie wissen möchten. Deshalb nennt es sich immer selbst - mit der gleichen Methode - bis es alles berechnet hat.
Rekursion ist wie folgt:
Ich würde vorschlagen zu verstehen, wie Rekursion funktioniert. Im Grunde läuft die fib-Funktion selbst mit einem kleineren Argument, bis das Argument auf 2 herunterkommt, dann gibt es nur 1 zurück.
%Vor%Eine Möglichkeit zu verstehen, wie es funktioniert, ist es, es in einem Debugger Schritt für Schritt auszuführen.
Es ist die Definition von Fibonacci-Zahlen.
n-te Fibonacci-Zahl gibt die Summe der (n-1) ten und (n-2) -ten Fibonacci-Zahlen zurück.
Wir können also induktiv beweisen, dass, wenn fib (n-1) und fib (n-2) die gültige (n-1) -te und (n-2) -te Fibonacci-Zahl ergeben, fib (n ) = fib (n-1) + fib (n-2) ist die gültige n-te Fibonacci-Zahl.
Der Grundschritt ist, dass fib (1) und fib (2) korrekt sind (das ist es fib (1) = fib (2) = 1) ...
Der Trick zum Verständnis der Rekursion ist das Verständnis des Stapels.
Ich bin in Zeile 2 in einer Funktion namens main , alle meine lokalen Variablen sind in meinem Stapelrahmen gespeichert:
Ich rufe dann fib(3) auf, also schiebt der Computer meine aktuelle Position (EIP) auf den Stapel, erstellt dann einen neuen Stapelrahmen für fib und fügt diesen hinzu. Ich kann immer nur auf den obersten Stapelrahmen zugreifen:
In Zeile 4 von fib ruft es fib erneut auf, so dass es wieder passiert:
Und das tut es immer wieder, da die Funktion rekursiv aufgerufen wird. Der Stapel wächst, bis etwas zurückkehrt. Zu diesem Zeitpunkt gibt er in Zeile 2 von fib 1 zurück. Dadurch wird der oberste Stapelrahmen gelöscht und verworfen. Anschließend wird die Ausführung an den gespeicherten Ausführungszeiger zurückgegeben, und das Programm wird dort fortgesetzt, wo es abgebrochen wurde
Schließlich landen Sie wieder in der aufrufenden Funktion (oder Sie bekommen einen Stapelüberlauf, wenn er zu groß wird). Das Wichtigste ist, dass jedes Mal, wenn die Funktion aufgerufen wird, ein neuer Stack-Frame mit all Ihren lokalen Variablen abgerufen wird und Ihre vorherige Position gespeichert wird. Das ist Rekursion.
Das Hauptproblem ist, dass bei der Rekursion von Personen immer die Fibonacci-Sequenz verwendet wird, was bedeutet, dass zwei rekursive Funktionsaufrufe auf einer Zeile stehen. Das ist unnötig verwirrend, da Sie mir sicher zustimmen werden!
Eine Fibonacci-Zahl ist definiert als die Summe der beiden vorherigen Fibonacci-Zahlen. Diese sind jeweils definiert als die Summe der beiden vorherigen Fibonacci-Zahlen. Etcetera, usw., bis du 1 erreichst. Jede zufällige Fibonacci-Zahl kann als die Summe zweier Fibonacci-Zahlen definiert werden; diese können rekursiv als die Summe von zwei Fibonacci-Zahlen usw. definiert werden. Das heißt, die Definition einer Fibonacci-Zahl ist grundsätzlich rekursiv; das heißt, die Definition davon beinhaltet, was es definiert.
Dieses Zeug kann knifflig sein, aber es ist sehr grundlegend für das Verständnis von Rekursion und Informatik. Mach weiter daran; Es wird irgendwann klicken.
Laut Definition sind Fibonacci-Zahlen die Summe der beiden vorherigen Zahlen in der Reihe (wobei die ersten beiden Zahlen 0 und 1 sind).
Wenn Sie also die Fibonacci-Nummer an einer Stelle erhalten, können Sie sie als Summe der beiden früheren Fibonacci-Nummern neu schreiben.
Mit Rekursion gehen Sie durch diesen Prozess, bis die "zwei Fibonacci-Nummern" 1 und 1 sind (im Falle dieses Algorithmus), und fahren Sie dann fort, die Zahlen zusammen zu addieren "sichern" Sie die Rekursion, bis Sie erhalten zurück zu Ihrem ursprünglichen Standort in der Reihenfolge.