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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: As jy gesien het
die video op rekursie,

3
00:00:07,670 --> 00:00:10,170
die hele proses kan hê
was 'n bietjie magiese.

4
00:00:10,170 --> 00:00:10,930
Hoe werk dit?

5
00:00:10,930 --> 00:00:15,010
Hoe kan die funksies weet dat hulle
nodig om te wag en wag vir 'n ander waarde

6
00:00:15,010 --> 00:00:19,150
om terug te keer van 'n ander funksie
bel om die resultaat wat ons wil hê?

7
00:00:19,150 --> 00:00:22,550
>> Wel, die rede waarom hierdie werk is omdat
van iets wat bekend staan ​​as die oproep stapel.

8
00:00:22,550 --> 00:00:26,360
Wanneer jy 'n funksie, die
stelsel ter syde stel ruimte in die geheue

9
00:00:26,360 --> 00:00:28,120
vir daardie funksie om sy werk te doen.

10
00:00:28,120 --> 00:00:31,720
En ons hierdie stukke van die geheue noem
word opsy gesit vir elke funksie

11
00:00:31,720 --> 00:00:35,670
roep 'n stapel raam of 'n funksie raam.

12
00:00:35,670 --> 00:00:38,290
En as jy kan verwag,
hierdie stapel rame

13
00:00:38,290 --> 00:00:41,000
lewe op die stapel deel van die geheue.

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

15
00:00:43,960 --> 00:00:47,540
>> Meer as een funksie stapel raamwerk
kan bestaan ​​in die geheue op 'n gegewe tyd.

16
00:00:47,540 --> 00:00:51,240
As hoof noem 'n funksie te beweeg,
en skuif oproepe rigting,

17
00:00:51,240 --> 00:00:54,460
al drie funksies oop rame.

18
00:00:54,460 --> 00:00:57,350
Maar hulle het nie almal aktief rame.

19
00:00:57,350 --> 00:00:59,410
Hierdie rame word in 'n stapel.

20
00:00:59,410 --> 00:01:01,820
En die raam van die
mees onlangs genoem

21
00:01:01,820 --> 00:01:04,390
funksie is altyd op die top van die stapel.

22
00:01:04,390 --> 00:01:07,150
En dit is altyd die aktiewe raam.

23
00:01:07,150 --> 00:01:10,420
Daar is eintlik net een ooit
funksie wat aktief op 'n tyd.

24
00:01:10,420 --> 00:01:12,420
Dit is die een op die top van die stapel.

25
00:01:12,420 --> 00:01:17,620
>> Wanneer 'n funksie roep 'n ander
funksie, dit soort van druk pouse.

26
00:01:17,620 --> 00:01:20,590
Dit is 'n soort van op te hou, en wag.

27
00:01:20,590 --> 00:01:24,050
En 'n ander stapel raamwerk gestoot
op die stapel op die top van dit.

28
00:01:24,050 --> 00:01:26,150
En dit word die aktiewe raam.

29
00:01:26,150 --> 00:01:28,600
En dadelik het die raam
onder dit moet wag

30
00:01:28,600 --> 00:01:33,560
totdat dit weer die aktiewe raam
voordat dit sy werk kan hervat.

31
00:01:33,560 --> 00:01:35,870
Wanneer 'n funksie is
volledige en dit is gedoen,

32
00:01:35,870 --> 00:01:37,720
sy raam inloer die stapel.

33
00:01:37,720 --> 00:01:38,950
Dit is die terminologie.

34
00:01:38,950 --> 00:01:41,110
En dadelik het die raam
onder dit, soos ek het net gesê,

35
00:01:41,110 --> 00:01:42,880
word die nuwe aktiewe raam.

36
00:01:42,880 --> 00:01:45,960
>> En as dit 'n ander funksie noem,
dit gaan om weer te breek.

37
00:01:45,960 --> 00:01:49,290
Stapel raamwerk dat die nuwe funksie se wil
gestoot op die top van die stapel.

38
00:01:49,290 --> 00:01:50,650
Dit sal die werk te doen.

39
00:01:50,650 --> 00:01:52,100
Dit mag dalk af pop rug.

40
00:01:52,100 --> 00:01:55,630
En die ander funksie
onder dit weer kan hervat.

41
00:01:55,630 --> 00:02:00,080
>> So laat ons gaan deur middel van hierdie weer soek
die idee van die faktoriaal funksie

42
00:02:00,080 --> 00:02:03,070
dat ons omskryf in die
rekursie video te sien

43
00:02:03,070 --> 00:02:07,770
presies hoe die magic agter hierdie
rekursiewe proses is wat plaasvind.

44
00:02:07,770 --> 00:02:09,870
So dit is ons hele lêer, reg?

45
00:02:09,870 --> 00:02:14,000
Ons gedefinieer twee
functions-- hoof- en werklikheid.

46
00:02:14,000 --> 00:02:15,980
En soos ons kan verwag,
enige C program gaan

47
00:02:15,980 --> 00:02:18,470
om te begin by die eerste reël van die belangrikste.

48
00:02:18,470 --> 00:02:21,660
>> So skep ons 'n nuwe stapel raamwerk vir die hoof.

49
00:02:21,660 --> 00:02:23,320
En dit gaan om te begin hardloop.

50
00:02:23,320 --> 00:02:25,270
Main oproepe printf.

51
00:02:25,270 --> 00:02:29,390
En printf gaan
druk faktoriaal van 5.

52
00:02:29,390 --> 00:02:31,440
Wel, beteken dit nie weet
wat faktoriaal van 5 is,

53
00:02:31,440 --> 00:02:35,620
en so hierdie oproep is reeds
afhangende van 'n ander funksie oproep.

54
00:02:35,620 --> 00:02:37,270
So belangrikste gaan reg daar breek.

55
00:02:37,270 --> 00:02:39,103
Ek gaan verlaat sy
arrow reg daar, kleur

56
00:02:39,103 --> 00:02:41,360
dit dieselfde kleur as die
stapel raam op regs,

57
00:02:41,360 --> 00:02:47,720
aan te dui dat hoof gaan vries
hier terwyl faktoriaal van 5 genoem word.

58
00:02:47,720 --> 00:02:49,300
>> So faktoriaal van 5 genoem word.

59
00:02:49,300 --> 00:02:53,160
En dit gaan om te begin by die heel
begin van die faktoriaal funksie.

60
00:02:53,160 --> 00:02:55,440
Dit vra die vraag ek gelyk aan 1?

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

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

63
00:02:57,410 --> 00:03:01,110
So dit gaan om af te gaan om
die ander kant, terugkeer N tye

64
00:03:01,110 --> 00:03:02,990
faktoriaal van N minus 1.

65
00:03:02,990 --> 00:03:03,490
Wel, OK.

66
00:03:03,490 --> 00:03:07,070
>> So nou, faktoriaal van 5 is
afhangende van 'n ander oproep

67
00:03:07,070 --> 00:03:09,740
om faktoriaal, verby
in 4 as die parameter.

68
00:03:09,740 --> 00:03:14,210
En so het die faktoriaal van
5 raam, wat rooi raam,

69
00:03:14,210 --> 00:03:17,160
gaan reg daar te vries
op daardie lyn Ek het aangedui

70
00:03:17,160 --> 00:03:21,914
en wag vir faktoriaal van 4 te voltooi
wat dit nodig het om dit te doen nie, dan is dit

71
00:03:21,914 --> 00:03:23,330
kan die aktiewe raam weer '.

72
00:03:23,330 --> 00:03:26,890
>> So faktoriaal van 4 begin by
die begin van faktoriaal.

73
00:03:26,890 --> 00:03:28,556
Is gelyk aan 4 1?

74
00:03:28,556 --> 00:03:30,180
Nee, so dit gaan om dieselfde ding te doen.

75
00:03:30,180 --> 00:03:31,590
Dit gaan om af te gaan die ander tak.

76
00:03:31,590 --> 00:03:33,240
Dit gaan die lyn van die kode te kry.

77
00:03:33,240 --> 00:03:35,710
OK, ek gaan vier keer terug.

78
00:03:35,710 --> 00:03:41,270
O, faktoriaal van 3-- so faktoriaal van
4 hang af van faktoriaal van 3 afwerking.

79
00:03:41,270 --> 00:03:43,055
>> En so is dit nodig om faktoriaal van 3 noem.

80
00:03:43,055 --> 00:03:45,180
En dit is nou eers deurgaan
dieselfde proses weer.

81
00:03:45,180 --> 00:03:48,200
Dit begin deur, kry hier.

82
00:03:48,200 --> 00:03:50,980
Faktoriaal van 3 hang
op faktoriaal van 1.

83
00:03:50,980 --> 00:03:53,750
So faktoriaal van 2 begin, kry hier.

84
00:03:53,750 --> 00:03:56,310
Dit hang af van faktoriaal van 1.

85
00:03:56,310 --> 00:03:57,430
Faktoriaal van 1 begin.

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

87
00:03:57,650 --> 00:03:59,775
So nou, is ons om
iewers interessante, reg?

88
00:03:59,775 --> 00:04:02,190
So nou, 1 is gelyk aan 1.

89
00:04:02,190 --> 00:04:05,130
En so het ons terug 1.

90
00:04:05,130 --> 00:04:06,770
Op hierdie punt, is ons terug.

91
00:04:06,770 --> 00:04:07,880
Die funksie gedoen.

92
00:04:07,880 --> 00:04:11,140
Dit is gedrag is-- daar
niks anders om dit te doen nie,

93
00:04:11,140 --> 00:04:17,006
en so die stapel raamwerk vir
faktoriaal van 1 verskyn het.

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

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

96
00:04:19,480 --> 00:04:23,370
En nou, faktoriaal van 2, wat
was die raam onmiddellik daaronder

97
00:04:23,370 --> 00:04:26,160
in die stapel, word die aktiewe raam.

98
00:04:26,160 --> 00:04:29,030
>> En dit kan optel
presies waar dit opgehou het.

99
00:04:29,030 --> 00:04:32,240
Dit is al vir 'n faktoriaal wag
van 1 tot sy werk te volbring.

100
00:04:32,240 --> 00:04:33,610
Dit het nou klaar.

101
00:04:33,610 --> 00:04:35,510
En so hier is ons.

102
00:04:35,510 --> 00:04:38,080
>> Faktoriaal van 1 teruggekeer 'n waarde van 1.

103
00:04:38,080 --> 00:04:42,430
So faktoriaal van 2 blikkie
sê terugkeer 2 keer 1.

104
00:04:42,430 --> 00:04:43,680
Sy werk is nou gedoen.

105
00:04:43,680 --> 00:04:49,110
Dit teruggekeer 2 tot faktoriaal
3, wat wag vir dit.

106
00:04:49,110 --> 00:04:53,370
Faktoriaal van 3 is nou die top raam,
die aktiewe raam in die stapel.

107
00:04:53,370 --> 00:04:58,617
En so is dit sê, OK, goed, ek gaan
3 keer 2, wat is 6 keer.

108
00:04:58,617 --> 00:05:00,700
En ek gaan om te gee wat
waardeer terug na faktoriaal

109
00:05:00,700 --> 00:05:03,430
van 4, het wat vir my gewag.

110
00:05:03,430 --> 00:05:04,500
Ek is klaar.

111
00:05:04,500 --> 00:05:09,410
Faktoriaal van 3 verskyn uit die stapel, en
faktoriaal van 4 is nou die aktiewe raam.

112
00:05:09,410 --> 00:05:13,510
>> 4 sê, OK, ek gaan 4 keer terug
die faktoriaal van 3, wat ses was.

113
00:05:13,510 --> 00:05:15,980
Dit was van die waarde wat
faktoriaal van 3 teruggekeer.

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

115
00:05:19,010 --> 00:05:20,990
En ek gaan om te slaag
wat terug na faktoriaal

116
00:05:20,990 --> 00:05:23,160
van 5, het wat vir my gewag.

117
00:05:23,160 --> 00:05:25,270
Faktoriaal van 5 is nou die aktiewe raam.

118
00:05:25,270 --> 00:05:30,700
Dit gaan tot 5 keer terug
faktoriaal van 4-- 5 keer 24 of 120--

119
00:05:30,700 --> 00:05:32,722
en gee wat waarde
Terug na die hoof, wat het

120
00:05:32,722 --> 00:05:35,680
is baie geduldig wag vir 'n
lang tyd aan die onderkant van die stapel.

121
00:05:35,680 --> 00:05:36,640
>> Dit is waar dit begin het.

122
00:05:36,640 --> 00:05:37,670
Dit het hierdie oproep.

123
00:05:37,670 --> 00:05:39,400
Verskeie rame oorgeneem by die top.

124
00:05:39,400 --> 00:05:41,890
Dit is nou weer terug op die top van die stapel.

125
00:05:41,890 --> 00:05:43,450
Dit is die aktiewe raam.

126
00:05:43,450 --> 00:05:47,810
So het die hoof waarde 120
terug van faktoriaal van 5.

127
00:05:47,810 --> 00:05:50,750
Dit is al wat wag om
druk wat waarde.

128
00:05:50,750 --> 00:05:51,657
En dan is dit gedoen.

129
00:05:51,657 --> 00:05:53,240
Daar is nie meer reëls van die kode in die belangrikste.

130
00:05:53,240 --> 00:05:56,800
So belangrikste se raam verskyn af
die stapel, en ons gedoen het.

131
00:05:56,800 --> 00:05:58,992
>> En dit is hoe rekursie werk.

132
00:05:58,992 --> 00:06:00,200
Dit is hoe stapel rame werk.

133
00:06:00,200 --> 00:06:03,120
Diegene funksie oproepe
wat voorheen gebeur het

134
00:06:03,120 --> 00:06:06,620
is net op die pouse, en wag
vir die daaropvolgende oproepe

135
00:06:06,620 --> 00:06:12,050
te voltooi, sodat hulle kan die aktief
raam en voltooi wat hulle nodig het om te doen.

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

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

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