Doug LLOYD: Se xa viu o vídeo en recursão, todo o proceso pode ter parecía un pouco máxico. Como funciona isto? Como as funcións de saber que necesitamos esperar e esperar por outro valor para volver dunha función diferente chamar a fin de obter o resultado que queremos? Ben, a razón é porque funciona de algo coñecido como a pila de chamadas. Cando chamar unha función, o sistema deixa de lado o espazo na memoria para esa función para facer o seu traballo. E chamamos eses bloques de memoria que están sendo retiradas para cada función chamar un cadro de pila ou marcos función. E como podería esperar, estes cadros de pila viven na parte pila de memoria. 

Máis que unha función de cadro de pila poden existir en memoria nun momento dado. Se principal chama un movemento función, e chama movemento dirección, as tres funcións teñen cadros abertos. Pero eles non teñen cadros activos. Estes cadros son dispostas nunha pila. E o cadro do máis recentemente chamado función é sempre na parte superior do conxunto. E iso é sempre o cadro activo. Só hai realmente sempre unha función que é activo en un tempo. É un na parte superior do conxunto. 

Cando unha función chama outra función, el presiona tipo de pausa. É unha especie de está esperando, esperando. E outro cadro de pila é empurrado para a pila enriba dela. E iso se fai o cadro activo. E o cadro inmediatamente debaixo del necesita esperar ata que sexa de novo o cadro activo antes de que poida retomar o seu traballo. Cando unha función é completo e está feito, seu cadro é eliminado da pila. Esa é a terminoloxía. E o cadro inmediatamente debaixo del, como acabo de dicir, pasa a ser o novo marco activo. 

E se chama outra función, vai deixar de novo. Pila cadro que nova función será ser empuxada para arriba da pila. Vai facer o seu traballo. Pode aparecer de novo fóra. E a outra función debaixo del pode retomar de novo. 

Entón, imos pasar por iso de novo, ollando coa idea da función factorial que define na video recursão para ver exactamente como a maxia detrás diso proceso recursivo se produciron. Polo tanto, este é todo o noso arquivo, non? Definimos dous funcións no inicio e feito. E, como era de esperar, calquera programa C vai para comezar na primeira liña do principal. 

Entón, creamos un novo marco de pila para o inicio. E vai a comezar a carreira. Principais chamadas printf. E printf vai imprimir factorial de 5. Ben, el non sabe o factorial de 5 é, e por iso esta chamada xa é dependendo de outra chamada de función. Así principal vai parar aí. Vou deixar o seu frecha para a dereita alí, cor que a mesma cor que o apilar cadro á dereita, para indicar que o principal vai conxelar aquí mentres factorial de 5 chámase. 

Entón factorial de 5 chámase. E que vai comezar no inicio da función factorial. Fai a pregunta que eu estou igual a 1? 5 é igual a 1? Ben, non. Entón, que vai baixar para a outra parte, o retorno n veces factorial de n menos 1. Ben, OK. 

Entón, agora, factorial de 5 é dependendo outra chamada a factorial, pasando en 4 como o parámetro. E así o factorial de 5 cadro, que marco vermella, vai conxelar alí en que a liña eu indiquei e esperar por factorial de 4 para rematar o que cómpre facer para que, a continuación, pode facer o cadro activo de novo. 

Entón factorial de 4 comeza en o inicio da factorial. 4 é igual a 1? Non, polo que vai facer o mesmo. Vai descender a rama máis. Chegará a esta liña de código. OK, eu vou devolver catro veces. Oh, factorial de 3-- tan factorial 4 depende factorial de 3 de acabado. 

E por iso que chamar factorial 3. E iso vai pasar por o mesmo proceso unha vez máis. Comeza a pasar, queda aquí. Factorial de 3 depende en factorial de 1. Entón factorial de 2 comeza, queda aquí. Depende factorial de 1. Factorial de 1 comeza. 

Aceptar. Entón, agora, estamos chegando nalgún lugar interesante, non? Entón agora, 1 é igual a 1. E así volvemos 1. Neste momento, estamos a volver. A función está feito. É un comportamento é-- hai nada máis para el facer, e así o cadro de pila para factorial de 1 aparece fóra. Está rematado. Volveu 1. E agora, factorial de 2, que foi a trama debaixo dela na pila, se fai o cadro activo. 

E pode incorporarse exactamente de onde parou. Está esperando por un factorial de 1 para rematar o seu traballo. El xa rematou. E entón aquí estamos. 

Factorial de 1 devolto un valor de 1. Entón factorial de 2 lata digamos volver 2 veces 1. O seu traballo xa está feito. Devólvese 2 a factorial de 3, que estaba esperando por el. Factorial de 3 agora cadro superior, o marco activo na pila. E así se di, OK, ben, eu vou para volver 3 veces 2, que é 6. E eu vou dar que valor ao factorial 4, que foi esperando por min. Rematei. Factorial de 3 aparece fóra da pila, e factorial de 4 é agora o cadro activo. 

4 di: OK, eu vou volver 4 veces o factorial de 3, que tiña seis anos. Iso era de valor que factorial de 3 devolto. E así é 4 veces 6 24. E eu vou pasar que volve á factorial de 5, que foi esperando por min. Factorial de 5 é agora o cadro activo. Volverá 5 veces factorial de 4-- 5 veces 24, ou 120-- e dar ese valor de volta á principal, que ten estaba esperando con moita paciencia para unha longo período de tempo no fondo da pila. 

É onde todo comezou. Fixo esta chamada. Varios cadros asumiu na parte superior. Agora de volta ao principio da pila. É o marco activo. Así principal adquiriuno o valor 120 de volta de factorial de 5. Está á espera de imprimir ese valor. E entón el está feito. Non hai é máis liñas de código en principal. Entón marco da principal aparece fóra a pila, e estamos a facer. 

E así é como funciona a recursividade. Isto é como cadros de pila funciona. Estas chamadas de función que pasou anteriormente son só en pausa, esperando para as chamadas posteriores para rematar, para que poidan chegar a ser o activo enmarcar e rematar o que eles precisan facer. 

Eu son Doug Lloyd. Este é CS50.