DOUG LLOYD: Hvis du har set videoen på rekursion, hele processen kan have syntes lidt magisk. Hvordan virker det? Hvordan funktionerne ved, at de nødt til at vente og vente på en anden værdi at vende tilbage fra en anden funktion ringe for at få det resultat, vi ønsker? Nå, grunden dette virker er, fordi af noget kendt som opkaldet stakken. Når du kalder en funktion, Systemet sætter til side plads i hukommelsen for denne funktion til at gøre sit arbejde. Og vi kalder disse bidder af hukommelse, er ved at blive afsat til hver funktion kalder en stak ramme eller en funktion ramme. Og som man kunne forvente, disse stakrammer bor på stakken del af hukommelsen. 

Mere end én funktion stakrammen kan eksistere i hukommelsen på et givet tidspunkt. Hvis vigtigste kalder en funktion flytte, og flytte kalder retning, alle tre funktioner har åbne rammer. Men de har ikke alle har aktive rammer. Disse rammer er placeret i en stak. Og rammen fra senest kaldte Funktionen er altid på toppen af ​​stakken. Og det er altid den aktive ramme. Der er kun virkelig nogensinde én funktion, der er aktive ad gangen. Det er den ene oven på stakken. 

Når en funktion kalder en anden funktion, det slags presser pause. Den slags er i venteposition og venter. Og en anden stakramme skubbes på stakken på toppen af ​​det. Og der bliver den aktive ramme. Og rammen straks nedenfor er det nødvendigt at vente indtil det er igen den aktive ramme før det kan genoptage sit arbejde. Når en funktion er komplet og det er gjort, dets ramme springer fra stakken. Det er terminologien. Og rammen straks under det, som jeg lige har sagt, bliver det nye aktive ramme. 

Og hvis den kalder en anden funktion, det kommer til at holde pause igen. Denne nye funktion er stakrammen vil skubbes på toppen af ​​stakken. Det vil gøre sit arbejde. Det kunne pop tilbage fra. Og anden funktion under den kan genoptage igen. 

Så lad os gå igennem det igen, ser ved tanken om fakultet funktion at vi defineret i rekursion video for at se præcis, hvordan magien bag dette rekursive proces finder sted. Så det er hele vores fil, ikke? Vi definerede to functions-- vigtigste og kendsgerning. Og som vi kunne forvente, hvilken som helst C-programmet går at starte på den første linje af main. 

Så vi oprette en ny stakrammen til main. Og det kommer til at begynde at køre. Vigtigste opkald printf. Og printf vil udskrive fakultet af 5. Tja, det ikke kender hvad fakultet af 5 er, og så denne indkaldelse er allerede afhængig af en anden funktion opkald. Så vigtigste kommer til at holde pause lige der. Jeg vil forlade sin pil lige der, farve det samme farve som stak ramme til højre, at angive, at main kommer til at fryse her, mens fakultet af 5 hedder. 

Så fakultet af 5 hedder. Og det kommer til at starte på den meget begyndelsen af ​​fakulteten funktion. Det stiller spørgsmålet er jeg lig med 1? Er 5 lig med 1? Nå, nej. Så det kommer til at gå ned til else side afkast n gange fakultet af n minus 1. Nå, OK. 

Så nu, fakultet af 5 er afhængig af et andet opkald at faktoriel, der passerer i 4 som parameter. Og så fakultet af 5 stel, at rød ramme, kommer til at fryse dér på denne linje, jeg har angivet og vente på fakultet af 4 til slut hvad det skal gøre, så så er det kan blive den aktive ramme igen. 

Så fakultet af 4 starter på begyndelsen af ​​fakultet. Er 4 lig med 1? Nej, så det kommer til at gøre det samme. Det kommer til at gå ned i andet gren. Det kommer til at komme til denne linje kode. OK, jeg har tænkt mig at vende tilbage fire gange. Åh, fakultet af 3-- så fakultet af 4 afhænger fakultet af 3. efterbehandling. 

Og så er det nødvendigt at kalde fakultet af 3. Og det skal nok gå igennem den samme proces igen. Det begynder ved, kommer. Fakultet af 3 afhænger på fakultet af en. Så fakultet af 2 starter, får her. Det afhænger af fakultet af en. Fakultet af 1 starter. 

OK. Så nu er vi få et sted interessant, ikke? Så nu, 1 er lig med 1. Og så vender vi tilbage 1. På dette tidspunkt, er vi tilbage. Funktionen er gjort. Det er adfærd is-- der er ikke andet for at gøre, og så stakken ramme til fakultet af 1 springer ud. Den er færdig. Det returnerede 1. Og nu, fakultet af 2, som var rammen umiddelbart under det i stablen, bliver den aktive ramme. 

Og det kan afhente præcis hvor den slap. Det har været ventet på en faktorielt 1 for at afslutte sit arbejde. Dette er nu afsluttet. Og så her er vi. 

Fakultet af 1 returnerede en værdi på 1. Så fakultet af 2 dåse siger returnere 2 gange 1. Dets arbejde er nu udført. Det er returneret 2 til faktorielt af 3, der ventede på det. Fakultet af 3 er nu den øverste ramme, den aktive ramme i stablen. Og så det siger, OK, godt, jeg vil at vende tilbage 3 gange 2, hvilket er 6. Og jeg har tænkt mig at give denne værdsætter tilbage til fakultet 4, er der ventet på mig. Jeg er færdig. Fakultet af 3 springer ud stakken, og fakultet af 4 er nu den aktive ramme. 

4 siger, OK, jeg har tænkt mig at vende tilbage 4 gange fakultet af 3, hvilket var seks. Det var af værdi, fakultet af 3 tilbage. Og så 4 gange 6 er 24. Og jeg har tænkt mig at passere det tilbage til fakultet af 5, har som ventet på mig. Fakultet af 5 er nu den aktive ramme. Det kommer til at vende tilbage 5 gange fakultet af 4-- 5 gange 24 eller 120-- og give denne værdi tilbage til main, som har ventet meget tålmodigt for en lang tid ved bunden af ​​stakken. 

Det er hvor det startede. Det gjorde denne indkaldelse. Flere rammer overtog øverst. Det er nu tilbage på toppen af ​​stakken. Det er den aktive ramme. Så vigtigste fik værdien 120 tilbage fra fakultet af 5. Det er blevet venter på at udskrive denne værdi. Og så er det gjort. Der er ikke flere linjer kode i main. Så vigtigste ramme springer ud stakken, og vi er færdig. 

Og det er sådan rekursion fungerer. Det er, hvordan stakrammer virker. Disse funktionskald der skete tidligere er lige på pause, venter for de efterfølgende opkald til slut så de kan blive aktive indramme og afslutte, hvad de skal gøre. 

Jeg er Doug Lloyd. Det er CS50.