Ich habe die Fibonacci-Sequenz berechnet und bin über diesen Code gestolpert, den ich sehr oft gesehen habe:
%Vor%Was ich nicht verstehe ist, wie es funktioniert, besonders der Return-Teil am Ende: Ruft es die Fibonacci-Funktion wieder auf? Könnte mir jemand durch diese Funktion treten?
Ja, die Funktion ruft sich selbst auf. Zum Beispiel
%Vor%Beachten Sie, dass die Fibonacci-Funktion hier 9 Mal aufgerufen wird. Im Allgemeinen hat die naive rekursive Fibonacci-Funktion eine exponentielle Laufzeit , was ist normalerweise ein schlechtes Ding.
Dies ist ein klassisches Beispiel für eine rekursive Funktion , eine Funktion, die sich selbst aufruft.
> Wenn Sie es sorgfältig lesen, werden Sie sehen, dass es sich selbst oder recurse immer wieder aufruft, bis es den sogenannten Basisfall erreicht , wenn x <= 1 an diesem Punkt beginnt, "zurück zu verfolgen" und die berechneten Werte zusammenzufassen.
Der folgende Code gibt die Spur des Algorithmus deutlich aus:
%Vor%Die Ausgabe ist die folgende:
%Vor%Eine Baumdarstellung der Spur würde ungefähr wie
aussehen %Vor%Beim Schreiben rekursiver Funktionen sind folgende wichtige Punkte zu beachten:
1. Achte auf den Basisfall
Was wäre passiert, wenn wir if (x<=1) return 1; im obigen Beispiel vergessen hätten?
2. Stellen Sie sicher, dass sich die rekursiven Aufrufe in Richtung des Basisfalls verringern
Was wäre passiert, wenn wir den Algorithmus versehentlich geändert hätten, um fibonacci(x)+fibonacci(x-1);
gib Fibonacci (x-1) + Fibonacci (x-2) zurück;
Das ist furchtbar ineffizient. Ich schlage die folgende lineare Alternative vor:
%Vor%Die Fibonacci-Sequenz kann in funktionellen Sprachen prägnanter ausgedrückt werden.
%Vor%Da Ihre Frage mit C ++ markiert ist, möchte ich darauf hinweisen, dass diese Funktion auch zur Kompilierungszeit als Vorlage erreicht werden kann, falls Sie eine Variable zur Kompilierungszeit haben, mit der Sie sie verwenden können.
%Vor%Eine Weile, seit ich so etwas geschrieben habe, könnte es ein bisschen raus sein, aber das sollte es sein.
Ja, die Fibonacci-Funktion wird erneut aufgerufen, dies wird Rekursion genannt.
Genauso wie Sie eine andere Funktion aufrufen können, können Sie die gleiche Funktion erneut aufrufen. Da der Funktionskontext gestapelt ist, können Sie dieselbe Funktion aufrufen, ohne die aktuell ausgeführte Funktion zu stören.
Beachten Sie, dass Rekursion schwierig ist, da Sie die gleiche Funktion möglicherweise unendlich oft aufrufen und den Aufruf-Stack füllen können. Dieser Fehler wird "Stack Overflow" genannt (hier ist es!)
In C und den meisten anderen Sprachen darf sich eine Funktion selbst wie jede andere Funktion aufrufen. Dies wird Rekursion genannt.
Wenn es seltsam aussieht, weil es sich von der Schleife unterscheidet, die Sie schreiben würden, haben Sie Recht. Dies ist keine sehr gute Anwendung der Rekursion, da das Auffinden der n -ten Fibonacci-Nummer doppelt so lange dauert wie das Auffinden der n -1. Dies führt zu exponentieller Laufzeit in n .
Wenn Sie über die Fibonacci-Sequenz iterieren, wird die Laufzeit an linear in n verbessert, indem Sie sich an die vorherige Fibonacci-Zahl erinnern, bevor Sie mit der nächsten fortfahren.
Rekursion selbst ist nicht schrecklich. Tatsächlich kann die soeben beschriebene Schleife (und jede Schleife) als rekursive Funktion implementiert werden:
%Vor%Oder wenn Sie schneller sein möchten, aber mehr Speicher benötigen, verwenden Sie dies.
%Vor%und für n = 10 haben Sie zum Beispiel: fib [1] fib [2] fib [3] fib [4] fib [5] fib [6] fib [7] fib [8] fib [9] fib [10] 1 1 2 3 5 8 13 21 34 55 ''