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.