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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Si vostè ha vist
el vídeo a la recursivitat,

3
00:00:07,670 --> 00:00:10,170
tot el procés podria tenir
semblava una mica màgic.

4
00:00:10,170 --> 00:00:10,930
Com funciona?

5
00:00:10,930 --> 00:00:15,010
Com saben les funcions que
que hagi d'esperar i esperar que un altre valor

6
00:00:15,010 --> 00:00:19,150
per tornar d'una funció diferent
cridar per tal d'obtenir el resultat que volem?

7
00:00:19,150 --> 00:00:22,550
>> Bé, la raó que això funciona és perquè
d'alguna cosa conegut com la pila de trucades.

8
00:00:22,550 --> 00:00:26,360
Quan es crida a una funció, el
sistema deixa de banda l'espai en memòria

9
00:00:26,360 --> 00:00:28,120
per a aquesta funció per funcionar.

10
00:00:28,120 --> 00:00:31,720
I cridem a aquests trossos de memòria que
estan sent reservat per a cada funció

11
00:00:31,720 --> 00:00:35,670
trucar a un marc de pila o un marc de funció.

12
00:00:35,670 --> 00:00:38,290
I com era d'esperar,
aquests marcs de pila

13
00:00:38,290 --> 00:00:41,000
viure a la part pila de memòria.

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

15
00:00:43,960 --> 00:00:47,540
>> Més d'una funció de marc de pila
pot existir en la memòria en un moment donat.

16
00:00:47,540 --> 00:00:51,240
Si crida a un moviment principal funció,
i moure crida direcció,

17
00:00:51,240 --> 00:00:54,460
les tres funcions tenen marcs oberts.

18
00:00:54,460 --> 00:00:57,350
Però no tots tenen marcs actius.

19
00:00:57,350 --> 00:00:59,410
Aquests marcs estan disposats en una pila.

20
00:00:59,410 --> 00:01:01,820
I el marc de la
més recentment anomenada

21
00:01:01,820 --> 00:01:04,390
funció és sempre a la part superior de la pila.

22
00:01:04,390 --> 00:01:07,150
I això és sempre el marc actiu.

23
00:01:07,150 --> 00:01:10,420
Només hi ha realment alguna vegada un sol
funció que és actiu alhora.

24
00:01:10,420 --> 00:01:12,420
És l'única en la part superior de la pila.

25
00:01:12,420 --> 00:01:17,620
>> Quan una funció crida a un altre
funció, tipus de premses de pausa.

26
00:01:17,620 --> 00:01:20,590
D'alguna manera està en espera, esperant.

27
00:01:20,590 --> 00:01:24,050
I és empès un altre marc de pila
a la pila a la part superior de la mateixa.

28
00:01:24,050 --> 00:01:26,150
I això es converteix en el marc actiu.

29
00:01:26,150 --> 00:01:28,600
I la trama immediatament
per sota d'ella ha d'esperar

30
00:01:28,600 --> 00:01:33,560
fins que sigui de nou el marc actiu
abans que pugui reprendre el seu treball.

31
00:01:33,560 --> 00:01:35,870
Quan una funció és
completa i es fa,

32
00:01:35,870 --> 00:01:37,720
el seu marc s'extreu de la pila.

33
00:01:37,720 --> 00:01:38,950
Aquesta és la terminologia.

34
00:01:38,950 --> 00:01:41,110
I la trama immediatament
per sota d'ella, com acabo de dir,

35
00:01:41,110 --> 00:01:42,880
es converteix en el nou marc actiu.

36
00:01:42,880 --> 00:01:45,960
>> I si es diu a una altra funció,
que va a fer una pausa de nou.

37
00:01:45,960 --> 00:01:49,290
Marc de pila d'aquesta nova funció
ser empès sobre la part superior de la pila.

38
00:01:49,290 --> 00:01:50,650
Es va a fer la seva feina.

39
00:01:50,650 --> 00:01:52,100
Podria esclatar enrere.

40
00:01:52,100 --> 00:01:55,630
I l'altra funció
a continuació es pot reprendre de nou.

41
00:01:55,630 --> 00:02:00,080
>> Així que anem a anar a través d'aquest nou, mirant
en la idea de la funció factorial

42
00:02:00,080 --> 00:02:03,070
que hem definit en el
vídeo recursivitat per veure

43
00:02:03,070 --> 00:02:07,770
exactament com la màgia darrere d'això
procés recursiu està tenint lloc.

44
00:02:07,770 --> 00:02:09,870
Així que això és tot el nostre arxiu, oi?

45
00:02:09,870 --> 00:02:14,000
Hem definit dos
functions-- principal i fet.

46
00:02:14,000 --> 00:02:15,980
I com era d'esperar,
qualsevol programa C es va

47
00:02:15,980 --> 00:02:18,470
començar en la primera línia de la principal.

48
00:02:18,470 --> 00:02:21,660
>> Així que vam crear un nou marc de pila per al principal.

49
00:02:21,660 --> 00:02:23,320
I que va a començar a córrer.

50
00:02:23,320 --> 00:02:25,270
Trucades principals printf.

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

52
00:02:29,390 --> 00:02:31,440
Bé, no ho sap
el factorial de 5 és,

53
00:02:31,440 --> 00:02:35,620
i així aquesta convocatòria ja està
depenent d'una altra crida a la funció.

54
00:02:35,620 --> 00:02:37,270
Així principal va a fer una pausa allà.

55
00:02:37,270 --> 00:02:39,103
Vaig a deixar al seu
fletxa just aquí, color

56
00:02:39,103 --> 00:02:41,360
que el mateix color que el
apilar marc de la dreta,

57
00:02:41,360 --> 00:02:47,720
per indicar que la principal va congelar
aquí mentre factorial de 5 es diu.

58
00:02:47,720 --> 00:02:49,300
>> Així factorial de 5 es diu.

59
00:02:49,300 --> 00:02:53,160
I que va començar en el mateix
a partir de la funció factorial.

60
00:02:53,160 --> 00:02:55,440
Es demana a la pregunta estic igual a 1?

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

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

63
00:02:57,410 --> 00:03:01,110
Així que baixarà a
l'altra banda, el retorn n vegades

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

65
00:03:02,990 --> 00:03:03,490
Bé, està bé.

66
00:03:03,490 --> 00:03:07,070
>> Així que ara, factorial de 5 és
depenent d'una altra anomenada

67
00:03:07,070 --> 00:03:09,740
a factorial, passant
en 4 com a paràmetre.

68
00:03:09,740 --> 00:03:14,210
I així el factorial d'
5 marc, que marc vermell,

69
00:03:14,210 --> 00:03:17,160
va congelar aquí
en aquesta línia he indicat

70
00:03:17,160 --> 00:03:21,914
i esperar que factorial de 4 per acabar
el que ha de fer perquè llavors

71
00:03:21,914 --> 00:03:23,330
pot convertir-se en el marc actiu de nou.

72
00:03:23,330 --> 00:03:26,890
>> Així factorial de 4 comença a
el començament 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, per la qual cosa va a fer el mateix.

75
00:03:30,180 --> 00:03:31,590
Es va a anar per la branca més.

76
00:03:31,590 --> 00:03:33,240
Va a arribar a aquesta línia de codi.

77
00:03:33,240 --> 00:03:35,710
OK, vaig a tornar quatre vegades.

78
00:03:35,710 --> 00:03:41,270
Oh, factorial de 3-- tan factorial de
4 depèn de factorial de 3 d'acabat.

79
00:03:41,270 --> 00:03:43,055
>> I pel que ha de trucar factorial de 3.

80
00:03:43,055 --> 00:03:45,180
I això va a anar a través de
el mateix procés de nou.

81
00:03:45,180 --> 00:03:48,200
Comença a través, arribi aquí.

82
00:03:48,200 --> 00:03:50,980
Factorial de 3 depèn
en factorial d'1.

83
00:03:50,980 --> 00:03:53,750
Així factorial de 2 comença, arriba aquí.

84
00:03:53,750 --> 00:03:56,310
Depèn de factorial d'1.

85
00:03:56,310 --> 00:03:57,430
Factorial d'1 comença.

86
00:03:57,430 --> 00:03:57,650
>> D'ACORD.

87
00:03:57,650 --> 00:03:59,775
Així que ara, que estem rebent
en algun lloc interessant, oi?

88
00:03:59,775 --> 00:04:02,190
Així que ara, 1 és igual a 1.

89
00:04:02,190 --> 00:04:05,130
I així tornem gener.

90
00:04:05,130 --> 00:04:06,770
En aquest punt, estem tornant.

91
00:04:06,770 --> 00:04:07,880
La funció està fet.

92
00:04:07,880 --> 00:04:11,140
És un comportament és-- hi
res més perquè ho faci,

93
00:04:11,140 --> 00:04:17,006
per la qual cosa el marc de pila per
factorial d'1 es dispara.

94
00:04:17,006 --> 00:04:17,589
S'ha acabat.

95
00:04:17,589 --> 00:04:19,480
Va tornar gener.

96
00:04:19,480 --> 00:04:23,370
I ara, factorial de 2, que
va ser el marc immediatament inferior

97
00:04:23,370 --> 00:04:26,160
a la pila, es converteix en el marc actiu.

98
00:04:26,160 --> 00:04:29,030
>> I pot recollir
exactament on ho va deixar.

99
00:04:29,030 --> 00:04:32,240
Ha estat esperant un factorial
d'1 per acabar la seva feina.

100
00:04:32,240 --> 00:04:33,610
Ara s'ha acabat.

101
00:04:33,610 --> 00:04:35,510
I aquí estem.

102
00:04:35,510 --> 00:04:38,080
>> Factorial d'1 retorna un valor d'1.

103
00:04:38,080 --> 00:04:42,430
Així factorial de 2 llauna
diguem tornar 2 vegades 1.

104
00:04:42,430 --> 00:04:43,680
La seva obra es fa ara.

105
00:04:43,680 --> 00:04:49,110
Es va tornar a 2 factorial
de 3, que s'espera d'ell.

106
00:04:49,110 --> 00:04:53,370
Factorial de 3 és ara el marc superior,
el marc actiu a la pila.

107
00:04:53,370 --> 00:04:58,617
I pel que diu, bé, bé, vaig
tornar 3 vegades 2, que és 6.

108
00:04:58,617 --> 00:05:00,700
I jo vaig a donar aquesta
valorar de nou a factorial

109
00:05:00,700 --> 00:05:03,430
de 4, que ha estat esperant per mi.

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

111
00:05:04,500 --> 00:05:09,410
Factorial de 3 apareix de la pila, i
factorial de 4 és ara el marc actiu.

112
00:05:09,410 --> 00:05:13,510
>> 4 diu: OK, vaig a tornar 4 vegades
el factorial de 3, que tenia sis anys.

113
00:05:13,510 --> 00:05:15,980
Això era de valor que
factorial de 3 va tornar.

114
00:05:15,980 --> 00:05:19,010
I així 4 vegades 6 és 24.

115
00:05:19,010 --> 00:05:20,990
I jo vaig a passar
de tornar a factorial

116
00:05:20,990 --> 00:05:23,160
de 5, que ha estat esperant per mi.

117
00:05:23,160 --> 00:05:25,270
Factorial de 5 és ara el marc actiu.

118
00:05:25,270 --> 00:05:30,700
Es va a tornar 5 vegades
factorial de 4-- 5 vegades 24 o 120--

119
00:05:30,700 --> 00:05:32,722
i donar a aquest valor
tornar al principal, que té

120
00:05:32,722 --> 00:05:35,680
estat esperant pacientment per a una
molt de temps a la part inferior de la pila.

121
00:05:35,680 --> 00:05:36,640
>> És el lloc on es va iniciar.

122
00:05:36,640 --> 00:05:37,670
Es va fer aquesta crida.

123
00:05:37,670 --> 00:05:39,400
Diversos quadres es van fer càrrec de la part superior.

124
00:05:39,400 --> 00:05:41,890
Ara està de tornada a la part superior de la pila.

125
00:05:41,890 --> 00:05:43,450
És el marc actiu.

126
00:05:43,450 --> 00:05:47,810
Així principal té el valor 120
de tornada de factorial de 5.

127
00:05:47,810 --> 00:05:50,750
Ha estat esperant per
imprimir aquest valor.

128
00:05:50,750 --> 00:05:51,657
I després es fa.

129
00:05:51,657 --> 00:05:53,240
No hi ha més línies de codi en principal.

130
00:05:53,240 --> 00:05:56,800
Així marc del principal es dispara
la pila, i hem acabat.

131
00:05:56,800 --> 00:05:58,992
>> I així és com funciona la recursivitat.

132
00:05:58,992 --> 00:06:00,200
Així és com marcs de pila funcionen.

133
00:06:00,200 --> 00:06:03,120
Aquestes crides a funcions
això va succeir anteriorment

134
00:06:03,120 --> 00:06:06,620
són només en pausa, a l'espera
per a les trucades posteriors

135
00:06:06,620 --> 00:06:12,050
per acabar, perquè puguin convertir-se en l'actiu
emmarquen i acabar el que han de fer.

136
00:06:12,050 --> 00:06:13,060
>> Sóc Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Això és CS50.

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