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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Als je hebt gezien
de video op terugkeer,

3
00:00:07,670 --> 00:00:10,170
het hele proces kan hebben
leek een beetje magisch.

4
00:00:10,170 --> 00:00:10,930
Hoe werkt het?

5
00:00:10,930 --> 00:00:15,010
Hoe weet de functies weten dat ze
moeten wachten en wachten op een andere waarde

6
00:00:15,010 --> 00:00:19,150
terug vanuit een andere functie
bellen om het resultaat dat we willen krijgen?

7
00:00:19,150 --> 00:00:22,550
>> Nou, de reden dat dit werkt is omdat
iets bekend als de call-stack.

8
00:00:22,550 --> 00:00:26,360
Wanneer u een functie aan te roepen, de
systeem vernietigt ruimte in het geheugen

9
00:00:26,360 --> 00:00:28,120
voor die functie om zijn werk te doen.

10
00:00:28,120 --> 00:00:31,720
En we die delen van het geheugen noemen
worden gereserveerd voor elke functie

11
00:00:31,720 --> 00:00:35,670
bel een stack frame of een functie frame.

12
00:00:35,670 --> 00:00:38,290
En zoals je zou verwachten,
deze stack frames

13
00:00:38,290 --> 00:00:41,000
live op de stapel deel van het geheugen.

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

15
00:00:43,960 --> 00:00:47,540
>> Meer dan één functie stack frame
kunnen bestaan ​​in het geheugen op een bepaald moment.

16
00:00:47,540 --> 00:00:51,240
Als voornaamste noemt een functie zet,
en beweging noemt richting,

17
00:00:51,240 --> 00:00:54,460
Alle drie functies hebben een open frames.

18
00:00:54,460 --> 00:00:57,350
Maar ze hebben niet allemaal actief frames.

19
00:00:57,350 --> 00:00:59,410
Deze frames zijn gerangschikt in een stapel.

20
00:00:59,410 --> 00:01:01,820
En het kader van de
meest recent opgeroepen

21
00:01:01,820 --> 00:01:04,390
functie altijd boven de stapel.

22
00:01:04,390 --> 00:01:07,150
En dat is altijd het actieve frame.

23
00:01:07,150 --> 00:01:10,420
Er is maar één echt ooit
functie is tegelijk actief.

24
00:01:10,420 --> 00:01:12,420
Het is de een boven op de stapel.

25
00:01:12,420 --> 00:01:17,620
>> Wanneer een functie noemt een ander
functie, soort drukt pauze.

26
00:01:17,620 --> 00:01:20,590
Het is een soort van de wacht, wacht.

27
00:01:20,590 --> 00:01:24,050
En een andere stack frame wordt geduwd
op de stapel op de top van het.

28
00:01:24,050 --> 00:01:26,150
En dat wordt de actieve frame.

29
00:01:26,150 --> 00:01:28,600
En onmiddellijk het frame
daaronder moet wachten

30
00:01:28,600 --> 00:01:33,560
totdat weer het actieve lijst
voordat het zijn werk kan hervatten.

31
00:01:33,560 --> 00:01:35,870
Als een functie
compleet en het is gedaan,

32
00:01:35,870 --> 00:01:37,720
het frame is popped uit de stapel.

33
00:01:37,720 --> 00:01:38,950
Dat is de terminologie.

34
00:01:38,950 --> 00:01:41,110
En onmiddellijk het frame
eronder, zoals ik net zei,

35
00:01:41,110 --> 00:01:42,880
wordt de nieuwe actieve frame.

36
00:01:42,880 --> 00:01:45,960
>> En als het een andere functie oproepen,
het gaat om weer te pauzeren.

37
00:01:45,960 --> 00:01:49,290
Stack frame dat de nieuwe functie zal
worden geduwd op de bovenzijde van de stapel.

38
00:01:49,290 --> 00:01:50,650
Het zal zijn werk doen.

39
00:01:50,650 --> 00:01:52,100
Het is misschien off pop terug.

40
00:01:52,100 --> 00:01:55,630
En de andere functie
daaronder weer kan hervatten.

41
00:01:55,630 --> 00:02:00,080
>> Dus laten we gaan door dit opnieuw, zoek
bij het idee van de faculteit-functie

42
00:02:00,080 --> 00:02:03,070
wij gedefinieerd in de
recursie video te zien

43
00:02:03,070 --> 00:02:07,770
precies hoe de magie achter deze
recursieve proces plaatsvindt.

44
00:02:07,770 --> 00:02:09,870
Dus dit is onze hele bestand, toch?

45
00:02:09,870 --> 00:02:14,000
We gedefinieerd twee
functions-- hoofd- en feit.

46
00:02:14,000 --> 00:02:15,980
En zoals we kunnen verwachten,
elke C programma gaat

47
00:02:15,980 --> 00:02:18,470
om te beginnen bij de eerste regel van de belangrijkste.

48
00:02:18,470 --> 00:02:21,660
>> Zo creëren we een nieuwe stack frame voor main.

49
00:02:21,660 --> 00:02:23,320
En het gaat om te beginnen met hardlopen.

50
00:02:23,320 --> 00:02:25,270
Belangrijkste oproepen printf.

51
00:02:25,270 --> 00:02:29,390
En printf gaat
uitprinten faculteit van 5.

52
00:02:29,390 --> 00:02:31,440
Nou, het maakt niet weet
Wat faculteit van 5 is,

53
00:02:31,440 --> 00:02:35,620
en zo deze oproep is al
afhankelijk van een andere functie aan te roepen.

54
00:02:35,620 --> 00:02:37,270
Dus belangrijkste gaat om daar te pauzeren.

55
00:02:37,270 --> 00:02:39,103
Ik laat haar
pijl daar, kleur

56
00:02:39,103 --> 00:02:41,360
Het dezelfde kleur als de
stack frame op de juiste,

57
00:02:41,360 --> 00:02:47,720
geeft aan dat belangrijke zal bevriezen
hier tijdens faculteit van 5 heet.

58
00:02:47,720 --> 00:02:49,300
>> Dus faculteit van 5 genoemd.

59
00:02:49,300 --> 00:02:53,160
En het gaat om te beginnen bij de
begin van de faculteit-functie.

60
00:02:53,160 --> 00:02:55,440
Het stelt de vraag ben ik gelijk aan 1?

61
00:02:55,440 --> 00:02:56,810
Is 5 gelijk aan 1?

62
00:02:56,810 --> 00:02:57,410
Nou nee.

63
00:02:57,410 --> 00:03:01,110
Dus het gaat naar beneden te gaan naar
de andere kant, rendement n keer

64
00:03:01,110 --> 00:03:02,990
faculteit van n minus 1.

65
00:03:02,990 --> 00:03:03,490
Nou oke.

66
00:03:03,490 --> 00:03:07,070
>> Dus nu, faculteit van 5 is
afhankelijk van een ander gesprek

67
00:03:07,070 --> 00:03:09,740
tot Faculteit, passeren
4 in de parameter.

68
00:03:09,740 --> 00:03:14,210
En zo de faculteit van
5 frame, dat rood frame,

69
00:03:14,210 --> 00:03:17,160
gaat om daar te bevriezen
op die lijn die ik heb aangegeven

70
00:03:17,160 --> 00:03:21,914
en wachten op faculteit van 4 tot finish
wat het moet dat doen dan

71
00:03:21,914 --> 00:03:23,330
kan het actieve beeld weer te worden.

72
00:03:23,330 --> 00:03:26,890
>> Dus faculteit van 4 begint bij
Begin factorial.

73
00:03:26,890 --> 00:03:28,556
4 is gelijk aan 1?

74
00:03:28,556 --> 00:03:30,180
Nee, dus het gaat om hetzelfde te doen.

75
00:03:30,180 --> 00:03:31,590
Het gaat naar beneden te gaan de andere tak.

76
00:03:31,590 --> 00:03:33,240
Het gaat om die regel code te krijgen.

77
00:03:33,240 --> 00:03:35,710
OK, ik ga tot vier keer terug te keren.

78
00:03:35,710 --> 00:03:41,270
Oh, faculteit van 3-- zo faculteit van
4 afhankelijk faculteit van 3 finishing.

79
00:03:41,270 --> 00:03:43,055
>> En zo moet faculteit van 3 noemen.

80
00:03:43,055 --> 00:03:45,180
En dat is gonna gaan door
hetzelfde proces opnieuw.

81
00:03:45,180 --> 00:03:48,200
Het begint door en krijgt hier.

82
00:03:48,200 --> 00:03:50,980
Faculteit van 3 afhangt
op faculteit van 1.

83
00:03:50,980 --> 00:03:53,750
Dus faculteit van 2 begint, krijgt hier.

84
00:03:53,750 --> 00:03:56,310
Het hangt faculteit van 1.

85
00:03:56,310 --> 00:03:57,430
Faculteit van 1 begint.

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

87
00:03:57,650 --> 00:03:59,775
Dus nu, we krijgen
ergens interessant, toch?

88
00:03:59,775 --> 00:04:02,190
Nu, 1 gelijk is aan 1.

89
00:04:02,190 --> 00:04:05,130
En zo zijn we weer 1.

90
00:04:05,130 --> 00:04:06,770
Op dit moment, keren we terug.

91
00:04:06,770 --> 00:04:07,880
De functie heeft gedaan.

92
00:04:07,880 --> 00:04:11,140
Het is gedrag is-- er
niets anders om het te doen,

93
00:04:11,140 --> 00:04:17,006
en zo de stack frame voor
faculteit van 1 knalt uit.

94
00:04:17,006 --> 00:04:17,589
Het is klaar.

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

96
00:04:19,480 --> 00:04:23,370
Nu, faculteit van 2, waarvan
was het frame direct eronder

97
00:04:23,370 --> 00:04:26,160
in de stapel, wordt de actieve frame.

98
00:04:26,160 --> 00:04:29,030
>> En het kan ophalen
precies waar hij was gebleven.

99
00:04:29,030 --> 00:04:32,240
Het is al te wachten op een faculteit
van 1 naar zijn werk te voltooien.

100
00:04:32,240 --> 00:04:33,610
Het is nu beëindigd.

101
00:04:33,610 --> 00:04:35,510
En zo zijn we hier.

102
00:04:35,510 --> 00:04:38,080
>> Faculteit van 1 terug een waarde van 1.

103
00:04:38,080 --> 00:04:42,430
Dus faculteit van 2 blikje
zeg terugkeren 2 keer 1.

104
00:04:42,430 --> 00:04:43,680
Zijn werk wordt nu gedaan.

105
00:04:43,680 --> 00:04:49,110
Het is teruggekeerd 2 tot Faculteit
van 3, die stond te wachten.

106
00:04:49,110 --> 00:04:53,370
Faculteit van 3 is nu de top frame,
de actieve frame in de stapel.

107
00:04:53,370 --> 00:04:58,617
En zo zegt: OK, nou, ik ga
tot 3 maal 2, dat 6 terug.

108
00:04:58,617 --> 00:05:00,700
En ik ga geven dat
de waarde terug naar faculteit

109
00:05:00,700 --> 00:05:03,430
van 4, is die op me te wachten.

110
00:05:03,430 --> 00:05:04,500
Ik ben klaar.

111
00:05:04,500 --> 00:05:09,410
Faculteit van 3 knalt uit de stapel, en
faculteit van 4 is nu de actieve frame.

112
00:05:09,410 --> 00:05:13,510
>> 4 zegt: OK, ik ga 4 keer terug
de faculteit van 3, waarvan zes was.

113
00:05:13,510 --> 00:05:15,980
Dat was van de waarde die
faculteit van 3 teruggekeerd.

114
00:05:15,980 --> 00:05:19,010
En dus 4 maal 6 is 24.

115
00:05:19,010 --> 00:05:20,990
En ik ga voorbij
die terug naar faculteit

116
00:05:20,990 --> 00:05:23,160
van 5, is die op me te wachten.

117
00:05:23,160 --> 00:05:25,270
Faculteit van 5 is nu de actieve frame.

118
00:05:25,270 --> 00:05:30,700
Het gaat om 5 keer terug
faculteit van 4-- 5 tijden 24 of 120--

119
00:05:30,700 --> 00:05:32,722
en geeft deze waarde
terug naar hoofdgerecht, die heeft

120
00:05:32,722 --> 00:05:35,680
is heel geduldig te wachten op een
tijd onderaan de stapel.

121
00:05:35,680 --> 00:05:36,640
>> Het is waar het begon.

122
00:05:36,640 --> 00:05:37,670
Het maakte deze oproep.

123
00:05:37,670 --> 00:05:39,400
Verschillende frames nam aan de top.

124
00:05:39,400 --> 00:05:41,890
Het is nu weer boven op de stapel.

125
00:05:41,890 --> 00:05:43,450
Het is de actieve frame.

126
00:05:43,450 --> 00:05:47,810
Dus belangrijkste kreeg de waarde 120
terug van faculteit van 5.

127
00:05:47,810 --> 00:05:50,750
Het is al te wachten om
afdrukken die waarde.

128
00:05:50,750 --> 00:05:51,657
En dan is het gedaan.

129
00:05:51,657 --> 00:05:53,240
Er is niet meer regels code in de belangrijkste.

130
00:05:53,240 --> 00:05:56,800
Dus belangrijkste Het frame knalt off
de stapel, en we zijn klaar.

131
00:05:56,800 --> 00:05:58,992
>> En dat is hoe recursie werkt.

132
00:05:58,992 --> 00:06:00,200
Dat is hoe stack frames werken.

133
00:06:00,200 --> 00:06:03,120
Die functie oproepen
dat voorheen gebeurde

134
00:06:03,120 --> 00:06:06,620
zijn gewoon op pauze, wachtend
voor de latere oproepen

135
00:06:06,620 --> 00:06:12,050
tot finish zodat ze het actief worden
kaderen en afmaken wat ze moeten doen.

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

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

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