DOUG LLOYD: Als je hebt gezien de video op terugkeer, het hele proces kan hebben leek een beetje magisch. Hoe werkt het? Hoe weet de functies weten dat ze moeten wachten en wachten op een andere waarde terug vanuit een andere functie bellen om het resultaat dat we willen krijgen? Nou, de reden dat dit werkt is omdat iets bekend als de call-stack. Wanneer u een functie aan te roepen, de systeem vernietigt ruimte in het geheugen voor die functie om zijn werk te doen. En we die delen van het geheugen noemen worden gereserveerd voor elke functie bel een stack frame of een functie frame. En zoals je zou verwachten, deze stack frames live op de stapel deel van het geheugen. 

Meer dan één functie stack frame kunnen bestaan ​​in het geheugen op een bepaald moment. Als voornaamste noemt een functie zet, en beweging noemt richting, Alle drie functies hebben een open frames. Maar ze hebben niet allemaal actief frames. Deze frames zijn gerangschikt in een stapel. En het kader van de meest recent opgeroepen functie altijd boven de stapel. En dat is altijd het actieve frame. Er is maar één echt ooit functie is tegelijk actief. Het is de een boven op de stapel. 

Wanneer een functie noemt een ander functie, soort drukt pauze. Het is een soort van de wacht, wacht. En een andere stack frame wordt geduwd op de stapel op de top van het. En dat wordt de actieve frame. En onmiddellijk het frame daaronder moet wachten totdat weer het actieve lijst voordat het zijn werk kan hervatten. Als een functie compleet en het is gedaan, het frame is popped uit de stapel. Dat is de terminologie. En onmiddellijk het frame eronder, zoals ik net zei, wordt de nieuwe actieve frame. 

En als het een andere functie oproepen, het gaat om weer te pauzeren. Stack frame dat de nieuwe functie zal worden geduwd op de bovenzijde van de stapel. Het zal zijn werk doen. Het is misschien off pop terug. En de andere functie daaronder weer kan hervatten. 

Dus laten we gaan door dit opnieuw, zoek bij het idee van de faculteit-functie wij gedefinieerd in de recursie video te zien precies hoe de magie achter deze recursieve proces plaatsvindt. Dus dit is onze hele bestand, toch? We gedefinieerd twee functions-- hoofd- en feit. En zoals we kunnen verwachten, elke C programma gaat om te beginnen bij de eerste regel van de belangrijkste. 

Zo creëren we een nieuwe stack frame voor main. En het gaat om te beginnen met hardlopen. Belangrijkste oproepen printf. En printf gaat uitprinten faculteit van 5. Nou, het maakt niet weet Wat faculteit van 5 is, en zo deze oproep is al afhankelijk van een andere functie aan te roepen. Dus belangrijkste gaat om daar te pauzeren. Ik laat haar pijl daar, kleur Het dezelfde kleur als de stack frame op de juiste, geeft aan dat belangrijke zal bevriezen hier tijdens faculteit van 5 heet. 

Dus faculteit van 5 genoemd. En het gaat om te beginnen bij de begin van de faculteit-functie. Het stelt de vraag ben ik gelijk aan 1? Is 5 gelijk aan 1? Nou nee. Dus het gaat naar beneden te gaan naar de andere kant, rendement n keer faculteit van n minus 1. Nou oke. 

Dus nu, faculteit van 5 is afhankelijk van een ander gesprek tot Faculteit, passeren 4 in de parameter. En zo de faculteit van 5 frame, dat rood frame, gaat om daar te bevriezen op die lijn die ik heb aangegeven en wachten op faculteit van 4 tot finish wat het moet dat doen dan kan het actieve beeld weer te worden. 

Dus faculteit van 4 begint bij Begin factorial. 4 is gelijk aan 1? Nee, dus het gaat om hetzelfde te doen. Het gaat naar beneden te gaan de andere tak. Het gaat om die regel code te krijgen. OK, ik ga tot vier keer terug te keren. Oh, faculteit van 3-- zo faculteit van 4 afhankelijk faculteit van 3 finishing. 

En zo moet faculteit van 3 noemen. En dat is gonna gaan door hetzelfde proces opnieuw. Het begint door en krijgt hier. Faculteit van 3 afhangt op faculteit van 1. Dus faculteit van 2 begint, krijgt hier. Het hangt faculteit van 1. Faculteit van 1 begint. 

OK. Dus nu, we krijgen ergens interessant, toch? Nu, 1 gelijk is aan 1. En zo zijn we weer 1. Op dit moment, keren we terug. De functie heeft gedaan. Het is gedrag is-- er niets anders om het te doen, en zo de stack frame voor faculteit van 1 knalt uit. Het is klaar. Het leverde 1. Nu, faculteit van 2, waarvan was het frame direct eronder in de stapel, wordt de actieve frame. 

En het kan ophalen precies waar hij was gebleven. Het is al te wachten op een faculteit van 1 naar zijn werk te voltooien. Het is nu beëindigd. En zo zijn we hier. 

Faculteit van 1 terug een waarde van 1. Dus faculteit van 2 blikje zeg terugkeren 2 keer 1. Zijn werk wordt nu gedaan. Het is teruggekeerd 2 tot Faculteit van 3, die stond te wachten. Faculteit van 3 is nu de top frame, de actieve frame in de stapel. En zo zegt: OK, nou, ik ga tot 3 maal 2, dat 6 terug. En ik ga geven dat de waarde terug naar faculteit van 4, is die op me te wachten. Ik ben klaar. Faculteit van 3 knalt uit de stapel, en faculteit van 4 is nu de actieve frame. 

4 zegt: OK, ik ga 4 keer terug de faculteit van 3, waarvan zes was. Dat was van de waarde die faculteit van 3 teruggekeerd. En dus 4 maal 6 is 24. En ik ga voorbij die terug naar faculteit van 5, is die op me te wachten. Faculteit van 5 is nu de actieve frame. Het gaat om 5 keer terug faculteit van 4-- 5 tijden 24 of 120-- en geeft deze waarde terug naar hoofdgerecht, die heeft is heel geduldig te wachten op een tijd onderaan de stapel. 

Het is waar het begon. Het maakte deze oproep. Verschillende frames nam aan de top. Het is nu weer boven op de stapel. Het is de actieve frame. Dus belangrijkste kreeg de waarde 120 terug van faculteit van 5. Het is al te wachten om afdrukken die waarde. En dan is het gedaan. Er is niet meer regels code in de belangrijkste. Dus belangrijkste Het frame knalt off de stapel, en we zijn klaar. 

En dat is hoe recursie werkt. Dat is hoe stack frames werken. Die functie oproepen dat voorheen gebeurde zijn gewoon op pauze, wachtend voor de latere oproepen tot finish zodat ze het actief worden kaderen en afmaken wat ze moeten doen. 

Ik ben Doug Lloyd. Dit is CS50.