DOUG LLOYD: As jy gesien het die video op rekursie,
die hele proses kan hê was 'n bietjie magiese.
Hoe werk dit?
Hoe kan die funksies weet dat hulle nodig om te wag en wag vir 'n ander waarde
om terug te keer van 'n ander funksie bel om die resultaat wat ons wil hê?
>> Wel, die rede waarom hierdie werk is omdat van iets wat bekend staan ​​as die oproep stapel.
Wanneer jy 'n funksie, die stelsel ter syde stel ruimte in die geheue
vir daardie funksie om sy werk te doen.
En ons hierdie stukke van die geheue noem word opsy gesit vir elke funksie
roep 'n stapel raam of 'n funksie raam.
En as jy kan verwag, hierdie stapel rame
lewe op die stapel deel van die geheue.
>> Meer as een funksie stapel raamwerk kan bestaan ​​in die geheue op 'n gegewe tyd.
As hoof noem 'n funksie te beweeg, en skuif oproepe rigting,
al drie funksies oop rame.
Maar hulle het nie almal aktief rame.
Hierdie rame word in 'n stapel.
En die raam van die mees onlangs genoem
funksie is altyd op die top van die stapel.
En dit is altyd die aktiewe raam.
Daar is eintlik net een ooit funksie wat aktief op 'n tyd.
Dit is die een op die top van die stapel.
>> Wanneer 'n funksie roep 'n ander funksie, dit soort van druk pouse.
Dit is 'n soort van op te hou, en wag.
En 'n ander stapel raamwerk gestoot op die stapel op die top van dit.
En dit word die aktiewe raam.
En dadelik het die raam onder dit moet wag
totdat dit weer die aktiewe raam voordat dit sy werk kan hervat.
Wanneer 'n funksie is volledige en dit is gedoen,
sy raam inloer die stapel.
Dit is die terminologie.
En dadelik het die raam onder dit, soos ek het net gesê,
word die nuwe aktiewe raam.
>> En as dit 'n ander funksie noem, dit gaan om weer te breek.
Stapel raamwerk dat die nuwe funksie se wil gestoot op die top van die stapel.
Dit sal die werk te doen.
Dit mag dalk af pop rug.
En die ander funksie onder dit weer kan hervat.
>> So laat ons gaan deur middel van hierdie weer soek die idee van die faktoriaal funksie
dat ons omskryf in die rekursie video te sien
presies hoe die magic agter hierdie rekursiewe proses is wat plaasvind.
So dit is ons hele lêer, reg?
Ons gedefinieer twee functions-- hoof- en werklikheid.
En soos ons kan verwag, enige C program gaan
om te begin by die eerste reël van die belangrikste.
>> So skep ons 'n nuwe stapel raamwerk vir die hoof.
En dit gaan om te begin hardloop.
Main oproepe printf.
En printf gaan druk faktoriaal van 5.
Wel, beteken dit nie weet wat faktoriaal van 5 is,
en so hierdie oproep is reeds afhangende van 'n ander funksie oproep.
So belangrikste gaan reg daar breek.
Ek gaan verlaat sy arrow reg daar, kleur
dit dieselfde kleur as die stapel raam op regs,
aan te dui dat hoof gaan vries hier terwyl faktoriaal van 5 genoem word.
>> So faktoriaal van 5 genoem word.
En dit gaan om te begin by die heel begin van die faktoriaal funksie.
Dit vra die vraag ek gelyk aan 1?
Is gelyk aan 5 1?
Wel, nee.
So dit gaan om af te gaan om die ander kant, terugkeer N tye
faktoriaal van N minus 1.
Wel, OK.
>> So nou, faktoriaal van 5 is afhangende van 'n ander oproep
om faktoriaal, verby in 4 as die parameter.
En so het die faktoriaal van 5 raam, wat rooi raam,
gaan reg daar te vries op daardie lyn Ek het aangedui
en wag vir faktoriaal van 4 te voltooi wat dit nodig het om dit te doen nie, dan is dit
kan die aktiewe raam weer '.
>> So faktoriaal van 4 begin by die begin van faktoriaal.
Is gelyk aan 4 1?
Nee, so dit gaan om dieselfde ding te doen.
Dit gaan om af te gaan die ander tak.
Dit gaan die lyn van die kode te kry.
OK, ek gaan vier keer terug.
O, faktoriaal van 3-- so faktoriaal van 4 hang af van faktoriaal van 3 afwerking.
>> En so is dit nodig om faktoriaal van 3 noem.
En dit is nou eers deurgaan dieselfde proses weer.
Dit begin deur, kry hier.
Faktoriaal van 3 hang op faktoriaal van 1.
So faktoriaal van 2 begin, kry hier.
Dit hang af van faktoriaal van 1.
Faktoriaal van 1 begin.
>> OK.
So nou, is ons om iewers interessante, reg?
So nou, 1 is gelyk aan 1.
En so het ons terug 1.
Op hierdie punt, is ons terug.
Die funksie gedoen.
Dit is gedrag is-- daar niks anders om dit te doen nie,
en so die stapel raamwerk vir faktoriaal van 1 verskyn het.
Dis klaar.
Dit teruggekeer 1.
En nou, faktoriaal van 2, wat was die raam onmiddellik daaronder
in die stapel, word die aktiewe raam.
>> En dit kan optel presies waar dit opgehou het.
Dit is al vir 'n faktoriaal wag van 1 tot sy werk te volbring.
Dit het nou klaar.
En so hier is ons.
>> Faktoriaal van 1 teruggekeer 'n waarde van 1.
So faktoriaal van 2 blikkie sê terugkeer 2 keer 1.
Sy werk is nou gedoen.
Dit teruggekeer 2 tot faktoriaal 3, wat wag vir dit.
Faktoriaal van 3 is nou die top raam, die aktiewe raam in die stapel.
En so is dit sê, OK, goed, ek gaan 3 keer 2, wat is 6 keer.
En ek gaan om te gee wat waardeer terug na faktoriaal
van 4, het wat vir my gewag.
Ek is klaar.
Faktoriaal van 3 verskyn uit die stapel, en faktoriaal van 4 is nou die aktiewe raam.
>> 4 sê, OK, ek gaan 4 keer terug die faktoriaal van 3, wat ses was.
Dit was van die waarde wat faktoriaal van 3 teruggekeer.
En so 4 keer 6 is 24.
En ek gaan om te slaag wat terug na faktoriaal
van 5, het wat vir my gewag.
Faktoriaal van 5 is nou die aktiewe raam.
Dit gaan tot 5 keer terug faktoriaal van 4-- 5 keer 24 of 120--
en gee wat waarde Terug na die hoof, wat het
is baie geduldig wag vir 'n lang tyd aan die onderkant van die stapel.
>> Dit is waar dit begin het.
Dit het hierdie oproep.
Verskeie rame oorgeneem by die top.
Dit is nou weer terug op die top van die stapel.
Dit is die aktiewe raam.
So het die hoof waarde 120 terug van faktoriaal van 5.
Dit is al wat wag om druk wat waarde.
En dan is dit gedoen.
Daar is nie meer reëls van die kode in die belangrikste.
So belangrikste se raam verskyn af die stapel, en ons gedoen het.
>> En dit is hoe rekursie werk.
Dit is hoe stapel rame werk.
Diegene funksie oproepe wat voorheen gebeur het
is net op die pouse, en wag vir die daaropvolgende oproepe
te voltooi, sodat hulle kan die aktief raam en voltooi wat hulle nodig het om te doen.
>> Ek is Doug Lloyd.
Dit is CS50.