DOUG LLOYD: Si usted ha visto el vídeo en la recursividad,
todo el proceso podría tener parecía un poco mágico.
¿Como funciona?
¿Cómo saben las funciones que que tenga que esperar y esperar a que otro valor
para volver de una función diferente llamar con el fin de obtener el resultado que queremos?
>> Bueno, la razón de que esto funciona es porque de algo conocido como la pila de llamadas.
Cuando se llama a una función, el sistema deja de lado el espacio en memoria
para esa función para hacer su trabajo.
Y llamamos a estos trozos de memoria que están siendo reservado para cada función
llamar a un marco de pila o un marco de función.
Y como era de esperar, estos marcos de pila
vivir en la parte pila de memoria.
>> Más de una función de marco de pila puede existir en la memoria en un momento dado.
Si llama a un movimiento principal función, y mover llama dirección,
las tres funciones tienen marcos abiertos.
Pero no todos tienen marcos activos.
Estos marcos están dispuestos en una pila.
Y el marco de la más recientemente llamada
función es siempre en la parte superior de la pila.
Y eso es siempre el marco activo.
Sólo hay realmente alguna vez un solo función que es activo a la vez.
Es la única en la parte superior de la pila.
>> Cuando una función llama a otro función, tipo de prensas de pausa.
De alguna manera está en espera, esperando.
Y es empujado otro marco de pila en la pila en la parte superior de la misma.
Y eso se convierte en el marco activo.
Y la trama inmediatamente por debajo de ella tiene que esperar
hasta que sea de nuevo el marco activo antes de que pueda reanudar su trabajo.
Cuando una función es completa y se hace,
su marco se extrae de la pila.
Esa es la terminología.
Y la trama inmediatamente por debajo de ella, como acabo de decir,
se convierte en el nuevo marco activo.
>> Y si se llama a otra función, que va a hacer una pausa de nuevo.
Marco de pila de esa nueva función ser empujado sobre la parte superior de la pila.
Se va a hacer su trabajo.
Podría estallar atrás.
Y la otra función a continuación se puede reanudar de nuevo.
>> Así que vamos a ir a través de este nuevo, mirando en la idea de la función factorial
que hemos definido en el vídeo recursividad para ver
exactamente cómo la magia detrás de esto proceso recursivo está teniendo lugar.
Así que esto es todo nuestro archivo, ¿verdad?
Hemos definido dos functions-- principal y hecho.
Y como era de esperar, cualquier programa C se va
comenzar en la primera línea de la principal.
>> Así que creamos un nuevo marco de pila para el principal.
Y que va a empezar a correr.
Llamadas principales printf.
Y printf va a imprimir factorial de 5.
Bueno, no lo sabe lo factorial de 5 es,
y así esta convocatoria ya está dependiendo de otra llamada a la función.
Así principal va a hacer una pausa allí.
Voy a dejar a su flecha justo ahí, color
que el mismo color que el apilar marco de la derecha,
para indicar que la principal va a congelar aquí mientras factorial de 5 se llama.
>> Así factorial de 5 se llama.
Y que va a comenzar en el mismo a partir de la función factorial.
Se pide a la pregunta estoy igual a 1?
Es 5 igual a 1?
Bueno no.
Así que va a bajar a la otra parte, el regreso n veces
factorial de n menos 1.
Bien ok.
>> Así que ahora, factorial de 5 es dependiendo de otra llamada
a factorial, pasando en 4 como parámetro.
Y así el factorial de 5 marco, que marco rojo,
va a congelar ahí en esa línea he indicado
y esperar a que factorial de 4 para terminar lo que tiene que hacer para que entonces
puede convertirse en el marco activo de nuevo.
>> Así factorial de 4 comienza en el comienzo de factorial.
Es 4 igual a 1?
No, por lo que va a hacer lo mismo.
Se va a ir por la rama más.
Va a llegar a esa línea de código.
OK, voy a devolver cuatro veces.
Oh, factorial de 3-- tan factorial de 4 depende de factorial de 3 de acabado.
>> Y por lo que debe llamar factorial de 3.
Y eso va a ir a través de el mismo proceso de nuevo.
Comienza a través, llegue aquí.
Factorial de 3 depende en factorial de 1.
Así factorial de 2 comienza, llega aquí.
Depende de factorial de 1.
Factorial de 1 comienza.
>> OK.
Así que ahora, que estamos recibiendo en algún lugar interesante, ¿verdad?
Así que ahora, 1 es igual a 1.
Y así volvemos 1.
En este punto, estamos volviendo.
La función está hecho.
Es un comportamiento es-- hay nada más para que lo haga,
por lo que el marco de pila para factorial de 1 se dispara.
Está terminado.
Volvió 1.
Y ahora, factorial de 2, que fue el marco inmediatamente inferior
en la pila, se convierte en el marco activo.
>> Y puede recoger exactamente donde lo dejó.
Ha estado esperando un factorial de 1 para terminar su trabajo.
Ahora se ha terminado.
Y aquí estamos.
>> Factorial de 1 devuelve un valor de 1.
Así factorial de 2 lata digamos volver 2 veces 1.
Su obra se hace ahora.
Se volvió a 2 factorial de 3, que se espera de él.
Factorial de 3 es ahora el marco superior, el marco activo en la pila.
Y por lo que dice, bien, bien, voy volver 3 veces 2, que es 6.
Y yo voy a dar esa valorar de nuevo a factorial
de 4, que ha estado esperando por mí.
He terminado.
Factorial de 3 aparece de la pila, y factorial de 4 es ahora el marco activo.
>> 4 dice: OK, voy a volver 4 veces el factorial de 3, que tenía seis años.
Eso era de valor que factorial de 3 regresó.
Y así 4 veces 6 es 24.
Y yo voy a pasar que volver a factorial
de 5, que ha estado esperando por mí.
Factorial de 5 es ahora el marco activo.
Se va a volver 5 veces factorial de 4-- 5 veces 24 o 120--
y dar a ese valor volver al principal, que tiene
estado esperando pacientemente para una mucho tiempo en la parte inferior de la pila.
>> Es el lugar donde se inició.
Se hizo esta llamada.
Varios cuadros se hicieron cargo de la parte superior.
Ahora está de vuelta en la parte superior de la pila.
Es el marco activo.
Así principal tiene el valor 120 de vuelta de factorial de 5.
Ha estado esperando para imprimir ese valor.
Y luego se hace.
No hay más líneas de código en principal.
Así marco del principal se dispara la pila, y hemos terminado.
>> Y así es como funciona la recursividad.
Así es como marcos de pila funcionan.
Esas llamadas a funciones eso sucedió anteriormente
son sólo en pausa, a la espera para las llamadas posteriores
para terminar, para que puedan convertirse en el activo enmarcan y terminar lo que tienen que hacer.
>> Soy Doug Lloyd.
Esto es CS50.