Doug LLOYD: Ako ste vidjeli video na rekurzije,
cijeli proces bi mogao imati činilo malo čarobno.
Kako radi?
Kako funkcionira znaju da su morati čekati i čekati drugu vrijednost
da se vrate iz različitih funkcija poziv kako bi dobili rezultat koji želimo?
>> Pa, razlog je zato što to radi nešto poznat kao stog poziva.
Kada pozovete funkciju, Sustav izdvaja prostor u memoriji
za tu funkciju raditi svoj posao.
I mi zovemo ove komade memorije se odvojeno za svaku funkciju
pozvati okvir stog ili funkciju okvir.
I kao što ste mogli očekivati, ove stog okviri
živjeti na stog dio memorije.
>> Više od jednog funkcija stog okvira može postojati u memoriju u određenom trenutku.
Ako glavni naziva funkcija potez, i potez naziva smjer,
sve tri funkcije imaju otvorene okvire.
Ali nisu svi nemaju aktivne okvire.
Ti okviri su raspoređeni u stog.
A okvir iz nedavno uputili
Funkcija je uvijek na vrhu snopa.
A to je uvijek aktivan okvir.
Postoji samo jedan doista ikada funkcija koja je aktivna u isto vrijeme.
To je jedan na vrhu snopa.
>> Kada funkcija poziva drugu funkcija, ona vrsta preše pauzu.
To je vrsta na čekanju, čeka.
I još hrpa okvir gurnula na stog na vrhu.
I to postaje aktivni okvir.
A okvir odmah nastavku treba čekati
dok je ponovno aktivni okvir prije nego što može nastaviti svoj rad.
Kada je funkcija potpuna i to je učinio,
njegov okvir je popped off stog.
To je terminologija.
A okvir odmah ispod nje, kao što sam rekao,
postaje novi aktivni okvir.
>> A ako to zahtijeva drugi funkciju, to će ponovno pauzirati.
To nova funkcija je stog okvir će se guraju na vrhu snopa.
To će učiniti svoje.
To bi moglo pop back off.
I druga funkcija ispod se može nastaviti opet.
>> Tako ćemo proći kroz to opet, u potrazi na ideji faktorska funkcije
da mi je definirano u rekurzija videa vidjeti
točno kako je magija iza toga rekurzivna proces odvija.
Dakle, ovo je naša cijela datoteka, zar ne?
Definirali smo dva functions-- glavni i činjenica.
I kao što smo mogli očekivati, bilo C program ide
za početak na prvoj liniji glavna.
>> Tako smo stvorili novu stog okvir za glavni.
I to će se početi prikazivati.
Glavni pozivi printf.
I printf će ispis faktorijel 5.
Pa, to ne zna što faktorijalni 5 je,
pa to je poziv već Ovisno o drugom pozivu funkcije.
Dakle, glavna će pauzirati upravo tamo.
Ja ću ostaviti arrow pravo postoji, boju
je iste boje kao i stog okvir na desnoj strani,
naznačiti da je glavna će se smrznuti ovdje dok faktorijalni 5 zove.
>> Dakle faktorijalni 5 zove.
I to će početi na samom počevši od faktorska funkcije.
To postavlja pitanje ću jednak 1?
Je 5 jednak 1?
Pa, ne.
Dakle, to će ići dolje drugi dio, povratak n puta
faktorijalni n minus 1.
Pa, u redu.
>> Tako sada, faktorski 5 je ovisno o drugom pozivu
da faktorijalni, prolazeći u 4 kao parametar.
I tako faktorijel 5 okvira, koji crvenog okvira,
će zamrznuti upravo tamo na toj liniji sam naznačeno
i čekati faktorijel 4 do kraja ono što treba učiniti kako bi zatim ga
može ponovno postati aktivnom okviru.
>> Dakle faktorijel 4 počinje u početak faktorski.
4 jednak 1?
Ne, pa to će učiniti istu stvar.
To će ići dolje još granu.
To će doći do te linije koda.
U redu, ja ću se vratiti četiri puta.
Oh, faktorijel 3-- tako faktorijel 4 ovisi o faktorijel 3 dorade.
>> I tako to treba nazvati faktorijel 3.
I to će proći kroz opet isti proces.
Ona počinje kroz, dobiva ovdje.
Faktorijel 3 ovisi na faktorijel 1.
Dakle faktorijalni 2 počinje, dobiva ovdje.
To ovisi o faktorijel 1.
Faktorijel 1 počinje.
>> U REDU.
Tako sada, mi smo dobivanje negdje Zanimljivo, zar ne?
Tako sada, 1 jednak 1.
I tako smo se vratili 1.
U ovom trenutku, mi se vraćaju.
Funkcija je učinio.
To je ponašanje is-- postoji ništa drugo za to učiniti,
pa stog okvir za faktorijalni od 1. pops off.
To je završio.
Ona se vratila 1.
A sada, faktorski 2, koji je je okvir odmah ispod nje
u snopu, postaje aktivni okvir.
>> I to može pokupiti točno tamo gdje je stao.
To je bio čeka faktorski od 1 završiti svoj rad.
To je sada gotovo.
I tako smo ovdje.
>> Faktorijel 1 vratio vrijednost 1.
Dakle faktorijalni 2 limenke recimo vratili 2 puta 1.
Njegov rad je sada učinio.
To je vratila 2 do faktorski 3, koji je čekao nju.
Faktorijel 3 je sada na vrhu okvira, aktivni okvir u snopu.
I tako je, kaže, u redu, dobro, idem za povratak 3 puta 2, 6.
I ja ću dati da se vrijednost natrag na faktorski
4, koji je čekao me.
Gotov sam.
Faktorijel 3 pops off stog, a faktorijalni 4 je sada aktivan okvir.
>> 4 kaže: U redu, ja ću se vratiti 4 puta faktorijel od 3, što je šest.
To je vrijednost koja faktorijalni 3 se vraća.
I tako 4 puta 6 je 24.
I ja ću proći da natrag na faktorski
5, koji je čekao me.
Faktorijel 5 je sada aktivan okvir.
To će vratiti 5 puta faktorijel 4-- 5 puta 24 ili 120--
i dati tu vrijednost Povratak na stranicu, koja ima
Čekali vrlo strpljivo za dugo vremena na dnu snopa.
>> To je mjesto gdje je sve počelo.
To je napravio ovaj poziv.
Nekoliko okviri preuzeo na vrhu.
Sada je ponovno na vrhu dimnjaka.
To je aktivan okvir.
Dakle, glavni je dobio vrijednost 120 natrag od faktorijel 5.
To je čekala da ispisati tu vrijednost.
I onda se to radi.
Nema više linija koda u glavni.
Dakle, glavni je okvir pops off stog, a mi smo učinili.
>> I tako je rekurzija radi.
Tako stog okviri raditi.
Ti pozivi funkcija što se dogodilo prije
samo su na pauzi, čekajući za naknadne pozive
završiti tako da oni mogu postati aktivni okvir i završiti ono što im je potrebno učiniti.
>> Ja sam Doug Lloyd.
Ovo je CS50.