1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Si usted ha visto
el vídeo en la recursividad,

3
00:00:07,670 --> 00:00:10,170
todo el proceso podría tener
parecía un poco mágico.

4
00:00:10,170 --> 00:00:10,930
¿Como funciona?

5
00:00:10,930 --> 00:00:15,010
¿Cómo saben las funciones que
que tenga que esperar y esperar a que otro valor

6
00:00:15,010 --> 00:00:19,150
para volver de una función diferente
llamar con el fin de obtener el resultado que queremos?

7
00:00:19,150 --> 00:00:22,550
>> Bueno, la razón de que esto funciona es porque
de algo conocido como la pila de llamadas.

8
00:00:22,550 --> 00:00:26,360
Cuando se llama a una función, el
sistema deja de lado el espacio en memoria

9
00:00:26,360 --> 00:00:28,120
para esa función para hacer su trabajo.

10
00:00:28,120 --> 00:00:31,720
Y llamamos a estos trozos de memoria que
están siendo reservado para cada función

11
00:00:31,720 --> 00:00:35,670
llamar a un marco de pila o un marco de función.

12
00:00:35,670 --> 00:00:38,290
Y como era de esperar,
estos marcos de pila

13
00:00:38,290 --> 00:00:41,000
vivir en la parte pila de memoria.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Más de una función de marco de pila
puede existir en la memoria en un momento dado.

16
00:00:47,540 --> 00:00:51,240
Si llama a un movimiento principal función,
y mover llama dirección,

17
00:00:51,240 --> 00:00:54,460
las tres funciones tienen marcos abiertos.

18
00:00:54,460 --> 00:00:57,350
Pero no todos tienen marcos activos.

19
00:00:57,350 --> 00:00:59,410
Estos marcos están dispuestos en una pila.

20
00:00:59,410 --> 00:01:01,820
Y el marco de la
más recientemente llamada

21
00:01:01,820 --> 00:01:04,390
función es siempre en la parte superior de la pila.

22
00:01:04,390 --> 00:01:07,150
Y eso es siempre el marco activo.

23
00:01:07,150 --> 00:01:10,420
Sólo hay realmente alguna vez un solo
función que es activo a la vez.

24
00:01:10,420 --> 00:01:12,420
Es la única en la parte superior de la pila.

25
00:01:12,420 --> 00:01:17,620
>> Cuando una función llama a otro
función, tipo de prensas de pausa.

26
00:01:17,620 --> 00:01:20,590
De alguna manera está en espera, esperando.

27
00:01:20,590 --> 00:01:24,050
Y es empujado otro marco de pila
en la pila en la parte superior de la misma.

28
00:01:24,050 --> 00:01:26,150
Y eso se convierte en el marco activo.

29
00:01:26,150 --> 00:01:28,600
Y la trama inmediatamente
por debajo de ella tiene que esperar

30
00:01:28,600 --> 00:01:33,560
hasta que sea de nuevo el marco activo
antes de que pueda reanudar su trabajo.

31
00:01:33,560 --> 00:01:35,870
Cuando una función es
completa y se hace,

32
00:01:35,870 --> 00:01:37,720
su marco se extrae de la pila.

33
00:01:37,720 --> 00:01:38,950
Esa es la terminología.

34
00:01:38,950 --> 00:01:41,110
Y la trama inmediatamente
por debajo de ella, como acabo de decir,

35
00:01:41,110 --> 00:01:42,880
se convierte en el nuevo marco activo.

36
00:01:42,880 --> 00:01:45,960
>> Y si se llama a otra función,
que va a hacer una pausa de nuevo.

37
00:01:45,960 --> 00:01:49,290
Marco de pila de esa nueva función
ser empujado sobre la parte superior de la pila.

38
00:01:49,290 --> 00:01:50,650
Se va a hacer su trabajo.

39
00:01:50,650 --> 00:01:52,100
Podría estallar atrás.

40
00:01:52,100 --> 00:01:55,630
Y la otra función
a continuación se puede reanudar de nuevo.

41
00:01:55,630 --> 00:02:00,080
>> Así que vamos a ir a través de este nuevo, mirando
en la idea de la función factorial

42
00:02:00,080 --> 00:02:03,070
que hemos definido en el
vídeo recursividad para ver

43
00:02:03,070 --> 00:02:07,770
exactamente cómo la magia detrás de esto
proceso recursivo está teniendo lugar.

44
00:02:07,770 --> 00:02:09,870
Así que esto es todo nuestro archivo, ¿verdad?

45
00:02:09,870 --> 00:02:14,000
Hemos definido dos
functions-- principal y hecho.

46
00:02:14,000 --> 00:02:15,980
Y como era de esperar,
cualquier programa C se va

47
00:02:15,980 --> 00:02:18,470
comenzar en la primera línea de la principal.

48
00:02:18,470 --> 00:02:21,660
>> Así que creamos un nuevo marco de pila para el principal.

49
00:02:21,660 --> 00:02:23,320
Y que va a empezar a correr.

50
00:02:23,320 --> 00:02:25,270
Llamadas principales printf.

51
00:02:25,270 --> 00:02:29,390
Y printf va a
imprimir factorial de 5.

52
00:02:29,390 --> 00:02:31,440
Bueno, no lo sabe
lo factorial de 5 es,

53
00:02:31,440 --> 00:02:35,620
y así esta convocatoria ya está
dependiendo de otra llamada a la función.

54
00:02:35,620 --> 00:02:37,270
Así principal va a hacer una pausa allí.

55
00:02:37,270 --> 00:02:39,103
Voy a dejar a su
flecha justo ahí, color

56
00:02:39,103 --> 00:02:41,360
que el mismo color que el
apilar marco de la derecha,

57
00:02:41,360 --> 00:02:47,720
para indicar que la principal va a congelar
aquí mientras factorial de 5 se llama.

58
00:02:47,720 --> 00:02:49,300
>> Así factorial de 5 se llama.

59
00:02:49,300 --> 00:02:53,160
Y que va a comenzar en el mismo
a partir de la función factorial.

60
00:02:53,160 --> 00:02:55,440
Se pide a la pregunta estoy igual a 1?

61
00:02:55,440 --> 00:02:56,810
Es 5 igual a 1?

62
00:02:56,810 --> 00:02:57,410
Bueno no.

63
00:02:57,410 --> 00:03:01,110
Así que va a bajar a
la otra parte, el regreso n veces

64
00:03:01,110 --> 00:03:02,990
factorial de n menos 1.

65
00:03:02,990 --> 00:03:03,490
Bien ok.

66
00:03:03,490 --> 00:03:07,070
>> Así que ahora, factorial de 5 es
dependiendo de otra llamada

67
00:03:07,070 --> 00:03:09,740
a factorial, pasando
en 4 como parámetro.

68
00:03:09,740 --> 00:03:14,210
Y así el factorial de
5 marco, que marco rojo,

69
00:03:14,210 --> 00:03:17,160
va a congelar ahí
en esa línea he indicado

70
00:03:17,160 --> 00:03:21,914
y esperar a que factorial de 4 para terminar
lo que tiene que hacer para que entonces

71
00:03:21,914 --> 00:03:23,330
puede convertirse en el marco activo de nuevo.

72
00:03:23,330 --> 00:03:26,890
>> Así factorial de 4 comienza en
el comienzo de factorial.

73
00:03:26,890 --> 00:03:28,556
Es 4 igual a 1?

74
00:03:28,556 --> 00:03:30,180
No, por lo que va a hacer lo mismo.

75
00:03:30,180 --> 00:03:31,590
Se va a ir por la rama más.

76
00:03:31,590 --> 00:03:33,240
Va a llegar a esa línea de código.

77
00:03:33,240 --> 00:03:35,710
OK, voy a devolver cuatro veces.

78
00:03:35,710 --> 00:03:41,270
Oh, factorial de 3-- tan factorial de
4 depende de factorial de 3 de acabado.

79
00:03:41,270 --> 00:03:43,055
>> Y por lo que debe llamar factorial de 3.

80
00:03:43,055 --> 00:03:45,180
Y eso va a ir a través de
el mismo proceso de nuevo.

81
00:03:45,180 --> 00:03:48,200
Comienza a través, llegue aquí.

82
00:03:48,200 --> 00:03:50,980
Factorial de 3 depende
en factorial de 1.

83
00:03:50,980 --> 00:03:53,750
Así factorial de 2 comienza, llega aquí.

84
00:03:53,750 --> 00:03:56,310
Depende de factorial de 1.

85
00:03:56,310 --> 00:03:57,430
Factorial de 1 comienza.

86
00:03:57,430 --> 00:03:57,650
>> OK.

87
00:03:57,650 --> 00:03:59,775
Así que ahora, que estamos recibiendo
en algún lugar interesante, ¿verdad?

88
00:03:59,775 --> 00:04:02,190
Así que ahora, 1 es igual a 1.

89
00:04:02,190 --> 00:04:05,130
Y así volvemos 1.

90
00:04:05,130 --> 00:04:06,770
En este punto, estamos volviendo.

91
00:04:06,770 --> 00:04:07,880
La función está hecho.

92
00:04:07,880 --> 00:04:11,140
Es un comportamiento es-- hay
nada más para que lo haga,

93
00:04:11,140 --> 00:04:17,006
por lo que el marco de pila para
factorial de 1 se dispara.

94
00:04:17,006 --> 00:04:17,589
Está terminado.

95
00:04:17,589 --> 00:04:19,480
Volvió 1.

96
00:04:19,480 --> 00:04:23,370
Y ahora, factorial de 2, que
fue el marco inmediatamente inferior

97
00:04:23,370 --> 00:04:26,160
en la pila, se convierte en el marco activo.

98
00:04:26,160 --> 00:04:29,030
>> Y puede recoger
exactamente donde lo dejó.

99
00:04:29,030 --> 00:04:32,240
Ha estado esperando un factorial
de 1 para terminar su trabajo.

100
00:04:32,240 --> 00:04:33,610
Ahora se ha terminado.

101
00:04:33,610 --> 00:04:35,510
Y aquí estamos.

102
00:04:35,510 --> 00:04:38,080
>> Factorial de 1 devuelve un valor de 1.

103
00:04:38,080 --> 00:04:42,430
Así factorial de 2 lata
digamos volver 2 veces 1.

104
00:04:42,430 --> 00:04:43,680
Su obra se hace ahora.

105
00:04:43,680 --> 00:04:49,110
Se volvió a 2 factorial
de 3, que se espera de él.

106
00:04:49,110 --> 00:04:53,370
Factorial de 3 es ahora el marco superior,
el marco activo en la pila.

107
00:04:53,370 --> 00:04:58,617
Y por lo que dice, bien, bien, voy
volver 3 veces 2, que es 6.

108
00:04:58,617 --> 00:05:00,700
Y yo voy a dar esa
valorar de nuevo a factorial

109
00:05:00,700 --> 00:05:03,430
de 4, que ha estado esperando por mí.

110
00:05:03,430 --> 00:05:04,500
He terminado.

111
00:05:04,500 --> 00:05:09,410
Factorial de 3 aparece de la pila, y
factorial de 4 es ahora el marco activo.

112
00:05:09,410 --> 00:05:13,510
>> 4 dice: OK, voy a volver 4 veces
el factorial de 3, que tenía seis años.

113
00:05:13,510 --> 00:05:15,980
Eso era de valor que
factorial de 3 regresó.

114
00:05:15,980 --> 00:05:19,010
Y así 4 veces 6 es 24.

115
00:05:19,010 --> 00:05:20,990
Y yo voy a pasar
que volver a factorial

116
00:05:20,990 --> 00:05:23,160
de 5, que ha estado esperando por mí.

117
00:05:23,160 --> 00:05:25,270
Factorial de 5 es ahora el marco activo.

118
00:05:25,270 --> 00:05:30,700
Se va a volver 5 veces
factorial de 4-- 5 veces 24 o 120--

119
00:05:30,700 --> 00:05:32,722
y dar a ese valor
volver al principal, que tiene

120
00:05:32,722 --> 00:05:35,680
estado esperando pacientemente para una
mucho tiempo en la parte inferior de la pila.

121
00:05:35,680 --> 00:05:36,640
>> Es el lugar donde se inició.

122
00:05:36,640 --> 00:05:37,670
Se hizo esta llamada.

123
00:05:37,670 --> 00:05:39,400
Varios cuadros se hicieron cargo de la parte superior.

124
00:05:39,400 --> 00:05:41,890
Ahora está de vuelta en la parte superior de la pila.

125
00:05:41,890 --> 00:05:43,450
Es el marco activo.

126
00:05:43,450 --> 00:05:47,810
Así principal tiene el valor 120
de vuelta de factorial de 5.

127
00:05:47,810 --> 00:05:50,750
Ha estado esperando para
imprimir ese valor.

128
00:05:50,750 --> 00:05:51,657
Y luego se hace.

129
00:05:51,657 --> 00:05:53,240
No hay más líneas de código en principal.

130
00:05:53,240 --> 00:05:56,800
Así marco del principal se dispara
la pila, y hemos terminado.

131
00:05:56,800 --> 00:05:58,992
>> Y así es como funciona la recursividad.

132
00:05:58,992 --> 00:06:00,200
Así es como marcos de pila funcionan.

133
00:06:00,200 --> 00:06:03,120
Esas llamadas a funciones
eso sucedió anteriormente

134
00:06:03,120 --> 00:06:06,620
son sólo en pausa, a la espera
para las llamadas posteriores

135
00:06:06,620 --> 00:06:12,050
para terminar, para que puedan convertirse en el activo
enmarcan y terminar lo que tienen que hacer.

136
00:06:12,050 --> 00:06:13,060
>> Soy Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Esto es CS50.

138
00:06:14,880 --> 00:06:16,580