1 00:00:00,000 --> 00:00:05,587 2 00:00:05,587 --> 00:00:07,670 DOUG LLOYD: Wenn Sie gesehen haben die Video-on-Rekursion, 3 00:00:07,670 --> 00:00:10,170 den gesamten Prozess haben könnte schien ein bisschen magisch. 4 00:00:10,170 --> 00:00:10,930 Wie funktioniert das? 5 00:00:10,930 --> 00:00:15,010 Wie wirken sich die Funktionen wissen, dass sie müssen Sie warten und warten, einen anderen Wert 6 00:00:15,010 --> 00:00:19,150 von einer anderen Funktion zurückgeben rufen, um das Ergebnis, das wir bekommen? 7 00:00:19,150 --> 00:00:22,550 >> Nun, das ist der Grund, warum das funktioniert, weil von etwas, wie der Aufruf-Liste bekannt. 8 00:00:22,550 --> 00:00:26,360 Wenn Sie eine Funktion aufrufen, die System hebt Platz im Speicher 9 00:00:26,360 --> 00:00:28,120 für diese Funktion, um seine Arbeit zu tun. 10 00:00:28,120 --> 00:00:31,720 Und wir diese Stücke von Speicheraufruf, werden zur Seite für die jeweilige Funktion eingestellt 11 00:00:31,720 --> 00:00:35,670 rufen Sie einen Stapelrahmen oder eine Funktion Rahmen. 12 00:00:35,670 --> 00:00:38,290 Und wie man erwarten könnte, diese Stack-Frames 13 00:00:38,290 --> 00:00:41,000 leben auf dem Stack Teil des Speichers. 14 00:00:41,000 --> 00:00:43,960 15 00:00:43,960 --> 00:00:47,540 >> Mehr als eine Funktion Stapelrahmen Im Speicher können zu einem bestimmten Zeitpunkt vorhanden sind. 16 00:00:47,540 --> 00:00:51,240 Wenn Haupt ruft eine Funktion verschieben, und bewegen ruft Richtung, 17 00:00:51,240 --> 00:00:54,460 alle drei Funktionen haben offene Frames. 18 00:00:54,460 --> 00:00:57,350 Aber sie haben nicht alle aktiven Rahmen. 19 00:00:57,350 --> 00:00:59,410 Diese Rahmen werden in einem Stapel angeordnet. 20 00:00:59,410 --> 00:01:01,820 Und der Rahmen aus dem zuletzt aufgerufenen 21 00:01:01,820 --> 00:01:04,390 Funktion ist immer an der Spitze des Stapels. 22 00:01:04,390 --> 00:01:07,150 Und das ist immer der aktive Rahmen. 23 00:01:07,150 --> 00:01:10,420 Es gibt nur einen wirklich überhaupt Funktion, die zu einer Zeit aktiv ist. 24 00:01:10,420 --> 00:01:12,420 Es ist der eine auf der Oberseite des Stapels. 25 00:01:12,420 --> 00:01:17,620 >> Wenn eine Funktion ruft eine andere Funktion, es irgendwie drückt Pause. 26 00:01:17,620 --> 00:01:20,590 Es Art gehalten wird, wartet. 27 00:01:20,590 --> 00:01:24,050 Und noch ein Stapelrahmen geschoben auf den Stapel auf der Oberseite davon. 28 00:01:24,050 --> 00:01:26,150 Und das wird zum aktiven Rahmen. 29 00:01:26,150 --> 00:01:28,600 Und der Rahmen unmittelbar darunter muss warten 30 00:01:28,600 --> 00:01:33,560 bis es wieder die aktive Rahmen bevor er seine Arbeit wieder aufnehmen. 31 00:01:33,560 --> 00:01:35,870 Wenn eine Funktion vollständig und es fertig ist, 32 00:01:35,870 --> 00:01:37,720 seinem Rahmen wird vom Stapel geholt. 33 00:01:37,720 --> 00:01:38,950 Das ist die Terminologie. 34 00:01:38,950 --> 00:01:41,110 Und der Rahmen unmittelbar darunter, wie ich bereits sagte, 35 00:01:41,110 --> 00:01:42,880 wird zum neuen aktiven Rahmen. 36 00:01:42,880 --> 00:01:45,960 >> Und wenn es eine andere Funktion aufruft, es wird wieder anzuhalten. 37 00:01:45,960 --> 00:01:49,290 Stapelrahmen, die neue Funktion wird auf die Oberseite des Stapels geschoben werden. 38 00:01:49,290 --> 00:01:50,650 Es wird seine Arbeit zu tun. 39 00:01:50,650 --> 00:01:52,100 Es könnte off pop zurück. 40 00:01:52,100 --> 00:01:55,630 Und die andere Funktions darunter wieder fortzusetzen. 41 00:01:55,630 --> 00:02:00,080 >> Also lassen Sie uns durch diese gehen wieder suchen bei der Vorstellung des Fakultätsfunktion 42 00:02:00,080 --> 00:02:03,070 dass wir in die definierte Rekursion Video zu sehen, 43 00:02:03,070 --> 00:02:07,770 genau, wie die Magie dahinter rekursiven Prozess stattfindet. 44 00:02:07,770 --> 00:02:09,870 Das ist also unsere gesamte Datei, oder? 45 00:02:09,870 --> 00:02:14,000 Wir definierten zwei functions-- Haupt- und Tat. 46 00:02:14,000 --> 00:02:15,980 Und wir erwarten, Jeder C-Programm wird 47 00:02:15,980 --> 00:02:18,470 auf der ersten Zeile der Haupt starten. 48 00:02:18,470 --> 00:02:21,660 >> So schaffen wir einen neuen Stapelrahmen für Haupt. 49 00:02:21,660 --> 00:02:23,320 Und es geht um Lauf beginnen. 50 00:02:23,320 --> 00:02:25,270 Haupt Anrufe printf. 51 00:02:25,270 --> 00:02:29,390 Und printf Nahmen ausdrucken Fakultät von 5. 52 00:02:29,390 --> 00:02:31,440 Nun, es weiß nicht, welche Fakultät von 5, 53 00:02:31,440 --> 00:02:35,620 und so diesen Ruf bereits in Abhängigkeit von einem anderen Funktionsaufruf. 54 00:02:35,620 --> 00:02:37,270 So Haupt wird sich genau dort anzuhalten. 55 00:02:37,270 --> 00:02:39,103 Ich werde verlassen ihre arrow genau dort, Farbe 56 00:02:39,103 --> 00:02:41,360 sie dieselbe Farbe wie die Stack-Frame auf der rechten Seite, 57 00:02:41,360 --> 00:02:47,720 um anzuzeigen, dass Haupt wird zu frieren hier während Fakultät von 5 aufgerufen wird. 58 00:02:47,720 --> 00:02:49,300 >> So Fakultät von 5 aufgerufen wird. 59 00:02:49,300 --> 00:02:53,160 Und es geht um ganz am Anfang Anfang des Fakultätsfunktion. 60 00:02:53,160 --> 00:02:55,440 Er stellt die Frage, soll ich gleich 1? 61 00:02:55,440 --> 00:02:56,810 5 gleich 1? 62 00:02:56,810 --> 00:02:57,410 Nun, nein. 63 00:02:57,410 --> 00:03:01,110 Also, es wird nach unten zu gehen, die sonst teilweise Rück n-mal 64 00:03:01,110 --> 00:03:02,990 Fakultät von n minus 1. 65 00:03:02,990 --> 00:03:03,490 Gut, ok. 66 00:03:03,490 --> 00:03:07,070 >> So, jetzt ist Fakultät von 5 in Abhängigkeit von einem anderen Anruf 67 00:03:07,070 --> 00:03:09,740 um factorial, vorbei in 4 als Parameter. 68 00:03:09,740 --> 00:03:14,210 Und so ist die Fakultät 5 Rahmen, daß roten Rahmen, 69 00:03:14,210 --> 00:03:17,160 wird sich genau dort einfrieren bei dieser Linie habe ich angedeutet 70 00:03:17,160 --> 00:03:21,914 und warten Sie, Fakultät von 4 bis zum Ende was es zu, so dass es dann tun muss 71 00:03:21,914 --> 00:03:23,330 kann der aktive Frame wieder werden. 72 00:03:23,330 --> 00:03:26,890 >> So Fakultät von 4 beginnt bei der Beginn der faktoriellen. 73 00:03:26,890 --> 00:03:28,556 4 gleich 1? 74 00:03:28,556 --> 00:03:30,180 Nein, so es geht um das Gleiche zu tun. 75 00:03:30,180 --> 00:03:31,590 Es wird der ELSE-Zweig nach unten gehen. 76 00:03:31,590 --> 00:03:33,240 Es wird auf diese Zeile Code zu erhalten. 77 00:03:33,240 --> 00:03:35,710 OK, ich werde zu vier Mal zurück. 78 00:03:35,710 --> 00:03:41,270 Oh, Fakultät 3-- so Fakultät 4 hängt davon ab, Fakultät von 3 Finishing. 79 00:03:41,270 --> 00:03:43,055 >> Und so muss es Fakultät 3 aufrufen. 80 00:03:43,055 --> 00:03:45,180 Und das ist gonna durchlaufen der gleiche Vorgang erneut. 81 00:03:45,180 --> 00:03:48,200 Es beginnt durch, bekommt hier. 82 00:03:48,200 --> 00:03:50,980 Fakultät 3 hängt Auf Fakultät 1. 83 00:03:50,980 --> 00:03:53,750 So Fakultät von 2 beginnt, bekommt hier. 84 00:03:53,750 --> 00:03:56,310 Es hängt von Fakultät von 1. 85 00:03:56,310 --> 00:03:57,430 Fakultät 1 beginnt. 86 00:03:57,430 --> 00:03:57,650 >> OK. 87 00:03:57,650 --> 00:03:59,775 So, jetzt bekommen wir irgendwo interessant, nicht wahr? 88 00:03:59,775 --> 00:04:02,190 So, jetzt, 1 gleich 1 ist. 89 00:04:02,190 --> 00:04:05,130 Und so kehren wir 1. 90 00:04:05,130 --> 00:04:06,770 An dieser Stelle werden wir zurückkehren. 91 00:04:06,770 --> 00:04:07,880 Die Funktion fertig ist. 92 00:04:07,880 --> 00:04:11,140 Es ist das Verhalten ist-- es gibt sonst nichts für sie zu tun, 93 00:04:11,140 --> 00:04:17,006 so dass der Stapelrahmen für Fakultät 1 abspringt. 94 00:04:17,006 --> 00:04:17,589 Es ist fertig. 95 00:04:17,589 --> 00:04:19,480 Es ergab 1. 96 00:04:19,480 --> 00:04:23,370 Und nun, Fakultät von 2, die war der Rahmen unmittelbar darunter 97 00:04:23,370 --> 00:04:26,160 im Stapel, wird zum aktiven Rahmen. 98 00:04:26,160 --> 00:04:29,030 >> Und es abholen können genau dort, wo sie unterbrochen wurde. 99 00:04:29,030 --> 00:04:32,240 Es ist für einen faktoriellen gewartet von 1 auf seine Arbeit zu beenden. 100 00:04:32,240 --> 00:04:33,610 Es wurde nun beendet. 101 00:04:33,610 --> 00:04:35,510 Und so sind wir hier. 102 00:04:35,510 --> 00:04:38,080 >> Fakultät 1 zurück einen Wert von 1. 103 00:04:38,080 --> 00:04:42,430 So Fakultät von 2 Dose sagen wir zurückkehren 2 mal 1. 104 00:04:42,430 --> 00:04:43,680 Seine Arbeit ist nun getan. 105 00:04:43,680 --> 00:04:49,110 Es ergab 2 bis factorial von 3, was wartete sie. 106 00:04:49,110 --> 00:04:53,370 Fakultät 3 ist jetzt der obere Rahmen, der aktive Frame in dem Stapel. 107 00:04:53,370 --> 00:04:58,617 Und so heißt es, OK, gut, ich werde bis 3-mal 2, die 6 zurück. 108 00:04:58,617 --> 00:05:00,700 Und ich werde das zu geben Wert wieder auf factorial 109 00:05:00,700 --> 00:05:03,430 von 4, die gewartet hat für mich. 110 00:05:03,430 --> 00:05:04,500 Ich bin fertig. 111 00:05:04,500 --> 00:05:09,410 Fakultät 3 wird vom Stack genommen und Fakultät 4 ist jetzt der aktive Rahmen. 112 00:05:09,410 --> 00:05:13,510 >> 4 sagt: OK, ich werde bis 4 mal zurück die Fakultät von 3, die sechs Jahre alt war. 113 00:05:13,510 --> 00:05:15,980 Das war der Wert, Fakultät 3 zurückgegeben. 114 00:05:15,980 --> 00:05:19,010 Und so 4 mal 6 ist 24. 115 00:05:19,010 --> 00:05:20,990 Und ich werde weitergeben daß zurück zu factorial 116 00:05:20,990 --> 00:05:23,160 von 5, die gewartet hat für mich. 117 00:05:23,160 --> 00:05:25,270 Fakultät von 5 ist nun der aktive Rahmen. 118 00:05:25,270 --> 00:05:30,700 Es wird 5 mal zurück Fakultät 4-- 5 mal 24 oder 120-- 119 00:05:30,700 --> 00:05:32,722 und geben Sie diesen Wert zurück zur Hauptansicht, die hat 120 00:05:32,722 --> 00:05:35,680 sehr geduldig auf eine lange am Boden des Stapels. 121 00:05:35,680 --> 00:05:36,640 >> Es ist, wo es angefangen hat. 122 00:05:36,640 --> 00:05:37,670 Es machte diesen Aufruf. 123 00:05:37,670 --> 00:05:39,400 Mehrere Rahmen übernimmt an der Spitze. 124 00:05:39,400 --> 00:05:41,890 Es ist nun wieder an der Spitze des Stapels. 125 00:05:41,890 --> 00:05:43,450 Es ist der aktive Rahmen. 126 00:05:43,450 --> 00:05:47,810 So got den Wert 120 zurück von Fakultät von 5. 127 00:05:47,810 --> 00:05:50,750 Es ist zu lange gewartet Drucken Sie diesen Wert. 128 00:05:50,750 --> 00:05:51,657 Und dann ist es soweit. 129 00:05:51,657 --> 00:05:53,240 Es gibt keine weitere Codezeilen in Haupt. 130 00:05:53,240 --> 00:05:56,800 Also die Hauptrahmen erscheint off der Stapel, und wir sind fertig. 131 00:05:56,800 --> 00:05:58,992 >> Und das ist, wie Rekursion funktioniert. 132 00:05:58,992 --> 00:06:00,200 Das ist, wie Stack-Frames zu arbeiten. 133 00:06:00,200 --> 00:06:03,120 Diese Funktionsaufrufe dass zuvor passiert 134 00:06:03,120 --> 00:06:06,620 sind nur auf Pause, warten für die nachfolgenden Anrufe 135 00:06:06,620 --> 00:06:12,050 zu beenden, so dass sie die aktiv werden kann Rahmen und beenden, was sie tun müssen. 136 00:06:12,050 --> 00:06:13,060 >> Ich bin Doug Lloyd. 137 00:06:13,060 --> 00:06:14,880 Dies ist CS50. 138 00:06:14,880 --> 00:06:16,580