Ich beschäftige mich immer noch mit Rekursion, und ich denke, ich bekomme grundlegende wie faktorielle. Aber ich möchte eine weitere Erklärung, wenn die Return-Anweisung ein wenig komplexer ist, wie im folgenden Ausschnitt:
%Vor%Kommt es in der return-Anweisung vor, dass der Fibonacci (n-1) vollständig durchläuft, bevor er den Fibonacci (n-2) -Schritt durchläuft (macht das Sinn)? Wenn dem so ist, scheint dies sehr schwer vorstellbar zu sein.
Ja, ein Aufruf wird den ganzen Weg rückwärts durchlaufen und zurückgeben, bevor der andere beginnt, auszuführen.
Die Reihenfolge des Aufrufs in Java ist wohldefiniert: fibonacci(n-1) geht vor fibonacci(n-2) .
Bearbeiten: Da die Frage ursprünglich das [C ++] -Tag enthielt, ist hier der C ++ - Teil der Geschichte: einer der beiden Aufrufe muss noch vervollständigt werden, bevor der andere beginnt zu laufen, aber was Eine, fibonacci(n-1) oder fibonacci(n-2) , ist nicht spezifiziert.
Da die Funktion keine Nebenwirkungen hat, spielt es keine Rolle, welcher der beiden Aufrufe zuerst ausgeführt wird. Das einzige, was für das Verständnis der Rekursion wichtig ist, ist, dass beide Aufrufe abgeschlossen werden müssen, und ihre Ergebnisse müssen addiert werden, bevor der Aufruf auf der aktuellen Ebene zurückkehrt.
Es ist nicht viel anders als eine andere Funktion als sie selbst aufzurufen. Es muss beendet werden, bevor die aufrufende Funktion irgendetwas mit dem Ergebnis tun kann.
%Vor% Versuchen wir jetzt 2 , was nicht der Basisfall ist:
In Wirklichkeit passiert also, dass der Aufruf von fibonacci2 während jeder der zwei rekursiven Aufrufe von finish wartet, genau wie eine Funktion, die System.out.println warten würde, bis sie das Argument zuvor ausgedruckt hat Weiter zur nächsten Zeile. Rekursion ist nicht besonders.
Wissenswertes: Dies ist die Originalserie von Fibonacci selbst. Moderne Mathematiker starten die Reihe mit n als Basisfallergebnis und machen die Reihe 0, 1, 1, 2, ... statt 1, 1, 2, 3, ... .
es funktioniert auf diese Weise:
Fibonacci-Programm :
%Vor%Erläuterung: In der Fibonacci-Folge ist jeder Gegenstand die Summe der beiden vorherigen. Also nach rekursivem Algorithmus.
Also,
%Vor% Nun kennst du fibonacci(1)==1 and fibonacci(0) == 0 bereits. So können Sie anschließend die anderen Werte berechnen.
Jetzt,
%Vor%Bei mehrfacher Rekursion ruft das Programm sich selbst mit seinem ersten Aufruf auf, bis der Basisfall erreicht ist, in diesem Fall fibonacci (n-1) ; Danach stoppt die Rekursion und gibt ihren Wert zurück, um den Wert weiterhin an den zweiten Teil der Rekursion fibonacci (n-2) zu übergeben.
Wenn Sie die Mehrfachrekursion im Programm nicht visualisieren Fibonacci-Rekursionsbaum kann hilfreich sein.
