Rekursion-Funktion in Python
Berücksichtigen diese grundlegende Rekursion in Python:
def fibonacci(number):
if number == 0: return 0
elif number == 1:
return 1
else:
return fibonacci(number-1) + fibonacci(number-2)
Was Sinn macht, nach dem (n-1) + (n-2) - Funktion der Fibonacci-Reihe.
Wie funktioniert die Python ausführen Rekursion enthält eine weitere Rekursion nicht innerhalb, sondern innerhalb der gleichen code-Zeile? Funktioniert das " finobacci(Anzahl-1)' füllen Sie alle der Rekursion, bis es erreicht "1", und dann macht er das gleiche mit 'fibonacci(Zahl-2)" und fügen Sie Sie?
Zum Vergleich die folgende rekursive Funktion für die Erhöhung einer Anzahl 'x' in Kraft 'y', kann ich verstehen, die Rekursion, def macht den Aufruf, sich bis y==0 , da es nur einen rekursiven Aufruf in einer einzigen Zeile. Trotzdem sollten nicht alle Ergebnisse werden von '1' seit der letzten Befehl ausgeführt wird "return 1", wenn y==0, also ist x nicht zurückgegeben?
def power(x, y):
if y == 0:
return 1
else:
return x*power(x, y-1)
Du musst angemeldet sein, um einen Kommentar abzugeben.
In der expression
fibonacci(number-1) + fibonacci(number-2)
die erste Funktion aufrufen, müssen vor dem zweiten Funktionsaufruf aufgerufen wird.So, die ganze Rekursion-stack für den ersten Aufruf muss abgeschlossen sein, bevor der zweite Anruf gestartet wird.
Kurze Antwort
Jedes mal Python "sieht"
fibonacci()
macht es eine andere Funktion aufrufen und nicht weiter Voranschreiten, bis es fertig ist, die Funktion aufrufen.Beispiel
Also lasst uns sagen, es ist die Bewertung
fibonacci(4)
.Einmal wird es an der Linie
return fibonacci(number-1) + fibonacci(number-2)
es "sieht" der Ruffibonacci(number-1)
.So, jetzt läuft es
fibonacci(3)
- es noch nicht gesehenfibonacci(number-2)
überhaupt noch. Laufenfibonacci(3)
muss es herausfindenfibonacci(2)+fibonacci(1)
. Wieder, es läuft die erste Funktion, die es sieht, der dieses malfibonacci(2)
.Nun ist es endlich trifft ein base-case, wenn
fibonacci(2)
ausgeführt wird. Es wertetfibonacci(1)
gibt1
, dann, zum ersten mal, es kann weiterhin die+ fibonacci(number-2)
Teil einesfibonacci()
nennen.fibonacci(0)
zurück0
, die dann ermöglichtfibonacci(2)
zurück1
.Nun, dass
fibonacci(3)
abbekommen hat, der zurückgegeben Wert vonfibonacci(2)
ist, kann es Fortschritte zu bewertenfibonacci(number-2)
(fibonacci(1)
).Dieser Prozess wird fortgesetzt, bis alles ausgewertet wurde und
fibonacci(4)
zurückkehren können3
.Um zu sehen, wie die ganze Bewertung geht, befolgen Sie die Pfeile in diesem Diagramm:
Ja, das ist genau richtig. In anderen Worten, die folgenden
entspricht
Ich würde wirklich empfehlen, dass Sie Ihren code in die Python tutor.
Werden Sie der Lage sein, um es on-the-fly. Finden Sie unter den stackframe, Referenzen, usw.
Können Sie die rcviz Modul zu visualisieren, rekursionen, indem Sie einfach einen Dekorator zu Ihrem rekursiven Funktion.
Hier ist die Visualisierung für den code oben:
Die Kanten sind nummeriert nach der Reihenfolge, in der Sie waren durchzogen von der Ausführung. Die Ränder verblassen von schwarz zu Grau, um anzuzeigen Reihenfolge der traversal: schwarz-Kanten erste, graue Ränder letzten.
(Ich schrieb das rcviz Modul auf GitHub.)
Können Sie dies herauszufinden, sich selbst, indem Sie einen "drucken" - Funktion in die Funktion und das hinzufügen einer Tiefe also, wir können drucken Sie es aus schöner:
Aufrufen
fibonacci(5)
uns gibt:Können wir sehen, dass
5
Anrufe4
, die geht bis zur Fertigstellung, und dann ruft er3
, das geht dann bis zur Fertigstellung.Matthäus und MArtjin sind richtig, aber ich dachte, ich könnte aufwändig:
Python macht Sachen, von Links nach rechts, Wann immer er kann. Ausnahmen von dieser Regel sind implizit Klammern.
in
x*power(x, y-1)
:x
ausgewertet wird, dannpower
ausgewertetWährend in
fibonacci(number-1) + fibonacci(number-2)
,fibonacci(number-1)
ausgewertet wird (rekursiv, bis es anhält) und dannfibonacci(number-1)
ausgewertetIhre zweite Rekursion Funktionen bedeutet das (Beispiel), so ist 1 nicht zurückgegeben werden.