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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Se vi vidis
la video sur rekursio,

3
00:00:07,670 --> 00:00:10,170
la tuta procezo havu
ŝajnis iomete magia.

4
00:00:10,170 --> 00:00:10,930
Kiel ĝi funkcias?

5
00:00:10,930 --> 00:00:15,010
Kiel la funkcioj scias ke ili
bezonas atendi kaj atendi alian valoron

6
00:00:15,010 --> 00:00:19,150
reveni de malsama funkcio
voki por akiri la rezulton ni deziras?

7
00:00:19,150 --> 00:00:22,550
>> Nu, la kialo estas ĉar ĉi verkoj
de io konata kiel la alvoko pilo.

8
00:00:22,550 --> 00:00:26,360
Kiam vi nomas funkcio, la
sistemo malobservos spaco en memoro

9
00:00:26,360 --> 00:00:28,120
por tiu funkcio fari lia laboro.

10
00:00:28,120 --> 00:00:31,720
Kaj ni nomas tiujn pecojn de memoro kiu
estas estanta rezervita por ĉiu funkcio

11
00:00:31,720 --> 00:00:35,670
voki stako aŭ funkcio kadro.

12
00:00:35,670 --> 00:00:38,290
Kaj kiel vi povus atendi,
tiuj pilo kadroj

13
00:00:38,290 --> 00:00:41,000
vivi sur la stako parto de memoro.

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

15
00:00:43,960 --> 00:00:47,540
>> Pli ol unu funkcion stako
povas ekzisti en memoro je donita tempo.

16
00:00:47,540 --> 00:00:51,240
Se ĉefa nomas funkcio movo,
kaj movon nomas direkto,

17
00:00:51,240 --> 00:00:54,460
ĉiuj tri funkcioj havas malfermita kadroj.

18
00:00:54,460 --> 00:00:57,350
Sed ne ĉiuj havas aktivaj kadroj.

19
00:00:57,350 --> 00:00:59,410
Tiuj framoj estas aranĝitaj en stako.

20
00:00:59,410 --> 00:01:01,820
Kaj la kadro de la
plej ĵuse nomita

21
00:01:01,820 --> 00:01:04,390
funkcio estas ĉiam sur supro de la stako.

22
00:01:04,390 --> 00:01:07,150
Kaj tio estas ĉiam la aktiva kadro.

23
00:01:07,150 --> 00:01:10,420
Ekzistas nur vere iam oni
funkcio jen aktiva samtempe.

24
00:01:10,420 --> 00:01:12,420
Ĝi estas la unu sur supro de la stako.

25
00:01:12,420 --> 00:01:17,620
>> Kiam funkcio vokas alian
funkcio, ĝi ia premas paŭzo.

26
00:01:17,620 --> 00:01:20,590
Ĝi ia estas sur tene, atendante.

27
00:01:20,590 --> 00:01:24,050
Kaj alia stako estas pelita
sur la pilo sur gxian supron.

28
00:01:24,050 --> 00:01:26,150
Kaj tio igas la aktivan kadro.

29
00:01:26,150 --> 00:01:28,600
Kaj la kadro tuj
sube ĝi bezonas atendi

30
00:01:28,600 --> 00:01:33,560
ĝis ĝi estas denove la aktiva kadro
antaŭ ol ĝi povas rekomenci lian laboron.

31
00:01:33,560 --> 00:01:35,870
Kiam funkcio estas
kompleta kaj ĝi estas farita,

32
00:01:35,870 --> 00:01:37,720
ĝia kadro estas krevita for la stako.

33
00:01:37,720 --> 00:01:38,950
Tio estas la terminologio.

34
00:01:38,950 --> 00:01:41,110
Kaj la kadro tuj
sub ĝi, kiel mi ĵus diris,

35
00:01:41,110 --> 00:01:42,880
iĝas la nova aktiva kadro.

36
00:01:42,880 --> 00:01:45,960
>> Kaj se li nomas alian funkcion,
ĝi tuj paŭzi denove.

37
00:01:45,960 --> 00:01:49,290
Tiu nova funkcia stako volo
esti puŝita sur la supro de la stako.

38
00:01:49,290 --> 00:01:50,650
Ĝi faros lian laboron.

39
00:01:50,650 --> 00:01:52,100
Eble pop reen for.

40
00:01:52,100 --> 00:01:55,630
Kaj la alia funkcio
sube ĝi povas rekomenci denove.

41
00:01:55,630 --> 00:02:00,080
>> Do ni iru tra tiu denove, rigardanta
ĉe la ideo de la faktorialo funkcio

42
00:02:00,080 --> 00:02:03,070
ke ni difinis en la
rekursio vídeo vidi

43
00:02:03,070 --> 00:02:07,770
ĝuste kiel la magio malantaŭ tiu
rekursia procezo okazas.

44
00:02:07,770 --> 00:02:09,870
Do jen nia tuta dosiero, dekstra?

45
00:02:09,870 --> 00:02:14,000
Ni difinis du
functions-- ĉefa kaj fakto.

46
00:02:14,000 --> 00:02:15,980
Kaj kiel ni povus atendi,
ajna C programon tuj

47
00:02:15,980 --> 00:02:18,470
komenci ĉe la unua linio de ĉefa.

48
00:02:18,470 --> 00:02:21,660
>> Do ni krei novan stako por ĉefa.

49
00:02:21,660 --> 00:02:23,320
Kaj ĝi tuj komencos kurado.

50
00:02:23,320 --> 00:02:25,270
Ĉefa alvokoj printf.

51
00:02:25,270 --> 00:02:29,390
Kaj printf tuj
elprinti faktorialo de 5.

52
00:02:29,390 --> 00:02:31,440
Nu, ĝi ne scias
kio faktorialo de 5 estas:

53
00:02:31,440 --> 00:02:35,620
kaj tiel ĉi alvoko estas jam
depende alia funkcio nomita.

54
00:02:35,620 --> 00:02:37,270
Do ĉefa tuj paŭzi prava.

55
00:02:37,270 --> 00:02:39,103
Mi estas gonna forlasi liajn
arrow Dekstre, koloro

56
00:02:39,103 --> 00:02:41,360
ĝi la saman koloron kiel la
stako dekstre

57
00:02:41,360 --> 00:02:47,720
indiki ke ĉefa tuj frosti
tie dum faktorialo de 5 estas nomita.

58
00:02:47,720 --> 00:02:49,300
>> Do faktorialo de 5 estas nomita.

59
00:02:49,300 --> 00:02:53,160
Kaj ĝi tuj starti je la tre
komencante de la faktorialo funkcio.

60
00:02:53,160 --> 00:02:55,440
Ĝi demandas la demandon mi egali al 1?

61
00:02:55,440 --> 00:02:56,810
Estas 5 egala al 1?

62
00:02:56,810 --> 00:02:57,410
Nu, ne.

63
00:02:57,410 --> 00:03:01,110
Do ĝi estas tuj iri malsupren al
la alia parto, reveno n fojoj

64
00:03:01,110 --> 00:03:02,990
faktorialo de n minus 1.

65
00:03:02,990 --> 00:03:03,490
Nu, bone.

66
00:03:03,490 --> 00:03:07,070
>> Do nun, faktorialo de 5 estas
depende alia alvoko

67
00:03:07,070 --> 00:03:09,740
al faktorialo, pasante
en 4 kiel la parametro.

68
00:03:09,740 --> 00:03:14,210
Kaj tial la faktorialon
5 kadro, ke ruĝa kadro,

69
00:03:14,210 --> 00:03:17,160
tuj frosti Dekstre
en tiu linio mi indikis

70
00:03:17,160 --> 00:03:21,914
kaj atendi faktorialon 4 fini
kion bezonas fari tiel ke tiam

71
00:03:21,914 --> 00:03:23,330
povas fariĝi la aktiva kadro denove.

72
00:03:23,330 --> 00:03:26,890
>> Do faktorialon 4 komenciĝas ĉe
la komenco de faktorialo.

73
00:03:26,890 --> 00:03:28,556
Estas 4 egala al 1?

74
00:03:28,556 --> 00:03:30,180
Ne, tiel ĝi tuj faros la samon.

75
00:03:30,180 --> 00:03:31,590
Ĝi tuj malsupreniros la alia branĉo.

76
00:03:31,590 --> 00:03:33,240
Ĝi tuj atingos tion linio de kodo.

77
00:03:33,240 --> 00:03:35,710
OK, mi tuj revenos kvarfoje.

78
00:03:35,710 --> 00:03:41,270
Ho, faktorialo de 3-- tiel faktorialon
4 dependas faktorialon 3 broĉon.

79
00:03:41,270 --> 00:03:43,055
>> Kaj tial ĝi bezonas voki faktorialo de 3.

80
00:03:43,055 --> 00:03:45,180
Kaj tio estas gonna trairu
la sama procezo denove.

81
00:03:45,180 --> 00:03:48,200
Ĝi komenciĝas per, ricevas tie.

82
00:03:48,200 --> 00:03:50,980
Faktorialo de 3 dependas
sur faktorialon 1.

83
00:03:50,980 --> 00:03:53,750
Do faktorialon 2 startas, ricevas tie.

84
00:03:53,750 --> 00:03:56,310
Dependas faktorialon 1.

85
00:03:56,310 --> 00:03:57,430
Faktorialon 1 komencoj.

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

87
00:03:57,650 --> 00:03:59,775
Do nun, ni ricevas
ie interesa, ĉu ne?

88
00:03:59,775 --> 00:04:02,190
Do nun, 1 estas egala al 1.

89
00:04:02,190 --> 00:04:05,130
Kaj tiel ni revenos 1.

90
00:04:05,130 --> 00:04:06,770
Je tiu punkto, ni revenas.

91
00:04:06,770 --> 00:04:07,880
La funkcio estas farita.

92
00:04:07,880 --> 00:04:11,140
Estas konduto is-- ekzistas
Nenio alia eblas fari,

93
00:04:11,140 --> 00:04:17,006
kaj tiel la stako por
faktorialon 1 krevas for.

94
00:04:17,006 --> 00:04:17,589
Ĝi estas finita.

95
00:04:17,589 --> 00:04:19,480
Ĝi revenis 1.

96
00:04:19,480 --> 00:04:23,370
Kaj nun, faktorialo de 2, kiu
Estis la kadro tuj sub ĝi

97
00:04:23,370 --> 00:04:26,160
en la pilo, igas la aktivan kadro.

98
00:04:26,160 --> 00:04:29,030
>> Kaj ĝi povas repreni
ĝuste kie lasis.

99
00:04:29,030 --> 00:04:32,240
Ĝi estas estita atendanta por faktorialo
de 1 por fini lian laboron.

100
00:04:32,240 --> 00:04:33,610
Ĝi nun finita.

101
00:04:33,610 --> 00:04:35,510
Do jen ni estas.

102
00:04:35,510 --> 00:04:38,080
>> Faktorialon 1 resendis valoro de 1.

103
00:04:38,080 --> 00:04:42,430
Do faktorialon 2 ladskatolon
diru reveni 2 fojoj 1.

104
00:04:42,430 --> 00:04:43,680
Lia verko estas jam farita.

105
00:04:43,680 --> 00:04:49,110
Ĝi revenis al 2 faktorialo
de 3, kiu atendis ĝin.

106
00:04:49,110 --> 00:04:53,370
Faktorialo de 3 estas nun la supro kadro,
la aktiva kadro en la stako.

107
00:04:53,370 --> 00:04:58,617
Kaj tiel diras, OK, bone, mi tuj
reveni 3 fojojn 2, kiu estas 6.

108
00:04:58,617 --> 00:05:00,700
Kaj mi tuj doni tiun
taksos reen al faktorialo

109
00:05:00,700 --> 00:05:03,430
de 4, kiu estis atendanta min.

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

111
00:05:04,500 --> 00:05:09,410
Faktorialo de 3 krevas for la stako, kaj
faktorialo de 4 estas nun la aktiva kadro.

112
00:05:09,410 --> 00:05:13,510
>> 4 diras, OK, mi tuj revenos 4 fojoj
la faktorialo de 3, kiu estis ses.

113
00:05:13,510 --> 00:05:15,980
Kiu estis de valoro kiu
faktorialo de 3 revenis.

114
00:05:15,980 --> 00:05:19,010
Kaj do 4 fojojn 6 estas 24.

115
00:05:19,010 --> 00:05:20,990
Kaj mi tuj pasos
ke reen al faktorialo

116
00:05:20,990 --> 00:05:23,160
5, kiu estis atendanta min.

117
00:05:23,160 --> 00:05:25,270
Faktorialo de 5 estas nun la aktiva kadro.

118
00:05:25,270 --> 00:05:30,700
Ĝi tuj revenos 5 fojoj
faktorialon 4-- 5 fojojn 24, aŭ 120--

119
00:05:30,700 --> 00:05:32,722
kaj donu ke valoro
reen al ĉefa, kiu havas

120
00:05:32,722 --> 00:05:35,680
atendis tre pacience dum
longa tempo ĉe la fundo de la stako.

121
00:05:35,680 --> 00:05:36,640
>> Ĝi estas kie komenci.

122
00:05:36,640 --> 00:05:37,670
Ĝi faris tiun alvokon.

123
00:05:37,670 --> 00:05:39,400
Pluraj kadroj transprenis ĉe la supro.

124
00:05:39,400 --> 00:05:41,890
Ĝi estas nun reen sur pinto de la stako.

125
00:05:41,890 --> 00:05:43,450
Ĝi estas la aktiva kadro.

126
00:05:43,450 --> 00:05:47,810
Do ĉefa havas la valoron 120
reen de faktorialo de 5.

127
00:05:47,810 --> 00:05:50,750
Ĝi estas estita atendanta
elprinti tiun valoron.

128
00:05:50,750 --> 00:05:51,657
Kaj tiam ĝi estas farita.

129
00:05:51,657 --> 00:05:53,240
Mankas pli linioj de kodo en ĉefa.

130
00:05:53,240 --> 00:05:56,800
Do ĉefa la kadro krevas for
la pilo, kaj ni faris.

131
00:05:56,800 --> 00:05:58,992
>> Kaj tiel estas kiel rikuro funkcias.

132
00:05:58,992 --> 00:06:00,200
Tiel estas kiel stako kadroj labori.

133
00:06:00,200 --> 00:06:03,120
Tiuj funkcio alvokoj
kiu okazis antaŭe

134
00:06:03,120 --> 00:06:06,620
estas nur sur paŭzo, atendante
por la postaj vokoj

135
00:06:06,620 --> 00:06:12,050
fini tiel ili povas iĝi la aktiva
enmarcar kaj fini kion ili devas fari.

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

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

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