DOUG LLOYD: Si vostè ha vist el vídeo a la recursivitat,
tot el procés podria tenir semblava una mica màgic.
Com funciona?
Com saben les funcions que que hagi d'esperar i esperar que un altre valor
per tornar d'una funció diferent cridar per tal d'obtenir el resultat que volem?
>> Bé, la raó que això funciona és perquè d'alguna cosa conegut com la pila de trucades.
Quan es crida a una funció, el sistema deixa de banda l'espai en memòria
per a aquesta funció per funcionar.
I cridem a aquests trossos de memòria que estan sent reservat per a cada funció
trucar a un marc de pila o un marc de funció.
I com era d'esperar, aquests marcs de pila
viure a la part pila de memòria.
>> Més d'una funció de marc de pila pot existir en la memòria en un moment donat.
Si crida a un moviment principal funció, i moure crida direcció,
les tres funcions tenen marcs oberts.
Però no tots tenen marcs actius.
Aquests marcs estan disposats en una pila.
I el marc de la més recentment anomenada
funció és sempre a la part superior de la pila.
I això és sempre el marc actiu.
Només hi ha realment alguna vegada un sol funció que és actiu alhora.
És l'única en la part superior de la pila.
>> Quan una funció crida a un altre funció, tipus de premses de pausa.
D'alguna manera està en espera, esperant.
I és empès un altre marc de pila a la pila a la part superior de la mateixa.
I això es converteix en el marc actiu.
I la trama immediatament per sota d'ella ha d'esperar
fins que sigui de nou el marc actiu abans que pugui reprendre el seu treball.
Quan una funció és completa i es fa,
el seu marc s'extreu de la pila.
Aquesta és la terminologia.
I la trama immediatament per sota d'ella, com acabo de dir,
es converteix en el nou marc actiu.
>> I si es diu a una altra funció, que va a fer una pausa de nou.
Marc de pila d'aquesta nova funció ser empès sobre la part superior de la pila.
Es va a fer la seva feina.
Podria esclatar enrere.
I l'altra funció a continuació es pot reprendre de nou.
>> Així que anem a anar a través d'aquest nou, mirant en la idea de la funció factorial
que hem definit en el vídeo recursivitat per veure
exactament com la màgia darrere d'això procés recursiu està tenint lloc.
Així que això és tot el nostre arxiu, oi?
Hem definit dos functions-- principal i fet.
I com era d'esperar, qualsevol programa C es va
començar en la primera línia de la principal.
>> Així que vam crear un nou marc de pila per al principal.
I que va a començar a córrer.
Trucades principals printf.
I printf va imprimir factorial de 5.
Bé, no ho sap el factorial de 5 és,
i així aquesta convocatòria ja està depenent d'una altra crida a la funció.
Així principal va a fer una pausa allà.
Vaig a deixar al seu fletxa just aquí, color
que el mateix color que el apilar marc de la dreta,
per indicar que la principal va congelar aquí mentre factorial de 5 es diu.
>> Així factorial de 5 es diu.
I que va començar en el mateix a partir de la funció factorial.
Es demana a la pregunta estic igual a 1?
És 5 igual a 1?
Bé, no.
Així que baixarà a l'altra banda, el retorn n vegades
factorial de n almenys 1.
Bé, està bé.
>> Així que ara, factorial de 5 és depenent d'una altra anomenada
a factorial, passant en 4 com a paràmetre.
I així el factorial d' 5 marc, que marc vermell,
va congelar aquí en aquesta línia he indicat
i esperar que factorial de 4 per acabar el que ha de fer perquè llavors
pot convertir-se en el marc actiu de nou.
>> Així factorial de 4 comença a el començament de factorial.
Es 4 igual a 1?
No, per la qual cosa va a fer el mateix.
Es va a anar per la branca més.
Va a arribar a aquesta línia de codi.
OK, vaig a tornar quatre vegades.
Oh, factorial de 3-- tan factorial de 4 depèn de factorial de 3 d'acabat.
>> I pel que ha de trucar factorial de 3.
I això va a anar a través de el mateix procés de nou.
Comença a través, arribi aquí.
Factorial de 3 depèn en factorial d'1.
Així factorial de 2 comença, arriba aquí.
Depèn de factorial d'1.
Factorial d'1 comença.
>> D'ACORD.
Així que ara, que estem rebent en algun lloc interessant, oi?
Així que ara, 1 és igual a 1.
I així tornem gener.
En aquest punt, estem tornant.
La funció està fet.
És un comportament és-- hi res més perquè ho faci,
per la qual cosa el marc de pila per factorial d'1 es dispara.
S'ha acabat.
Va tornar gener.
I ara, factorial de 2, que va ser el marc immediatament inferior
a la pila, es converteix en el marc actiu.
>> I pot recollir exactament on ho va deixar.
Ha estat esperant un factorial d'1 per acabar la seva feina.
Ara s'ha acabat.
I aquí estem.
>> Factorial d'1 retorna un valor d'1.
Així factorial de 2 llauna diguem tornar 2 vegades 1.
La seva obra es fa ara.
Es va tornar a 2 factorial de 3, que s'espera d'ell.
Factorial de 3 és ara el marc superior, el marc actiu a la pila.
I pel que diu, bé, bé, vaig tornar 3 vegades 2, que és 6.
I jo vaig a donar aquesta valorar de nou a factorial
de 4, que ha estat esperant per mi.
He acabat.
Factorial de 3 apareix de la pila, i factorial de 4 és ara el marc actiu.
>> 4 diu: OK, vaig a tornar 4 vegades el factorial de 3, que tenia sis anys.
Això era de valor que factorial de 3 va tornar.
I així 4 vegades 6 és 24.
I jo vaig a passar de tornar a factorial
de 5, que ha estat esperant per mi.
Factorial de 5 és ara el marc actiu.
Es va a tornar 5 vegades factorial de 4-- 5 vegades 24 o 120--
i donar a aquest valor tornar al principal, que té
estat esperant pacientment per a una molt de temps a la part inferior de la pila.
>> És el lloc on es va iniciar.
Es va fer aquesta crida.
Diversos quadres es van fer càrrec de la part superior.
Ara està de tornada a la part superior de la pila.
És el marc actiu.
Així principal té el valor 120 de tornada de factorial de 5.
Ha estat esperant per imprimir aquest valor.
I després es fa.
No hi ha més línies de codi en principal.
Així marc del principal es dispara la pila, i hem acabat.
>> I així és com funciona la recursivitat.
Així és com marcs de pila funcionen.
Aquestes crides a funcions això va succeir anteriorment
són només en pausa, a l'espera per a les trucades posteriors
per acabar, perquè puguin convertir-se en l'actiu emmarquen i acabar el que han de fer.
>> Sóc Doug Lloyd.
Això és CS50.