DOUG LLOYD: Om du har sett videon på rekursion, hela processen kan ha verkade lite magiskt. Hur fungerar det? Hur vet funktionerna vet att de måste vänta och vänta på ett annat värde att återvända från en annan funktion ringa för att få det resultat vi vill ha? Tja, är orsaken det fungerar eftersom av något som kallas anropsstacken. När du ringer en funktion, systemet upphäver utrymme i minnet för denna funktion att göra sitt arbete. Och vi kallar dessa bitar av minne som är avsätts för varje funktion ringa en stapel ram eller en funktion ram. Och som man kan förvänta sig, dessa stapelramar lever på stacken del av minnet. 

Mer än en funktion stack ram kan existera i minnet vid en given tidpunkt. Om huvud anropar en funktion flytta, och flytta samtal riktning, alla tre funktionerna har öppna ramar. Men de har inte alla har aktiva ramar. Dessa ramar är anordnade i en stapel. Och ramen från senast kallade funktion är alltid på toppen av stacken. Och det är alltid den aktiva ramen. Det finns egentligen bara någonsin en funktion som är aktiv åt gången. Det är den en på toppen av stacken. 

När en funktion anropar en annan funktion, typ av pressar det paus. Det är typ av på is, väntar. Och en annan stapel ramen skjuts på stacken ovanpå den. Och det blir den aktiva ramen. Och ramen omedelbart nedan den behöver vänta tills det återigen är den aktiva ramen innan den kan återuppta sitt arbete. När en funktion är fullständig och det är gjort, dess ram fälls av stapeln. Det är terminologin. Och ramen omedelbart under det, som jag nyss sagt, blir ny aktiv ram. 

Och om den anropar en annan funktion, det kommer att göra en paus igen. Den nya funktionen stack ram skjutas på toppen av stacken. Det kommer att göra sitt arbete. Det kan pop tillbaka ut. Och den andra funktionen Nedan kan återupptas igen. 

Så låt oss gå igenom det här igen, ser vid tanken på fakulteten funktion att vi definierat i rekursion video för att se exakt hur magin bakom detta rekursiv process äger rum. Så detta är hela vår fil, eller hur? Vi definierade två functions-- huvud och faktum. Och som vi kan förvänta sig, någon C-programmet går att börja på den första raden i huvud. 

Så skapar vi en ny bunt ram för main. Och det kommer att börja visas. Huvudsakliga samtal printf. Och printf kommer att skriva ut fakulteten av 5. Tja, inte vet vad fakulteten av 5 är, och så denna inbjudan är redan beroende på en annan funktionsanrop. Så huvud kommer att pausa direkt. Jag ska lämna sin pil just där, färg det har samma färg som den stack ram på höger, för att indikera att huvud kommer att frysa här medan fakulteten av 5 heter. 

Så fakulteten av 5 heter. Och det kommer att börja på mycket början av fakulteten. Det ställer frågan jag lika med 1? Är 5 lika med 1? Tja, nej. Så det kommer att gå ner till else delen retur n gånger fakulteten av n minus en. Okej då. 

Så nu är fakulteten av 5 beroende på ett annat samtal att faktoriella, passerar i 4 som parameter. Och så fakulteten för 5 ram, som röd ram, kommer att frysa direkt på den linje som jag har angett och vänta på fakulteten av 4 för att avsluta vad den behöver för att göra så att då det kan bli den aktiva ramen igen. 

Så fakulteten av 4 börjar vid början av faktoriell. Är 4 lika med 1? Nej, så det kommer att göra samma sak. Det kommer att gå ner i annat grenen. Det kommer att komma till den kodrad. OK, jag kommer att återvända fyra gånger. Åh, fakulteten för 3-- så fakulteten av 4 beror på fakulteten av 3 efterbehandling. 

Och så måste ringa fakulteten av 3. Och det är gonna gå igenom samma process igen. Det börjar genom, kommer hit. Fakulteten av 3 beror på fakulteten av 1. Så fakulteten av 2 startar, blir här. Det beror på fakulteten av ett. Fakultet av 1 starter. 

OK. Så nu, vi får någonstans intressant, eller hur? Så nu, ett är lika med 1. Och så vi tillbaka en. Vid det här laget är vi tillbaka. Funktionen är gjort. Det är beteendet är-- finns ingenting annat för att det ska göra, och så stapeln ramen för fakulteten av 1 dyker upp. Det är avslutat. Det återvände 1. Och nu, fakulteten av 2, som var i ramen omedelbart nedanför det i stapeln, blir den aktiva ramen. 

Och det kan plocka upp precis där den slutade. Det har väntat på en faktor 1 för att avsluta sitt arbete. Det har nu avslutats. Och så här är vi. 

Fakulteten av en return värdet 1. Så fakulteten av 2 burk säg tillbaka 2 gånger 1. Dess arbete är nu klar. Det åter 2 faktor 3, som stod. Fakulteten av 3 är nu den övre ramen, den aktiva ramen i stapeln. Och så säger, OK, ja, jag kommer att återvända 3 gånger 2, vilket är sex. Och jag kommer att ge det värderar tillbaka till fakulteten 4, har som väntat på mig. Jag är färdig. Fakulteten av 3 poppar av stapeln, och fakulteten av fyra är nu den aktiva ramen. 

4 säger, OK, jag kommer att återvända 4 gånger fakulteten av 3, vilket var sex. Det var av värde som fakulteten av 3 returneras. Och så 4 gånger 6 är 24. Och jag kommer att passera det tillbaka till faktor av 5, har som väntat på mig. Fakultet av 5 är nu den aktiva ramen. Det kommer att återvända 5 gånger fakulteten av 4-- 5 gånger 24 eller 120-- och ge det värdet tillbaka till huvud, som har väntat mycket tålmodigt för lång tid vid botten av stapeln. 

Det är där det började. Det gjorde denna uppmaning. Flera ramar tog över i toppen. Det är nu tillbaka på toppen av stacken. Det är den aktiva ramen. Så på got värdet 120 tillbaka från fakulteten av 5. Det har väntat på skriva ut det värdet. Och då är det gjort. Det finns inga fler rader kod i main. Så huvud ram dyker upp stacken, och vi är klara. 

Och det är hur rekursion fungerar. Det är hur stack ramar fungerar. Dessa funktionsanrop som hände tidigare är bara på paus, väntar för efterföljande anrop till slut så att de kan bli aktiva rama in och avsluta vad de behöver göra. 

Jag är Doug Lloyd. Detta är CS50.