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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Ef þú hefur séð
vídeó á endurkvæmni,

3
00:00:07,670 --> 00:00:10,170
allt ferlið gæti hafa
virtist svolítið töfrandi.

4
00:00:10,170 --> 00:00:10,930
Hvernig virkar það?

5
00:00:10,930 --> 00:00:15,010
Hvernig gera aðgerðir vita að þeir
þurfa að bíða og bíða eftir öðrum verðmæti

6
00:00:15,010 --> 00:00:19,150
til að fara aftur frá mismunandi föllum
hringja til að fá niðurstöðuna sem við viljum?

7
00:00:19,150 --> 00:00:22,550
>> Jæja, ástæðan þetta virkar er vegna
eitthvað þekktur sem kalla stafla.

8
00:00:22,550 --> 00:00:26,360
Þegar þú hringja í aðgerð, sem
Kerfið setur til hliðar pláss í minni

9
00:00:26,360 --> 00:00:28,120
fyrir að virka að gera vinnu sína.

10
00:00:28,120 --> 00:00:31,720
Og við köllum þessar klumpur af minni sem
eru sett til hliðar fyrir hverja aðgerð

11
00:00:31,720 --> 00:00:35,670
kalla stafla ramma eða virka ramma.

12
00:00:35,670 --> 00:00:38,290
Og eins og þú might búast við,
þessi stafla ramma

13
00:00:38,290 --> 00:00:41,000
lifa á stafla af hálfu minni.

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

15
00:00:43,960 --> 00:00:47,540
>> Meira en ein aðgerð stafla ramma
getur verið í minni á hverjum tíma.

16
00:00:47,540 --> 00:00:51,240
Ef helstu kallar virka færa,
og færa símtöl átt,

17
00:00:51,240 --> 00:00:54,460
Öll þrjú aðgerðir hafa opinn ramma.

18
00:00:54,460 --> 00:00:57,350
En þeir gera ekki hafa allir virk ramma.

19
00:00:57,350 --> 00:00:59,410
Þessir rammar eru raðað í stafla.

20
00:00:59,410 --> 00:01:01,820
Og ramma úr
hringdir

21
00:01:01,820 --> 00:01:04,390
virka er alltaf ofan á stafla.

22
00:01:04,390 --> 00:01:07,150
Og það er alltaf virka rammanum.

23
00:01:07,150 --> 00:01:10,420
Það er bara virkilega alltaf einn
fall sem er virkt í einu.

24
00:01:10,420 --> 00:01:12,420
Það er eitt ofan á stafla.

25
00:01:12,420 --> 00:01:17,620
>> Þegar virka símtöl annar
virka, það þrýstir konar hlé.

26
00:01:17,620 --> 00:01:20,590
Það er tegund af bið, bið.

27
00:01:20,590 --> 00:01:24,050
Og annar stafla ramma er ýtt
á stafla ofan á hana.

28
00:01:24,050 --> 00:01:26,150
Og að verður virkur ramma.

29
00:01:26,150 --> 00:01:28,600
Og ramma strax
neðan það þarf að bíða

30
00:01:28,600 --> 00:01:33,560
þar til það er aftur virka rammanum
áður en það getur haldið áfram starfi sínu.

31
00:01:33,560 --> 00:01:35,870
Þegar aðgerð er
heill og það er gert,

32
00:01:35,870 --> 00:01:37,720
rammi hennar er smella af stafla.

33
00:01:37,720 --> 00:01:38,950
Það er hugtakanotkun.

34
00:01:38,950 --> 00:01:41,110
Og ramma strax
undir það, eins og ég sagði bara,

35
00:01:41,110 --> 00:01:42,880
verður nýja virka rammanum.

36
00:01:42,880 --> 00:01:45,960
>> Og ef það kallar annar virka,
það er að fara að gera hlé aftur.

37
00:01:45,960 --> 00:01:49,290
Stafla ramma sem nýtt hlutverk mun
verið ýtt inn á efsta hluta stafla.

38
00:01:49,290 --> 00:01:50,650
Það mun gera starf sitt.

39
00:01:50,650 --> 00:01:52,100
Það gæti skjóta aftur burt.

40
00:01:52,100 --> 00:01:55,630
Og önnur virka
neðan það getur haldið áfram aftur.

41
00:01:55,630 --> 00:02:00,080
>> Svo skulum við fara í gegnum þetta aftur, leita
á hugmyndinni um þátta virka

42
00:02:00,080 --> 00:02:03,070
að við og skilgreint er í
endurkvæmni video til að sjá

43
00:02:03,070 --> 00:02:07,770
nákvæmlega hvernig galdur á bak við þetta
endurkvæma aðferð er að taka fram.

44
00:02:07,770 --> 00:02:09,870
Svo er þetta allt skrá okkar, ekki satt?

45
00:02:09,870 --> 00:02:14,000
Við skilgreiningu tvö
functions-- helstu og staðreynd.

46
00:02:14,000 --> 00:02:15,980
Og eins og við mátti búast
hvaða C program er að fara

47
00:02:15,980 --> 00:02:18,470
að byrja á fyrstu línu main.

48
00:02:18,470 --> 00:02:21,660
>> Svo við að búa til nýja stafla ramma fyrir helstu.

49
00:02:21,660 --> 00:02:23,320
Og það er að fara að byrja að keyra.

50
00:02:23,320 --> 00:02:25,270
Helstu símtöl printf.

51
00:02:25,270 --> 00:02:29,390
Og printf er að fara að
prenta út aðfeldi 5.

52
00:02:29,390 --> 00:02:31,440
Jæja, það veit ekki
hvað þáttatilraun af 5 er,

53
00:02:31,440 --> 00:02:35,620
og svo er þetta kalla nú þegar
eftir öðru virka símtalinu.

54
00:02:35,620 --> 00:02:37,270
Svo helstu er að fara að gera hlé þarna.

55
00:02:37,270 --> 00:02:39,103
Ég ætla að fara þess
arrow rétt þar, lit

56
00:02:39,103 --> 00:02:41,360
það í sama lit sem
stafla ramma til hægri,

57
00:02:41,360 --> 00:02:47,720
að gefa til kynna að helstu er að fara að frysta
hér en þáttatilraun af 5 er kallað.

58
00:02:47,720 --> 00:02:49,300
>> Svo þáttatilraun af 5 er kallað.

59
00:02:49,300 --> 00:02:53,160
Og það er að fara að byrja á mjög
farin að þátta virka.

60
00:02:53,160 --> 00:02:55,440
Það spyr spurningu ég er jafn 1?

61
00:02:55,440 --> 00:02:56,810
Er 5 jöfn 1?

62
00:02:56,810 --> 00:02:57,410
Jæja, ekki.

63
00:02:57,410 --> 00:03:01,110
Svo það er að fara að fara niður í
else hluti, aftur n sinnum

64
00:03:01,110 --> 00:03:02,990
þáttatilraun n mínus 1.

65
00:03:02,990 --> 00:03:03,490
Jæja, allt í lagi.

66
00:03:03,490 --> 00:03:07,070
>> Svo nú, þáttatilraun af 5 er
eftir öðru símtali

67
00:03:07,070 --> 00:03:09,740
að þáttatilraun, liggur
í 4 sem breytu.

68
00:03:09,740 --> 00:03:14,210
Og svo aðfeldi
5 ramma, sem rauðum ramma,

69
00:03:14,210 --> 00:03:17,160
er að fara að frysta þarna
á þeirri línu sem ég hef ætlað

70
00:03:17,160 --> 00:03:21,914
og bíða eftir aðfeldi 4 að klára
það sem það þarf að gera svo að þá er það

71
00:03:21,914 --> 00:03:23,330
getur orðið virka rammanum aftur.

72
00:03:23,330 --> 00:03:26,890
>> Svo þáttatilraun af 4 hefst á
upphaf þáttatilraun.

73
00:03:26,890 --> 00:03:28,556
Er 4 jöfn 1?

74
00:03:28,556 --> 00:03:30,180
Nei, svo það er að fara að gera það sama.

75
00:03:30,180 --> 00:03:31,590
Það er að fara að fara niður annað útibú.

76
00:03:31,590 --> 00:03:33,240
Það er að fara að fá til að línu af kóða.

77
00:03:33,240 --> 00:03:35,710
OK, ég ætla að fara aftur fjórum sinnum.

78
00:03:35,710 --> 00:03:41,270
Oh, þáttatilraun af 3-- svo aðfeldi
4 veltur á Hrópmerkt 3. frágangi.

79
00:03:41,270 --> 00:03:43,055
>> Og svo það þarf að hringja aðfeldi 3.

80
00:03:43,055 --> 00:03:45,180
Og það er ađ fara í gegnum
sama ferli aftur.

81
00:03:45,180 --> 00:03:48,200
Það byrjar með, fær hér.

82
00:03:48,200 --> 00:03:50,980
Factorial af 3 veltur
á Hrópmerkt af 1.

83
00:03:50,980 --> 00:03:53,750
Svo þáttatilraun af 2 byrjar, fær hér.

84
00:03:53,750 --> 00:03:56,310
Það fer eftir Hrópmerkt af 1.

85
00:03:56,310 --> 00:03:57,430
Factorial af 1 hefst.

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

87
00:03:57,650 --> 00:03:59,775
Svo nú erum við að fá
einhvers staðar áhugavert, ekki satt?

88
00:03:59,775 --> 00:04:02,190
Svo nú, 1 er jafnt og 1.

89
00:04:02,190 --> 00:04:05,130
Og svo við aftur 1.

90
00:04:05,130 --> 00:04:06,770
Á þessum tímapunkti, við erum aftur.

91
00:04:06,770 --> 00:04:07,880
Fallið er gert.

92
00:04:07,880 --> 00:04:11,140
Það er hegðun is-- það er
ekkert annað fyrir það að gera,

93
00:04:11,140 --> 00:04:17,006
og svo stafla ramma fyrir
þáttatilraun af 1 birtist burt.

94
00:04:17,006 --> 00:04:17,589
Það er búið.

95
00:04:17,589 --> 00:04:19,480
Það skilaði 1.

96
00:04:19,480 --> 00:04:23,370
Og nú, þáttatilraun af 2, sem
var ramma strax fyrir neðan það

97
00:04:23,370 --> 00:04:26,160
í stafla, verður virkur ramma.

98
00:04:26,160 --> 00:04:29,030
>> Og það getur tekið upp
nákvæmlega hvar það var horfið.

99
00:04:29,030 --> 00:04:32,240
Það er verið að bíða eftir Hrópmerkt
frá 1 til ljúka störfum.

100
00:04:32,240 --> 00:04:33,610
Það hefur nú lokið.

101
00:04:33,610 --> 00:04:35,510
Og svo hér erum við.

102
00:04:35,510 --> 00:04:38,080
>> Factorial af 1 aftur gildið 1.

103
00:04:38,080 --> 00:04:42,430
Svo þáttatilraun af 2 dós
segjum aftur 2 sinnum 1.

104
00:04:42,430 --> 00:04:43,680
Starf hennar er nú lokið.

105
00:04:43,680 --> 00:04:49,110
Það er aftur 2 til þátta
3, sem var að bíða eftir henni.

106
00:04:49,110 --> 00:04:53,370
Factorial af 3 er nú efst ramma,
virka rammanum í stafla.

107
00:04:53,370 --> 00:04:58,617
Og svo segir hún, OK, vel, ég ætla
til að fara aftur 3 sinnum 2, sem er 6.

108
00:04:58,617 --> 00:05:00,700
Og ég ætla að gefa sem
gildi aftur til Hrópmerkt

109
00:05:00,700 --> 00:05:03,430
af 4, sem hefur verið að bíða eftir mér.

110
00:05:03,430 --> 00:05:04,500
Ég er búinn.

111
00:05:04,500 --> 00:05:09,410
Factorial af 3 birtist af stafla, og
þáttatilraun af 4 er nú virkur ramma.

112
00:05:09,410 --> 00:05:13,510
>> 4 segir, OK, ég ætla að fara aftur 4 sinnum
þáttatilraun af 3, sem var sex ára.

113
00:05:13,510 --> 00:05:15,980
Það var af value að
þáttatilraun af 3 aftur.

114
00:05:15,980 --> 00:05:19,010
Og svo 4 sinnum 6 er 24.

115
00:05:19,010 --> 00:05:20,990
Og ég ætla að fara
sem aftur þátta

116
00:05:20,990 --> 00:05:23,160
5, sem hefur verið að bíða eftir mér.

117
00:05:23,160 --> 00:05:25,270
Factorial af 5 er nú virk ramma.

118
00:05:25,270 --> 00:05:30,700
Það er að fara að fara aftur 5 sinnum
þáttatilraun af 4-- 5 sinnum 24 eða 120--

119
00:05:30,700 --> 00:05:32,722
og gefa það gildi
Til baka á aðalsíðu, sem hefur

120
00:05:32,722 --> 00:05:35,680
verið að bíða mjög þolinmóður eftir a
langan tíma neðst á stafla.

121
00:05:35,680 --> 00:05:36,640
>> Það er þar sem það byrjaði.

122
00:05:36,640 --> 00:05:37,670
Það gerði þetta símtal.

123
00:05:37,670 --> 00:05:39,400
Nokkrir rammar tók efst.

124
00:05:39,400 --> 00:05:41,890
Það er nú aftur ofan á stafla.

125
00:05:41,890 --> 00:05:43,450
Það er virka rammanum.

126
00:05:43,450 --> 00:05:47,810
Svo helstu fékk gildi 120
aftur frá Hrópmerkt 5.

127
00:05:47,810 --> 00:05:50,750
Það er verið að bíða eftir að
prenta út þetta gildi.

128
00:05:50,750 --> 00:05:51,657
Og þá er það gert.

129
00:05:51,657 --> 00:05:53,240
Það er engin fleiri línur af kóða í main.

130
00:05:53,240 --> 00:05:56,800
Svo birtist rammi main er af
stafla, og við erum að gera.

131
00:05:56,800 --> 00:05:58,992
>> Og það er hvernig endurkvæmni virkar.

132
00:05:58,992 --> 00:06:00,200
Það er hvernig stafla ramma vinna.

133
00:06:00,200 --> 00:06:03,120
Þeir virka símtöl
sem gerðist áður

134
00:06:03,120 --> 00:06:06,620
eru bara á hlé, bíða
fyrir síðari útboð

135
00:06:06,620 --> 00:06:12,050
að klára svo þeir geta orðið virkir
ramma og klára það sem þeir þurfa að gera.

136
00:06:12,050 --> 00:06:13,060
>> Ég er Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Þetta er CS50.

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