DOUG LLOYD: Ak ste videli video na rekurzia, Celý proces môže mať Zdalo sa trochu čarovné. Ako to funguje? Ako sa funkcie, vedia, že musieť čakať a čakať na inú hodnotu až sa vráti zo inú funkciu zavolať, aby si výsledok chceme? No, dôvod, prečo to funguje, je to, že niečoho známeho ako zásobníka volania. Pri volaní funkciu, Systém vyčleňuje miesto v pamäti pre túto funkciu robiť svoju prácu. A my nazývame tieto kúsky pamäte, ktorá sú vyčlenené pre každú funkciu volajte rám zásobníka alebo funkciu rámca. A ako sa dalo očakávať, Tieto zásobník rámy žijú na zásobníku časť pamäti. 

Viac ako jedna funkcia stack frame môže existovať v pamäti v danom čase. Ak hlavný volá funkciu ťah, a žiada, aby pohyb smerom, všetky tri funkcie majú otvorené rámy. Ale nie všetci majú aktívny rámy. Tieto rámy sú usporiadané v zásobníku. A rám z naposledy volal funkcia je vždy v hornej časti zásobníka. A to je vždy aktívny rámček. Je tu len naozaj vždy raz Funkcia, ktorá je aktívna vždy. Je to jeden na vrchole zásobníka. 

Keď sa funkcie volá ďalšia funkcie, to nejako lisy pauzu. Tak nejako je v poradí, a čakal. A ďalšie stack frame je tlačená do zásobníka na vrchole toho. A to sa stane aktívnou rámček. A snímka bezprostredne Nižšie je potrebné čakať kým nie je opäť aktívny frame pred tým, než môže pokračovať v jeho práci. Ak je funkcia kompletný a je to hotovo, jeho rám je vyskočila z kôpky. To je terminológia. A snímka bezprostredne pod ňou, ako som práve povedal, sa stane novým aktívnym rámu. 

A ak to volá inú funkciu, že to bude zase pauzu. Tá nová funkcia stack frame bude nasunúť na vrchole zásobníka. To bude robiť svoju prácu. Mohlo by to pop späť. A ďalšie funkcie pod ňou môže pokračovať znovu. 

Takže poďme cez to ešte raz, hľadá pri predstave, že funkcie faktoriálu že definované v rekurzia video vidieť presne tak, ako kúzlo za tým rekurzívne proces prebieha. Takže to je celý náš súbor, že jo? Definovali sme dva functions-- hlavné a fakt. A ako by sme mohli očakávať, akýkoľvek program v jazyku C sa deje začať na prvom riadku hlavnej. 

Tak sme vytvoriť nový rámec pre hlavné zásobníka. A bude to začať zobrazovať. Hlavné volanie printf. A printf bude vytlačiť faktoriál 5. No, to nevie čo faktoriál 5 je, a tak tento hovor sa už v závislosti na inom volanie funkcie. Takže hlavný bude pozastaviť práve tam. Nechám svoje šípka vpravo tam, farba to rovnakej farby ako stack frame na pravej strane, čo znamená, že hlavná bude zmraziť tu, zatiaľ čo faktoriál 5 sa nazýva. 

Takže faktoriál 5 sa nazýva. A bude to začať u veľmi začiatok faktoriálnym funkcie. To kladie otázku mám činiť až 1? Je 5 presne 1? No, no. Tak to bude, aby šiel do else časť, návrat n krát faktoriál n mínus 1. No, OK. 

Takže teraz, faktoriál 5 je V závislosti na ďalšom hovoru na faktoriál, odovzdávanie v 4 ako parameter. A tak sa faktoriál 5 rám, ktorý červeným rámikom, sa chystá zmraziť práve tam v tomto riadku som uvedený a čakať na faktoriálu 4 až do konca čo je potrebné to urobiť tak, že potom ju sa môže stať opäť aktívny rámček. 

Takže faktoriál 4 začína na začiatok faktoriál. 4 je rovné 1? Nie, tak to bude robiť to isté. Bude to ísť dole iného vetva. Bude sa dostať na tento riadok kódu. OK, budem sa vrátiť štyrikrát. Oh, faktoriál 3-- tak faktoriálu 4 závisí na faktoriál 3 úprav. 

A tak je potreba volať faktoriál 3. A to bude prejsť opäť rovnaký proces. Začína to cez, sa sem dostane. Faktoriál z 3. závisí o faktoriál 1. Takže faktoriál 2 štartov, sa sem dostane. Záleží na tom, faktoriál 1. Faktoriál z 1 štartov. 

OK. Takže teraz, sa dostávame nejakom zaujímavom mieste, že jo? Teraz teda, 1 je rovný 1. A tak sa vraciame 1. V tomto bode, sa vraciame. Funkcia sa stalo. Je to správanie je-- je tu nič iné pre to robiť, a tak rámec frontu pre faktoriál 1 objavia off. Je koniec. To sa vrátil 1. A teraz, faktoriál 2, ktorý bol rám bezprostredne pod ním v stohu, sa stane aktívnou rámček. 

A to môže vyzdvihnúť presne tam, kde prestali. Bolo to čakanie na faktoriál 1. dokončiť svoju prácu. Teraz bolo dokončené. A tak sme tu. 

Faktoriál z 1. vrátila hodnotu 1. Takže faktoriál 2 môže povedzme vrátiť 2 krát 1. Jeho práca je teraz hotovo. Je to vrátil do 2 faktoriál z 3., ktorý čakal na neho. Faktoriál z 3 je teraz horný rám, aktívny rám v stohu. A tak hovorí, OK, dobre, idem Pre návrat 3x 2, čo je 6. A ja dám, že hodnotu späť faktoriál 4, ktorý bol na mňa čaká. Skončil som. Faktoriál z 3. objaví mimo zásobníka, a faktoriál 4 je teraz aktívny rámček. 

4 hovorí, OK, budem sa vrátiť 4 krát faktoriál 3, čo bolo šesť. To bola hodnota, ktorá faktoriál 3 vrátil. A tak 4 krát 6 je 24. A ja idem prejsť že späť do faktoriál 5, ktorý bol na mňa čaká. Faktoriál 5 je teraz aktívny rámček. Bude to návrat 5x faktoriál 4-- 5 krát 24, alebo 120-- a dať túto hodnotu späť na hlavnú, ktorá má Čakal veľmi trpezlivo dlho v spodnej časti zásobníka. 

To je miesto, kde to začalo. To robilo toto volanie. Niekoľko snímok prevzal na vrchole. To je teraz späť v hornej časti zásobníka. Je to aktívny rámček. Takže hlavný dostal hodnotu 120 späť z faktoriál 5. Je to už čaká na vytlačiť túto hodnotu. A potom sa to robí. Neexistuje žiadne ďalšie riadky kódu v hlavnej. Takže hlavné je rám objavia off zásobníka, a my sme urobili. 

A to je to, ako funguje rekurzia. To je, ako stack snímok pracovať. Tieto volania funkcií že sa stalo predtým sú len na pauze, čakanie pre nasledujúcich výziev až do konca, takže sa môže stať aktívnym rám a dokončiť to, čo je potrebné urobiť. 

Som Doug Lloyd. To je CS50.