DOUG LLOYD: Hvis du har sett videoen på rekursjon, hele prosessen kan ha virket litt magisk. Hvordan fungerer det? Hvordan vet de funksjonene vet at de må vente og vente på en annen verdi å returnere fra en annen funksjon ringe for å få det resultatet vi ønsker? Vel, er årsaken til at dette fungerer fordi av noe som kalles anrops stabelen. Når du ringer en funksjon, Systemet setter til side plass i minnet for at funksjonen for å gjøre sitt arbeid. Og vi kaller disse biter av minnet som blir satt til side for hver funksjon kalle en stabel ramme eller en funksjon ramme. Og som du kanskje forventer, disse stakkrammer leve på stakken delen av minnet. 

Mer enn én funksjon takken kan eksistere i minnet på et gitt tidspunkt. Hvis hoved kaller en funksjon flytte, og flytte samtaler retning, alle tre funksjonene har åpne rammer. Men ikke alle har aktive rammer. Disse rammene er ordnet i en stabel. Og rammen fra ringt Funksjonen er alltid på toppen av bunken. Og det er alltid den aktive rammen. Det er egentlig bare noen gang en funksjon som er aktiv om gangen. Det er den ene på toppen av bunken. 

Når en funksjon kaller en annen funksjon, det liksom presser pause. Det er liksom på vent, venter. Og en annen takken er skjøvet på stakken på toppen av det. Og det blir den aktive rammen. Og rammen straks under den trenger å vente inntil det er igjen den aktive rammen før den kan gjenoppta sitt arbeid. Når en funksjon er komplett og det er gjort, rammen er popped av stabelen. Det er terminologien. Og rammen straks under den, som jeg nettopp sa, blir den nye aktive rammen. 

Og hvis den kaller en annen funksjon, det kommer til å ta en pause igjen. Det nye funksjonen er takken vil skyves på toppen av bunken. Det vil gjøre sitt arbeid. Det kan komme tilbake på. Og den andre funksjonen Nedenfor kan fortsette igjen. 

Så la oss gå gjennom dette igjen, ser ved tanken på fakultetet funksjon at vi definert i rekursjon videoen for å se nøyaktig hvordan magien bak dette rekursiv prosess pågår. Så dette er vår hele filen, ikke sant? Vi definert to functions-- hoved og faktum. Og som vi kunne forvente, noen C program kommer å starte på den første linjen i hoved. 

Så vi oppretter en ny takken for main. Og det kommer til å begynne å kjøre. Hoved samtaler printf. Og printf kommer til å skrive ut fakultetet av fem. Vel, det vet ikke hva fakultetet av fem er, og så denne samtalen er allerede avhengig av en annen funksjon samtale. Så hoved kommer til å ta en pause der. Jeg skal forlate sin pil rett der, farge det samme farge som stable rammen til høyre, for å vise at hoved kommer til å fryse her mens fakultetet av fem kalles. 

Så fakultetet av fem kalles. Og det kommer til å starte helt på begynnelsen av fakultetet funksjonen. Det stiller spørsmålet jeg lik en? Er fem lik 1? Vel, nei. Så det kommer til å gå ned til den andre delen, retur n ganger fakultetet av n minus en. Vel, ok. 

Så nå, er fakultetet av 5 avhengig av en annen samtale til fakultetet, passerer i 4 som parameter. Og så fakultetet av 5 ramme, som rød ramme, kommer til å fryse der på den linjen jeg har indikert og vente på fakultetet av fire til slutt hva den trenger å gjøre, slik at da er det kan bli den aktive rammen igjen. 

Så fakultetet av 4 starter ved I begynnelsen av fakultetet. 4 er lik 1? Nei, så det kommer til å gjøre det samme. Det kommer til å gå ned den andre grenen. Det kommer til å komme til det kodelinje. OK, jeg kommer til å gå tilbake fire ganger. Oh, fakultetet av 3-- så Fakultet for 4 avhenger av fakultetet av tre etterbehandling. 

Og så den trenger å ringe fakultetet av tre. Og det kommer til å gå gjennom den samme prosessen på nytt. Det begynner gjennom, får her. Fakultetet av tre avhenger på fakultetet av en. Så fakultetet av 2 starter, får her. Det avhenger av fakultetet av en. Fakultetet av 1 starter. 

OK. Så nå, vi får et interessant sted, ikke sant? Så nå, er en lik en. Og så vi kommer tilbake en. På dette punktet, er vi tilbake. Funksjonen er gjort. Det er atferd er-- det er ingenting annet for at den skal gjøre, og så takken for fakultetet av en spretter av. Det er ferdig. Det returnert en. Og nå, fakultetet av 2, som var rammen umiddelbart under det i stabelen, blir den aktive rammen. 

Og det kan plukke opp akkurat der den slapp. Det er ventet på et fakultet av en til slutt sitt arbeid. Det er nå ferdig. Og så er vi her. 

Fakultetet av en returnerte verdien av en. Så fakultetet av 2 kan si tilbake 2 ganger 1. Arbeidet er nå ferdig. Det har returnert to til fakultetet av tre, som var ventet på det. Fakultetet av tre er nå den øverste rammen, den aktive rammen i stabelen. Og så står det, OK, vel, jeg skal å returnere 3 ganger 2, som er seks. Og jeg kommer til å gi den verds tilbake til fakultetet av 4, har som ventet på meg. Jeg er ferdig. Fakultetet av tre spretter av stabelen, og fakultetet av 4 er nå den aktive rammen. 

4 sier, OK, jeg kommer til å gå tilbake 4 ganger fakultetet av tre, som var seks. Som var av verdi som fakultetet av tre returnert. Og så 4 ganger 6 er 24. Og jeg kommer til å passere det tilbake til fakultetet av fem, har som ventet på meg. Fakultetet av fem er nå den aktive rammen. Det kommer til å gå tilbake 5 ganger fakultetet av 4-- 5 ganger 24, eller 120-- og gi den verdien tilbake til hovedsiden, som har ventet veldig tålmodig på en lang tid i bunnen av stabelen. 

Det er der den startet. Det gjorde denne samtalen. Flere rammer overtok på toppen. Det er nå tilbake på toppen av bunken. Det er den aktive rammen. Så hoved fikk verdien 120 tilbake fra fakultetet av fem. Det har vært ventet å skrive ut denne verdien. Og så er det gjort. Det er ingen flere linjer med kode i main. Så hoved ramme spretter av stabelen, og vi er ferdige. 

Og det er hvordan rekursjon fungerer. Det er slik stack rammer fungere. Disse funksjonskall som skjedde tidligere er bare på pause, venter for de påfølgende samtaler til slutt slik at de kan bli virke ramme og fullføre det de må gjøre. 

Jeg er Doug Lloyd. Dette er CS50.