DOUG LLOYD: Dacă ați văzut video de pe recursivitate,
întregul proces ar putea avea părea un pic magic.
Cum functioneazã?
Cum funcțiile știu că trebuie să așteptați și să aștepte pentru o altă valoare
pentru a reveni la o funcție diferită apel în scopul de a obține rezultatul ne-o dorim?
>> Ei bine, motivul este pentru că aceasta funcționează de ceva cunoscut sub numele de stiva de apel.
Când apelați un funcție, Sistemul pune deoparte spațiu în memorie
pentru această funcție pentru a face munca sa.
Și numim aceste bucăți de memorie care sunt retrase din circuitul agricol pentru fiecare funcție
apela un cadru stivă sau un cadru funcție.
Și, după cum s-ar putea aștepta, aceste cadre stiva
trăiesc din partea stiva de memorie.
>> Mai mult de o funcție cadru stivă poate exista în memorie la un moment dat.
În cazul în care principala solicită o mișcare funcție, și muta solicită direcție,
toate cele trei funcții au cadre deschise.
Dar nu toți au cadre activi.
Aceste cadre sunt aranjate într-o stivă.
Și a cadrelor din cel mai recent numit
Funcția este întotdeauna pe partea de sus a stivei.
Și care este întotdeauna cadrul activ.
Există doar foarte vreodată funcție care este activă la un moment dat.
Este cea de pe partea de sus a stivei.
>> Când o funcție solicită un alt funcție, ea un fel de prese pauză.
Acesta fel de este în așteptare, de așteptare.
Și un alt cadru stivă este împins pe stiva pe partea de sus a acesteia.
Și care devine cadrul activ.
Și rama imediat de mai jos care are nevoie să aștepte
până când este din nou cadru activ înainte de a putea relua activitatea.
Când o funcție este completă și e gata,
rama este mi-a venit de pe stivă.
Asta e terminologia.
Și rama imediat sub ea, ca tocmai am spus,
devine noul cadru activ.
>> Și dacă o numește o altă funcție, se va întrerupe din nou la.
Cadru stiva că nouă funcție va fi împins pe partea de sus a stivei.
Se va face lucrarea.
S-ar putea pop înapoi.
Și altă funcție de mai jos se poate relua din nou.
>> Așa că haideți să trec prin asta din nou, în căutarea la ideea de a funcției factorial
că am definit în recursivitate video pentru a vedea
exact cum magia din spatele acestei proces recursiv are loc.
Deci, aceasta este intreaga noastra fișier, nu?
Am definit doi functions-- principală și de fapt.
Și, după cum ne-am putea aștepta, orice program C se va
să înceapă de la prima linie de principal.
>> Deci, vom crea un nou cadru de stivă pentru principal.
Și o să înceapă de funcționare.
Solicită Principalele printf.
Și printf va imprima factorial din 5.
Ei bine, nu știe ce factorial de 5 este,
și așa mai departe acest apel este deja în funcție de un alt apel de funcție.
Deci principal este de gând să pauză acolo.
Voi lăsa sa săgeată acolo, de culoare
este aceeasi culoare ca și stivă cadru pe dreapta,
pentru a indica faptul că principala este de gând să înghețe aici în timp ce factorial de 5 se numește.
>> Deci, factorial de 5 se numește.
Și se va incepe de la foarte începutul funcției factorial.
Acesta solicită întrebarea sunt eu egal cu 1?
Este de 5 egală cu 1?
Ei bine, nu.
Așa că va merge în jos pentru a else parte, întoarcerea de n ori
factorial de n minus 1.
Bine.
>> Deci, acum, factorial de 5 este în funcție de un alt apel
la factorial trece în 4 ca parametru.
Și astfel factorialul 5 cadru, acel cadru roșu,
este de gând să înghețe acolo la acea linie am arătat
și așteptați pentru factorial de 4 pentru a termina ceea ce trebuie să facă, astfel încât, atunci
poate deveni din nou cadru activ.
>> Deci factorială a 4 începe la începutul factorial.
Este de 4 egal cu 1?
Nu, așa că va face același lucru.
Se va merge în jos ramura altceva.
Se va ajunge la acea linie de cod.
OK, am de gând să se întoarcă de patru ori.
Oh, factorial de 3-- astfel factoriale a 4 depinde factorial de 3 finisare.
>> Și așa trebuie să solicite factorial de 3.
Și asta o să treacă prin același proces din nou.
Acesta începe prin, ajunge aici.
Factorial de 3 depinde pe factorial de 1.
Deci, factorial de 2 începe, ajunge aici.
Depinde de factoriale de 1.
Factorial de 1 începe.
>> BINE.
Deci, acum, ne apropiem undeva interesant, nu?
Deci, acum, 1 este egal cu 1.
Și astfel ne întoarcem 1.
În acest moment, ne întoarcem.
Funcția a făcut.
Este un comportament este-- e nimic altceva pentru el să facă,
și astfel încât cadrul stivei de factorial de 1 sare de pe.
Este terminat.
A revenit 1.
Și acum, factorial de 2, care a fost cadrul imediat sub ea
în stivă, devine cadru activ.
>> Și se poate ridica exact unde a rămas.
A fost de așteptare pentru un factorial din 1 pentru a termina lucrările sale.
Ea a terminat acum.
Și astfel, aici suntem.
>> Factorial de 1 returnat o valoare de 1.
Deci, factorial de 2 poate să zicem reveni de 2 ori 1.
Activitatea sa este acum gata.
Este revenit 2 la factoriale 3, care a fost de așteptare pentru ea.
Factorial de 3 este acum rama superioară, cadrul activ în stivă.
Și astfel se spune, OK, bine, am de gând să se întoarcă de 3 ori 2, care este 6.
Și am de gând să dau asta valoare înapoi la factorial
de 4, care a fost de așteptare pentru mine.
Am terminat.
Factorial de 3 apare pe stivă, și factorial de 4 este acum cadru activ.
>> 4 spune, OK, am de gând să se întoarcă de 4 ori factorialul 3, care a fost de șase.
Asta a fost de valoare care factorial de 3 a revenit.
Și așa mai departe de 4 ori 6 este de 24.
Și am de gând să treacă înapoi la factoriale
de 5, care a fost de așteptare pentru mine.
Factorial de 5 este acum cadrul activ.
O să se întoarcă de 5 ori factorial de 4-- 5 ori 24, sau 120--
și să dea acea valoare Înapoi la care are
fost de așteptare foarte răbdător pentru o lungă perioadă de timp în partea de jos a stivei.
>> E în cazul în care a început.
Ea a făcut acest apel.
Mai multe cadre preluat în partea de sus.
Acum este din nou pe partea de sus a stivei.
Este cadru activ.
Deci principal a primit valoarea de 120 înapoi la factorial de 5.
A fost de așteptare pentru a imprima această valoare.
Și apoi se face.
Nu există E mai multe linii de cod în principal.
Deci, cadrul principal de apare pe stiva, și am terminat.
>> Și asta e modul în care funcționează recursivitate.
Asta e modul în care funcționează cadre stiva.
Aceste apeluri de funcții ce sa întâmplat anterior
sunt doar pe pauză, așteptând pentru apelurile ulterioare
pentru a termina astfel încât să poată deveni activ cadru și să termin ceea ce au nevoie să facă.
>> Sunt Doug Lloyd.
Acest lucru este CS50.