DOUG LLOYD: Pokud jste viděli video na rekurze,
Celý proces může mít Zdálo se trochu kouzelné.
Jak to funguje?
Jak se funkce, vědí, že muset čekat a čekat na jinou hodnotu
až se vrátí ze jinou funkci zavolat, aby si výsledek chceme?
>> No, důvod, proč to funguje, je to, že něčeho známého jako zásobníku volání.
Při volání funkci, Systém vyčleňuje místo v paměti
pro tuto funkci dělat svou práci.
A my nazýváme tyto kousky paměti, která jsou vyčleněny pro každou funkci
volejte rám zásobníku nebo funkci rámce.
A jak se dalo očekávat, Tyto zásobník rámy
žijí na zásobníku část paměti.
>> Více než jedna funkce stack frame může existovat v paměti v daném čase.
Pokud hlavní volá funkci tah, a žádá, aby pohyb směrem,
všechny tři funkce mají otevřené rámy.
Ale ne všichni mají aktivní rámy.
Tyto rámy jsou uspořádány v zásobníku.
A rám z naposledy volal
funkce je vždy v horní části zásobníku.
A to je vždy aktivní rámeček.
Je tu jen opravdu vždy jednou Funkce, která je aktivní vždy.
Je to jeden na vrcholu zásobníku.
>> Když se funkce volá další funkce, to nějak lisy pauzu.
Tak nějak je v pořadí, a čekal.
A další stack frame je tlačena do zásobníku na vrcholu toho.
A to se stane aktivní rámeček.
A snímek bezprostředně Níže je třeba čekat
dokud není opět aktivní frame před tím, než může pokračovat v jeho práci.
Pokud je funkce kompletní a je to hotovo,
jeho rám je vyskočila z hromádky.
To je terminologie.
A snímek bezprostředně pod ní, jak jsem právě řekl,
se stane novým aktivním rámu.
>> A pokud to volá jinou funkci, že to bude zase pauzu.
Ta nová funkce stack frame bude nasunout na vrcholu zásobníku.
To bude dělat svou práci.
Mohlo by to pop zpátky.
A další funkce pod ní může pokračovat znovu.
>> Takže pojďme přes to ještě jednou, hledá při představě, že funkce faktoriálu
že definovány v rekurze video vidět
přesně tak, jak kouzlo za tím rekurzivní proces probíhá.
Takže to je celý náš soubor, že jo?
Definovali jsme dva functions-- hlavní a fakt.
A jak bychom mohli očekávat, jakýkoli program v jazyce C se děje
začít na prvním řádku hlavní.
>> Tak jsme vytvořit nový rámec pro hlavní zásobníku.
A bude to začít zobrazovat.
Hlavní volání printf.
A printf bude vytisknout faktoriál 5.
No, to neví co faktoriál 5 je,
a tak tento hovor je již v závislosti na jiném volání funkce.
Takže hlavní bude pozastavit právě tam.
Nechám své šipka vpravo tam, barva
to stejné barvy jako stack frame na pravé straně,
což znamená, že hlavní bude zmrazit tady, zatímco faktoriál 5 se nazývá.
>> Takže faktoriál 5 se nazývá.
A bude to začít u velmi začátek faktoriálové funkce.
To klade otázku mám činit až 1?
Je 5 rovno 1?
No, no.
Tak to bude, aby šel do else část, návrat n krát
faktoriál n minus 1.
No dobře.
>> Takže teď, faktoriál 5 je V závislosti na dalším hovoru
na faktoriál, předávání ve 4 jako parametr.
A tak se faktoriál 5 rám, který červeným rámečkem,
se chystá zmrazit právě tam v tomto řádku jsem uveden
a čekat na faktoriálem 4 až do konce co je třeba to udělat tak, že pak ji
se může stát opět aktivní rámeček.
>> Takže faktoriál 4 začíná na začátek faktoriál.
4 je rovno 1?
Ne, tak to bude dělat totéž.
Bude to jít dolů jiného větev.
Bude se dostat na tento řádek kódu.
OK, budu se vrátit čtyřikrát.
Oh, faktoriál 3-- tak faktoriálu 4 závisí na faktoriálem 3 úprav.
>> A tak je potřeba volat faktoriál 3.
A to bude projít opět stejný proces.
Začíná to přes, se sem dostane.
Faktoriál ze dne 3. závisí o faktoriálem 1.
Takže faktoriál 2 startů, se sem dostane.
Záleží na tom, faktoriálem 1.
Faktoriál z 1 startů.
>> DOBŘE.
Takže teď, se dostáváme nějakém zajímavém místě, že jo?
Nyní tedy, 1 je roven 1.
A tak se vracíme 1.
V tomto bodě, se vracíme.
Funkce se stalo.
Je to chování je-- je tu nic jiného pro to dělat,
a tak rámec fronty pro faktoriál 1 objeví off.
Je konec.
To se vrátil 1.
A teď, faktoriál 2, který byl rám bezprostředně pod ním
ve stohu, se stane aktivní rámeček.
>> A to může vyzvednout přesně tam, kde přestali.
Bylo to čekání na faktoriál 1. dokončit svou práci.
Nyní bylo dokončeno.
A tak jsme tady.
>> Faktoriál ze dne 1. vrátila hodnotu 1.
Takže faktoriál 2 může řekněme vrátit 2 krát 1.
Jeho práce je nyní hotovo.
Je to vrátil do 2 faktoriál ze dne 3., který čekal na něj.
Faktoriál ze 3 je nyní horní rám, aktivní rám ve stohu.
A tak říká, OK, dobře, jdu Pro návrat 3x 2, což je 6.
A já dám, že hodnotu zpět faktoriál
4, který byl na mě čeká.
Jsem hotov.
Faktoriál ze dne 3. objeví mimo zásobníku, a faktoriál 4 je nyní aktivní rámeček.
>> 4 říká, OK, budu se vrátit 4 krát faktoriál 3, což bylo šest.
To byla hodnota, která faktoriál 3 vrátil.
A tak 4 krát 6 je 24.
A já jdu projít že zpět do faktoriál
5, který byl na mě čeká.
Faktoriál 5 je nyní aktivní rámeček.
Bude to návrat 5x faktoriál 4-- 5 krát 24, nebo 120--
a dát tuto hodnotu zpět na hlavní, která má
Čekal velmi trpělivě dlouho ve spodní části zásobníku.
>> To je místo, kde to začalo.
To dělalo toto volání.
Několik snímků převzal na vrcholu.
To je nyní zpět v horní části zásobníku.
Je to aktivní rámeček.
Takže hlavní dostal hodnotu 120 zpět z faktoriálem 5.
Je to už čeká na vytisknout tuto hodnotu.
A pak se to dělá.
Neexistuje žádné další řádky kódu v hlavní.
Takže hlavní je rám objeví off zásobníku, a my jsme udělali.
>> A to je to, jak funguje rekurze.
To je, jak stack snímků pracovat.
Tyto volání funkcí že se stalo předtím
jsou jen na pauze, čekání pro následných výzev
až do konce, takže se může stát aktivním rám a dokončit to, co je třeba udělat.
>> Jsem Doug Lloyd.
To je CS50.