DOUG LLOYD: Se vi vidis la video sur rekursio,
la tuta procezo havu ŝajnis iomete magia.
Kiel ĝi funkcias?
Kiel la funkcioj scias ke ili bezonas atendi kaj atendi alian valoron
reveni de malsama funkcio voki por akiri la rezulton ni deziras?
>> Nu, la kialo estas ĉar ĉi verkoj de io konata kiel la alvoko pilo.
Kiam vi nomas funkcio, la sistemo malobservos spaco en memoro
por tiu funkcio fari lia laboro.
Kaj ni nomas tiujn pecojn de memoro kiu estas estanta rezervita por ĉiu funkcio
voki stako aŭ funkcio kadro.
Kaj kiel vi povus atendi, tiuj pilo kadroj
vivi sur la stako parto de memoro.
>> Pli ol unu funkcion stako povas ekzisti en memoro je donita tempo.
Se ĉefa nomas funkcio movo, kaj movon nomas direkto,
ĉiuj tri funkcioj havas malfermita kadroj.
Sed ne ĉiuj havas aktivaj kadroj.
Tiuj framoj estas aranĝitaj en stako.
Kaj la kadro de la plej ĵuse nomita
funkcio estas ĉiam sur supro de la stako.
Kaj tio estas ĉiam la aktiva kadro.
Ekzistas nur vere iam oni funkcio jen aktiva samtempe.
Ĝi estas la unu sur supro de la stako.
>> Kiam funkcio vokas alian funkcio, ĝi ia premas paŭzo.
Ĝi ia estas sur tene, atendante.
Kaj alia stako estas pelita sur la pilo sur gxian supron.
Kaj tio igas la aktivan kadro.
Kaj la kadro tuj sube ĝi bezonas atendi
ĝis ĝi estas denove la aktiva kadro antaŭ ol ĝi povas rekomenci lian laboron.
Kiam funkcio estas kompleta kaj ĝi estas farita,
ĝia kadro estas krevita for la stako.
Tio estas la terminologio.
Kaj la kadro tuj sub ĝi, kiel mi ĵus diris,
iĝas la nova aktiva kadro.
>> Kaj se li nomas alian funkcion, ĝi tuj paŭzi denove.
Tiu nova funkcia stako volo esti puŝita sur la supro de la stako.
Ĝi faros lian laboron.
Eble pop reen for.
Kaj la alia funkcio sube ĝi povas rekomenci denove.
>> Do ni iru tra tiu denove, rigardanta ĉe la ideo de la faktorialo funkcio
ke ni difinis en la rekursio vídeo vidi
ĝuste kiel la magio malantaŭ tiu rekursia procezo okazas.
Do jen nia tuta dosiero, dekstra?
Ni difinis du functions-- ĉefa kaj fakto.
Kaj kiel ni povus atendi, ajna C programon tuj
komenci ĉe la unua linio de ĉefa.
>> Do ni krei novan stako por ĉefa.
Kaj ĝi tuj komencos kurado.
Ĉefa alvokoj printf.
Kaj printf tuj elprinti faktorialo de 5.
Nu, ĝi ne scias kio faktorialo de 5 estas:
kaj tiel ĉi alvoko estas jam depende alia funkcio nomita.
Do ĉefa tuj paŭzi prava.
Mi estas gonna forlasi liajn arrow Dekstre, koloro
ĝi la saman koloron kiel la stako dekstre
indiki ke ĉefa tuj frosti tie dum faktorialo de 5 estas nomita.
>> Do faktorialo de 5 estas nomita.
Kaj ĝi tuj starti je la tre komencante de la faktorialo funkcio.
Ĝi demandas la demandon mi egali al 1?
Estas 5 egala al 1?
Nu, ne.
Do ĝi estas tuj iri malsupren al la alia parto, reveno n fojoj
faktorialo de n minus 1.
Nu, bone.
>> Do nun, faktorialo de 5 estas depende alia alvoko
al faktorialo, pasante en 4 kiel la parametro.
Kaj tial la faktorialon 5 kadro, ke ruĝa kadro,
tuj frosti Dekstre en tiu linio mi indikis
kaj atendi faktorialon 4 fini kion bezonas fari tiel ke tiam
povas fariĝi la aktiva kadro denove.
>> Do faktorialon 4 komenciĝas ĉe la komenco de faktorialo.
Estas 4 egala al 1?
Ne, tiel ĝi tuj faros la samon.
Ĝi tuj malsupreniros la alia branĉo.
Ĝi tuj atingos tion linio de kodo.
OK, mi tuj revenos kvarfoje.
Ho, faktorialo de 3-- tiel faktorialon 4 dependas faktorialon 3 broĉon.
>> Kaj tial ĝi bezonas voki faktorialo de 3.
Kaj tio estas gonna trairu la sama procezo denove.
Ĝi komenciĝas per, ricevas tie.
Faktorialo de 3 dependas sur faktorialon 1.
Do faktorialon 2 startas, ricevas tie.
Dependas faktorialon 1.
Faktorialon 1 komencoj.
>> BONE.
Do nun, ni ricevas ie interesa, ĉu ne?
Do nun, 1 estas egala al 1.
Kaj tiel ni revenos 1.
Je tiu punkto, ni revenas.
La funkcio estas farita.
Estas konduto is-- ekzistas Nenio alia eblas fari,
kaj tiel la stako por faktorialon 1 krevas for.
Ĝi estas finita.
Ĝi revenis 1.
Kaj nun, faktorialo de 2, kiu Estis la kadro tuj sub ĝi
en la pilo, igas la aktivan kadro.
>> Kaj ĝi povas repreni ĝuste kie lasis.
Ĝi estas estita atendanta por faktorialo de 1 por fini lian laboron.
Ĝi nun finita.
Do jen ni estas.
>> Faktorialon 1 resendis valoro de 1.
Do faktorialon 2 ladskatolon diru reveni 2 fojoj 1.
Lia verko estas jam farita.
Ĝi revenis al 2 faktorialo de 3, kiu atendis ĝin.
Faktorialo de 3 estas nun la supro kadro, la aktiva kadro en la stako.
Kaj tiel diras, OK, bone, mi tuj reveni 3 fojojn 2, kiu estas 6.
Kaj mi tuj doni tiun taksos reen al faktorialo
de 4, kiu estis atendanta min.
Mi faris.
Faktorialo de 3 krevas for la stako, kaj faktorialo de 4 estas nun la aktiva kadro.
>> 4 diras, OK, mi tuj revenos 4 fojoj la faktorialo de 3, kiu estis ses.
Kiu estis de valoro kiu faktorialo de 3 revenis.
Kaj do 4 fojojn 6 estas 24.
Kaj mi tuj pasos ke reen al faktorialo
5, kiu estis atendanta min.
Faktorialo de 5 estas nun la aktiva kadro.
Ĝi tuj revenos 5 fojoj faktorialon 4-- 5 fojojn 24, aŭ 120--
kaj donu ke valoro reen al ĉefa, kiu havas
atendis tre pacience dum longa tempo ĉe la fundo de la stako.
>> Ĝi estas kie komenci.
Ĝi faris tiun alvokon.
Pluraj kadroj transprenis ĉe la supro.
Ĝi estas nun reen sur pinto de la stako.
Ĝi estas la aktiva kadro.
Do ĉefa havas la valoron 120 reen de faktorialo de 5.
Ĝi estas estita atendanta elprinti tiun valoron.
Kaj tiam ĝi estas farita.
Mankas pli linioj de kodo en ĉefa.
Do ĉefa la kadro krevas for la pilo, kaj ni faris.
>> Kaj tiel estas kiel rikuro funkcias.
Tiel estas kiel stako kadroj labori.
Tiuj funkcio alvokoj kiu okazis antaŭe
estas nur sur paŭzo, atendante por la postaj vokoj
fini tiel ili povas iĝi la aktiva enmarcar kaj fini kion ili devas fari.
>> Mi Doug Lloyd.
Jen CS50.