DOUG LLOYD: Wenn Sie gesehen haben die Video-on-Rekursion,
den gesamten Prozess haben könnte schien ein bisschen magisch.
Wie funktioniert das?
Wie wirken sich die Funktionen wissen, dass sie müssen Sie warten und warten, einen anderen Wert
von einer anderen Funktion zurückgeben rufen, um das Ergebnis, das wir bekommen?
>> Nun, das ist der Grund, warum das funktioniert, weil von etwas, wie der Aufruf-Liste bekannt.
Wenn Sie eine Funktion aufrufen, die System hebt Platz im Speicher
für diese Funktion, um seine Arbeit zu tun.
Und wir diese Stücke von Speicheraufruf, werden zur Seite für die jeweilige Funktion eingestellt
rufen Sie einen Stapelrahmen oder eine Funktion Rahmen.
Und wie man erwarten könnte, diese Stack-Frames
leben auf dem Stack Teil des Speichers.
>> Mehr als eine Funktion Stapelrahmen Im Speicher können zu einem bestimmten Zeitpunkt vorhanden sind.
Wenn Haupt ruft eine Funktion verschieben, und bewegen ruft Richtung,
alle drei Funktionen haben offene Frames.
Aber sie haben nicht alle aktiven Rahmen.
Diese Rahmen werden in einem Stapel angeordnet.
Und der Rahmen aus dem zuletzt aufgerufenen
Funktion ist immer an der Spitze des Stapels.
Und das ist immer der aktive Rahmen.
Es gibt nur einen wirklich überhaupt Funktion, die zu einer Zeit aktiv ist.
Es ist der eine auf der Oberseite des Stapels.
>> Wenn eine Funktion ruft eine andere Funktion, es irgendwie drückt Pause.
Es Art gehalten wird, wartet.
Und noch ein Stapelrahmen geschoben auf den Stapel auf der Oberseite davon.
Und das wird zum aktiven Rahmen.
Und der Rahmen unmittelbar darunter muss warten
bis es wieder die aktive Rahmen bevor er seine Arbeit wieder aufnehmen.
Wenn eine Funktion vollständig und es fertig ist,
seinem Rahmen wird vom Stapel geholt.
Das ist die Terminologie.
Und der Rahmen unmittelbar darunter, wie ich bereits sagte,
wird zum neuen aktiven Rahmen.
>> Und wenn es eine andere Funktion aufruft, es wird wieder anzuhalten.
Stapelrahmen, die neue Funktion wird auf die Oberseite des Stapels geschoben werden.
Es wird seine Arbeit zu tun.
Es könnte off pop zurück.
Und die andere Funktions darunter wieder fortzusetzen.
>> Also lassen Sie uns durch diese gehen wieder suchen bei der Vorstellung des Fakultätsfunktion
dass wir in die definierte Rekursion Video zu sehen,
genau, wie die Magie dahinter rekursiven Prozess stattfindet.
Das ist also unsere gesamte Datei, oder?
Wir definierten zwei functions-- Haupt- und Tat.
Und wir erwarten, Jeder C-Programm wird
auf der ersten Zeile der Haupt starten.
>> So schaffen wir einen neuen Stapelrahmen für Haupt.
Und es geht um Lauf beginnen.
Haupt Anrufe printf.
Und printf Nahmen ausdrucken Fakultät von 5.
Nun, es weiß nicht, welche Fakultät von 5,
und so diesen Ruf bereits in Abhängigkeit von einem anderen Funktionsaufruf.
So Haupt wird sich genau dort anzuhalten.
Ich werde verlassen ihre arrow genau dort, Farbe
sie dieselbe Farbe wie die Stack-Frame auf der rechten Seite,
um anzuzeigen, dass Haupt wird zu frieren hier während Fakultät von 5 aufgerufen wird.
>> So Fakultät von 5 aufgerufen wird.
Und es geht um ganz am Anfang Anfang des Fakultätsfunktion.
Er stellt die Frage, soll ich gleich 1?
5 gleich 1?
Nun, nein.
Also, es wird nach unten zu gehen, die sonst teilweise Rück n-mal
Fakultät von n minus 1.
Gut, ok.
>> So, jetzt ist Fakultät von 5 in Abhängigkeit von einem anderen Anruf
um factorial, vorbei in 4 als Parameter.
Und so ist die Fakultät 5 Rahmen, daß roten Rahmen,
wird sich genau dort einfrieren bei dieser Linie habe ich angedeutet
und warten Sie, Fakultät von 4 bis zum Ende was es zu, so dass es dann tun muss
kann der aktive Frame wieder werden.
>> So Fakultät von 4 beginnt bei der Beginn der faktoriellen.
4 gleich 1?
Nein, so es geht um das Gleiche zu tun.
Es wird der ELSE-Zweig nach unten gehen.
Es wird auf diese Zeile Code zu erhalten.
OK, ich werde zu vier Mal zurück.
Oh, Fakultät 3-- so Fakultät 4 hängt davon ab, Fakultät von 3 Finishing.
>> Und so muss es Fakultät 3 aufrufen.
Und das ist gonna durchlaufen der gleiche Vorgang erneut.
Es beginnt durch, bekommt hier.
Fakultät 3 hängt Auf Fakultät 1.
So Fakultät von 2 beginnt, bekommt hier.
Es hängt von Fakultät von 1.
Fakultät 1 beginnt.
>> OK.
So, jetzt bekommen wir irgendwo interessant, nicht wahr?
So, jetzt, 1 gleich 1 ist.
Und so kehren wir 1.
An dieser Stelle werden wir zurückkehren.
Die Funktion fertig ist.
Es ist das Verhalten ist-- es gibt sonst nichts für sie zu tun,
so dass der Stapelrahmen für Fakultät 1 abspringt.
Es ist fertig.
Es ergab 1.
Und nun, Fakultät von 2, die war der Rahmen unmittelbar darunter
im Stapel, wird zum aktiven Rahmen.
>> Und es abholen können genau dort, wo sie unterbrochen wurde.
Es ist für einen faktoriellen gewartet von 1 auf seine Arbeit zu beenden.
Es wurde nun beendet.
Und so sind wir hier.
>> Fakultät 1 zurück einen Wert von 1.
So Fakultät von 2 Dose sagen wir zurückkehren 2 mal 1.
Seine Arbeit ist nun getan.
Es ergab 2 bis factorial von 3, was wartete sie.
Fakultät 3 ist jetzt der obere Rahmen, der aktive Frame in dem Stapel.
Und so heißt es, OK, gut, ich werde bis 3-mal 2, die 6 zurück.
Und ich werde das zu geben Wert wieder auf factorial
von 4, die gewartet hat für mich.
Ich bin fertig.
Fakultät 3 wird vom Stack genommen und Fakultät 4 ist jetzt der aktive Rahmen.
>> 4 sagt: OK, ich werde bis 4 mal zurück die Fakultät von 3, die sechs Jahre alt war.
Das war der Wert, Fakultät 3 zurückgegeben.
Und so 4 mal 6 ist 24.
Und ich werde weitergeben daß zurück zu factorial
von 5, die gewartet hat für mich.
Fakultät von 5 ist nun der aktive Rahmen.
Es wird 5 mal zurück Fakultät 4-- 5 mal 24 oder 120--
und geben Sie diesen Wert zurück zur Hauptansicht, die hat
sehr geduldig auf eine lange am Boden des Stapels.
>> Es ist, wo es angefangen hat.
Es machte diesen Aufruf.
Mehrere Rahmen übernimmt an der Spitze.
Es ist nun wieder an der Spitze des Stapels.
Es ist der aktive Rahmen.
So got den Wert 120 zurück von Fakultät von 5.
Es ist zu lange gewartet Drucken Sie diesen Wert.
Und dann ist es soweit.
Es gibt keine weitere Codezeilen in Haupt.
Also die Hauptrahmen erscheint off der Stapel, und wir sind fertig.
>> Und das ist, wie Rekursion funktioniert.
Das ist, wie Stack-Frames zu arbeiten.
Diese Funktionsaufrufe dass zuvor passiert
sind nur auf Pause, warten für die nachfolgenden Anrufe
zu beenden, so dass sie die aktiv werden kann Rahmen und beenden, was sie tun müssen.
>> Ich bin Doug Lloyd.
Dies ist CS50.