Rekursionsfunktion in Python
Betrachten Sie diese grundlegende Rekursion in Python:
%Vor%Was macht Sinn nach der (n-1) + (n-2) -Funktion der Fibonacci-Serie.
Wie führt Python eine Rekursion durch, die eine andere Rekursion enthält, die nicht innerhalb, sondern innerhalb derselben Codezeile liegt? Vervollständigen die "Finobacci (Nummer-1)" die gesamte Rekursion, bis sie "1" erreicht hat, und dann das Gleiche mit "Fibonacci (Nummer-2)" und füge sie hinzu?
Zum Vergleich, die folgende rekursive Funktion zum Erhöhen einer Zahl 'x' in Potenz 'y', kann ich die Rekursion verstehen, def power nennt sich selbst bis y == 0, da es nur einen rekursiven Aufruf in einer einzelnen Zeile gibt. Trotzdem sollten nicht alle Ergebnisse '1' sein, da der letzte Befehl 'return 1' ist, wenn y == 0, deshalb wird x nicht zurückgegeben?
%Vor%9 Antworten
Im Ausdruck fibonacci(number-1) + fibonacci(number-2) muss der erste Funktionsaufruf abgeschlossen sein, bevor der zweite Funktionsaufruf aufgerufen wird.
Also muss der gesamte Rekursionsstapel für den ersten Aufruf abgeschlossen sein, bevor der zweite Aufruf gestartet wird.
Kurze Antwort
Jedes Mal, wenn Python " fibonacci() " sieht, macht es einen anderen Funktionsaufruf und geht erst dann weiter, wenn dieser Funktionsaufruf beendet ist.
Beispiel
Nehmen wir an, es wird fibonacci(4) ausgewertet.
Sobald es die Zeile return fibonacci(number-1) + fibonacci(number-2) erreicht, "sieht" es den Aufruf fibonacci(number-1) .
Nun läuft fibonacci(3) -% fibonacci(number-2) wurde noch nicht gesehen. Um fibonacci(3) auszuführen, muss fibonacci(2)+fibonacci(1) ermittelt werden. Erneut führt er die erste Funktion aus, die er sieht, diesmal ist fibonacci(2) .
Nun trifft es schließlich auf einen Basisfall, wenn fibonacci(2) ausgeführt wird. Er bewertet fibonacci(1) , das 1 zurückgibt, und kann dann zum ersten Mal mit dem + fibonacci(number-2) -Teil eines fibonacci() -Aufrufs fortfahren. fibonacci(0) gibt 0 zurück, dann kann fibonacci(2) 1 zurückgeben.
Nun, da fibonacci(3) den von fibonacci(2) zurückgegebenen Wert erhalten hat, kann es mit der Auswertung von fibonacci(number-2) ( fibonacci(1) ) fortfahren.
Dieser Prozess wird fortgesetzt, bis alles ausgewertet wurde und fibonacci(4) kann 3 zurückgeben.
Um zu sehen, wie die gesamte Auswertung abläuft, folgen Sie den Pfeilen in diesem Diagramm:
Ich würde wirklich empfehlen, dass Sie Ihren Code in den Python-Tutor einfügen.
Sie werden in der Lage sein, es im laufenden Betrieb zu bekommen. Sehen Sie sich den Stackframe, Referenzen usw. an.
Sie können das Modul rcviz verwenden, um Rekursionen zu visualisieren, indem Sie einfach einen Dekorator zu Ihrer rekursiven Funktion hinzufügen.
Hier ist die Visualisierung für Ihren Code oben:
Die Kanten sind in der Reihenfolge nummeriert, in der sie von der Ausführung durchlaufen wurden. Die Ränder verblassen von Schwarz zu Grau, um die Reihenfolge des Durchlaufs anzuzeigen: schwarze Kanten zuerst, graue Kanten dauern.
(Ich habe das rcviz-Modul auf GitHub geschrieben.)
Sie können das selbst herausfinden, indem Sie eine Druckfunktion in die Funktion einfügen und eine Tiefe hinzufügen, damit wir sie schöner ausdrucken können:
%Vor% Aufruf fibonacci(5) gibt uns:
Wir können sehen, dass 5 Aufrufe von 4 aufruft, was zum Abschluss führt, und dann ruft es 3 auf, was dann zu Ende geht.
Matthew und Martjin haben Recht, aber ich dachte, ich könnte es ausarbeiten:
Python macht Sachen von links nach rechts, wann immer es geht. Ausnahmen von dieser Regel werden durch Klammern impliziert.
in x*power(x, y-1) : x wird ausgewertet und power wird ausgewertet
In fibonacci(number-1) + fibonacci(number-2) wird fibonacci(number-1) ausgewertet (rekursiv, bis zum Ende) und dann wird fibonacci(number-1) ausgewertet