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

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Se xa viu
o vídeo en recursão,

3
00:00:07,670 --> 00:00:10,170
todo o proceso pode ter
parecía un pouco máxico.

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

5
00:00:10,930 --> 00:00:15,010
Como as funcións de saber que
necesitamos esperar e esperar por outro valor

6
00:00:15,010 --> 00:00:19,150
para volver dunha función diferente
chamar a fin de obter o resultado que queremos?

7
00:00:19,150 --> 00:00:22,550
>> Ben, a razón é porque funciona
de algo coñecido como a pila de chamadas.

8
00:00:22,550 --> 00:00:26,360
Cando chamar unha función, o
sistema deixa de lado o espazo na memoria

9
00:00:26,360 --> 00:00:28,120
para esa función para facer o seu traballo.

10
00:00:28,120 --> 00:00:31,720
E chamamos eses bloques de memoria que
están sendo retiradas para cada función

11
00:00:31,720 --> 00:00:35,670
chamar un cadro de pila ou marcos función.

12
00:00:35,670 --> 00:00:38,290
E como podería esperar,
estes cadros de pila

13
00:00:38,290 --> 00:00:41,000
viven na parte pila de memoria.

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

15
00:00:43,960 --> 00:00:47,540
>> Máis que unha función de cadro de pila
poden existir en memoria nun momento dado.

16
00:00:47,540 --> 00:00:51,240
Se principal chama un movemento función,
e chama movemento dirección,

17
00:00:51,240 --> 00:00:54,460
as tres funcións teñen cadros abertos.

18
00:00:54,460 --> 00:00:57,350
Pero eles non teñen cadros activos.

19
00:00:57,350 --> 00:00:59,410
Estes cadros son dispostas nunha pila.

20
00:00:59,410 --> 00:01:01,820
E o cadro do
máis recentemente chamado

21
00:01:01,820 --> 00:01:04,390
función é sempre na parte superior do conxunto.

22
00:01:04,390 --> 00:01:07,150
E iso é sempre o cadro activo.

23
00:01:07,150 --> 00:01:10,420
Só hai realmente sempre unha
función que é activo en un tempo.

24
00:01:10,420 --> 00:01:12,420
É un na parte superior do conxunto.

25
00:01:12,420 --> 00:01:17,620
>> Cando unha función chama outra
función, el presiona tipo de pausa.

26
00:01:17,620 --> 00:01:20,590
É unha especie de está esperando, esperando.

27
00:01:20,590 --> 00:01:24,050
E outro cadro de pila é empurrado
para a pila enriba dela.

28
00:01:24,050 --> 00:01:26,150
E iso se fai o cadro activo.

29
00:01:26,150 --> 00:01:28,600
E o cadro inmediatamente
debaixo del necesita esperar

30
00:01:28,600 --> 00:01:33,560
ata que sexa de novo o cadro activo
antes de que poida retomar o seu traballo.

31
00:01:33,560 --> 00:01:35,870
Cando unha función é
completo e está feito,

32
00:01:35,870 --> 00:01:37,720
seu cadro é eliminado da pila.

33
00:01:37,720 --> 00:01:38,950
Esa é a terminoloxía.

34
00:01:38,950 --> 00:01:41,110
E o cadro inmediatamente
debaixo del, como acabo de dicir,

35
00:01:41,110 --> 00:01:42,880
pasa a ser o novo marco activo.

36
00:01:42,880 --> 00:01:45,960
>> E se chama outra función,
vai deixar de novo.

37
00:01:45,960 --> 00:01:49,290
Pila cadro que nova función será
ser empuxada para arriba da pila.

38
00:01:49,290 --> 00:01:50,650
Vai facer o seu traballo.

39
00:01:50,650 --> 00:01:52,100
Pode aparecer de novo fóra.

40
00:01:52,100 --> 00:01:55,630
E a outra función
debaixo del pode retomar de novo.

41
00:01:55,630 --> 00:02:00,080
>> Entón, imos pasar por iso de novo, ollando
coa idea da función factorial

42
00:02:00,080 --> 00:02:03,070
que define na
video recursão para ver

43
00:02:03,070 --> 00:02:07,770
exactamente como a maxia detrás diso
proceso recursivo se produciron.

44
00:02:07,770 --> 00:02:09,870
Polo tanto, este é todo o noso arquivo, non?

45
00:02:09,870 --> 00:02:14,000
Definimos dous
funcións no inicio e feito.

46
00:02:14,000 --> 00:02:15,980
E, como era de esperar,
calquera programa C vai

47
00:02:15,980 --> 00:02:18,470
para comezar na primeira liña do principal.

48
00:02:18,470 --> 00:02:21,660
>> Entón, creamos un novo marco de pila para o inicio.

49
00:02:21,660 --> 00:02:23,320
E vai a comezar a carreira.

50
00:02:23,320 --> 00:02:25,270
Principais chamadas printf.

51
00:02:25,270 --> 00:02:29,390
E printf vai
imprimir factorial de 5.

52
00:02:29,390 --> 00:02:31,440
Ben, el non sabe
o factorial de 5 é,

53
00:02:31,440 --> 00:02:35,620
e por iso esta chamada xa é
dependendo de outra chamada de función.

54
00:02:35,620 --> 00:02:37,270
Así principal vai parar aí.

55
00:02:37,270 --> 00:02:39,103
Vou deixar o seu
frecha para a dereita alí, cor

56
00:02:39,103 --> 00:02:41,360
que a mesma cor que o
apilar cadro á dereita,

57
00:02:41,360 --> 00:02:47,720
para indicar que o principal vai conxelar
aquí mentres factorial de 5 chámase.

58
00:02:47,720 --> 00:02:49,300
>> Entón factorial de 5 chámase.

59
00:02:49,300 --> 00:02:53,160
E que vai comezar no
inicio da función factorial.

60
00:02:53,160 --> 00:02:55,440
Fai a pregunta que eu estou igual a 1?

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

62
00:02:56,810 --> 00:02:57,410
Ben, non.

63
00:02:57,410 --> 00:03:01,110
Entón, que vai baixar para
a outra parte, o retorno 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
Ben, OK.

66
00:03:03,490 --> 00:03:07,070
>> Entón, agora, factorial de 5 é
dependendo outra chamada

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

68
00:03:09,740 --> 00:03:14,210
E así o factorial de
5 cadro, que marco vermella,

69
00:03:14,210 --> 00:03:17,160
vai conxelar alí
en que a liña eu indiquei

70
00:03:17,160 --> 00:03:21,914
e esperar por factorial de 4 para rematar
o que cómpre facer para que, a continuación,

71
00:03:21,914 --> 00:03:23,330
pode facer o cadro activo de novo.

72
00:03:23,330 --> 00:03:26,890
>> Entón factorial de 4 comeza en
o inicio da factorial.

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

74
00:03:28,556 --> 00:03:30,180
Non, polo que vai facer o mesmo.

75
00:03:30,180 --> 00:03:31,590
Vai descender a rama máis.

76
00:03:31,590 --> 00:03:33,240
Chegará a esta liña de código.

77
00:03:33,240 --> 00:03:35,710
OK, eu vou devolver catro veces.

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

79
00:03:41,270 --> 00:03:43,055
>> E por iso que chamar factorial 3.

80
00:03:43,055 --> 00:03:45,180
E iso vai pasar por
o mesmo proceso unha vez máis.

81
00:03:45,180 --> 00:03:48,200
Comeza a pasar, queda 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
Entón factorial de 2 comeza, queda aquí.

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

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

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

87
00:03:57,650 --> 00:03:59,775
Entón, agora, estamos chegando
nalgún lugar interesante, non?

88
00:03:59,775 --> 00:04:02,190
Entón agora, 1 é igual a 1.

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

90
00:04:05,130 --> 00:04:06,770
Neste momento, estamos a volver.

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

92
00:04:07,880 --> 00:04:11,140
É un comportamento é-- hai
nada máis para el facer,

93
00:04:11,140 --> 00:04:17,006
e así o cadro de pila para
factorial de 1 aparece fóra.

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

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

96
00:04:19,480 --> 00:04:23,370
E agora, factorial de 2, que
foi a trama debaixo dela

97
00:04:23,370 --> 00:04:26,160
na pila, se fai o cadro activo.

98
00:04:26,160 --> 00:04:29,030
>> E pode incorporarse
exactamente de onde parou.

99
00:04:29,030 --> 00:04:32,240
Está esperando por un factorial
de 1 para rematar o seu traballo.

100
00:04:32,240 --> 00:04:33,610
El xa rematou.

101
00:04:33,610 --> 00:04:35,510
E entón aquí estamos.

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

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

104
00:04:42,430 --> 00:04:43,680
O seu traballo xa está feito.

105
00:04:43,680 --> 00:04:49,110
Devólvese 2 a factorial
de 3, que estaba esperando por el.

106
00:04:49,110 --> 00:04:53,370
Factorial de 3 agora cadro superior,
o marco activo na pila.

107
00:04:53,370 --> 00:04:58,617
E así se di, OK, ben, eu vou
para volver 3 veces 2, que é 6.

108
00:04:58,617 --> 00:05:00,700
E eu vou dar que
valor ao factorial

109
00:05:00,700 --> 00:05:03,430
4, que foi esperando por min.

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

111
00:05:04,500 --> 00:05:09,410
Factorial de 3 aparece fóra da pila, e
factorial de 4 é agora o cadro activo.

112
00:05:09,410 --> 00:05:13,510
>> 4 di: OK, eu vou volver 4 veces
o factorial de 3, que tiña seis anos.

113
00:05:13,510 --> 00:05:15,980
Iso era de valor que
factorial de 3 devolto.

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

115
00:05:19,010 --> 00:05:20,990
E eu vou pasar
que volve á factorial

116
00:05:20,990 --> 00:05:23,160
de 5, que foi esperando por min.

117
00:05:23,160 --> 00:05:25,270
Factorial de 5 é agora o cadro activo.

118
00:05:25,270 --> 00:05:30,700
Volverá 5 veces
factorial de 4-- 5 veces 24, ou 120--

119
00:05:30,700 --> 00:05:32,722
e dar ese valor
de volta á principal, que ten

120
00:05:32,722 --> 00:05:35,680
estaba esperando con moita paciencia para unha
longo período de tempo no fondo da pila.

121
00:05:35,680 --> 00:05:36,640
>> É onde todo comezou.

122
00:05:36,640 --> 00:05:37,670
Fixo esta chamada.

123
00:05:37,670 --> 00:05:39,400
Varios cadros asumiu na parte superior.

124
00:05:39,400 --> 00:05:41,890
Agora de volta ao principio da pila.

125
00:05:41,890 --> 00:05:43,450
É o marco activo.

126
00:05:43,450 --> 00:05:47,810
Así principal adquiriuno o valor 120
de volta de factorial de 5.

127
00:05:47,810 --> 00:05:50,750
Está á espera de
imprimir ese valor.

128
00:05:50,750 --> 00:05:51,657
E entón el está feito.

129
00:05:51,657 --> 00:05:53,240
Non hai é máis liñas de código en principal.

130
00:05:53,240 --> 00:05:56,800
Entón marco da principal aparece fóra
a pila, e estamos a facer.

131
00:05:56,800 --> 00:05:58,992
>> E así é como funciona a recursividade.

132
00:05:58,992 --> 00:06:00,200
Isto é como cadros de pila funciona.

133
00:06:00,200 --> 00:06:03,120
Estas chamadas de función
que pasou anteriormente

134
00:06:03,120 --> 00:06:06,620
son só en pausa, esperando
para as chamadas posteriores

135
00:06:06,620 --> 00:06:12,050
para rematar, para que poidan chegar a ser o activo
enmarcar e rematar o que eles precisan facer.

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

137
00:06:13,060 --> 00:06:14,880
Este é CS50.

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