Die Rekursion mit der Fibonacci-Serie verstehen
Ich versuche Rekursion besser zu verstehen und wie Return-Anweisungen funktionieren. Als solches betrachte ich einen Code, der die Fibonacci-Zahl identifizieren soll, die mit einem bestimmten Begriff verbunden ist - in diesem Fall 4. Ich habe Schwierigkeiten, die else-Aussage zu verstehen.
%Vor%Ich habe versucht, mit Visualize Python zu untersuchen, was bei jedem Schritt passiert, aber ich verliere mich, wenn es die else-Anweisung trifft.
Es sieht so aus, als nehme es den Wert von n und subtrahiert 1, um einen neuen n-Wert von 3 zu erzeugen, den es an die Funktionsdefinition zurückgibt. Es scheint also, nur den Wert von der ersten Funktion in der else-Anweisung zurückzugeben. Die else-Anweisung wird jedoch geschrieben, um die Summe von 2 Funktionen f (n-1) + f (n-2) zurückzugeben. In diesem Fall dachte ich, der Rückgabewert wäre 5? Kannst du sogar 2 Funktionen zusammenfügen?
Vielen Dank im Voraus für Ihre Hilfe.
Hier ist ein Link zum Code in Visualize Python Summe von 2 Funktionen
2 Antworten
Im Zweifelsfall brechen Sie es einfach ab.
Der Baumfluss ist dem tatsächlichen Kontrollfluss entgegengesetzt, aber sobald Sie die Reihenfolge der Aufrufe verstehen, wird es klarer. Die Sache, die hier zu verstehen ist, besteht darin, dass Sie eine größere Berechnung in eine Summe kleinerer Berechnungen zerlegen, und Sie stoppen, wenn Sie den Basisfall (die if -Anweisungen) treffen. Jetzt können Sie alle kleinen Berechnungen durchführen und die Ergebnisse dieser kleinen Berechnungen zu einem größeren, größeren Ergebnis kombinieren, bis Sie Ihre endgültige Antwort haben.
Jedes Mal, wenn ein rekursiver Aufruf den Basisfall erreicht, gibt er entweder 1 oder 0 zurück, je nachdem, welcher Fall getroffen wurde. Dieser Wert wird an den vorherigen Aufrufer zurückgegeben. Um zu verstehen, überlegen:
%Vor% Beachten Sie, dass der Index die Tiefe der Rekursionsaufrufstruktur darstellt. Der Aufruf erfolgt durch f(2)2 . f(1)3 wird zuerst berechnet und 1 wird an f(2)2 zurückgegeben. f(0)3 wird dann berechnet, und 0 wird an f(2)2 zurückgegeben. Die zwei Rückgabewerte werden summiert und das Ergebnis ist 1 .
f(2)2 then gibt 1 an denjenigen zurück, der it aufgerufen hat, was in diesem Fall f(3)1 ist. f(3)1 heißt f(2)2 + f(1)2 , während diese andere f(1)2 auch 1 zu f(3)1 zurückgibt, die nun das mit dem Ergebnis von f(2)2 hinzufügt, um 2 zu bilden.
f(3)1 übergibt nun 2 an f(4)0 , seinen Aufrufer, der zufällig f(3)1 + f(2)1 aufgerufen hat ... und so geht es.
Eine alternative Betrachtungsweise besteht darin, mit dem ersten tatsächlich ausgeführten Funktionsaufruf zu beginnen: f(4)0 .
f(4)0 berechnet f(3)1 + f(2)1 . Aber um f(3)1 zu berechnen, muss es f(2)2 + f(1)2 kennen, und ähnlich muss f(2)1 berechnet werden, um f(1)2 + f(0)2 usw. zu wissen.