1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Om te verstaan
rekursie, moet jy

3
00:00:10,190 --> 00:00:13,820
eers verstaan ​​rekursie.

4
00:00:13,820 --> 00:00:17,280
Met rekursie in program ontwerp middel
dat jy self-referensiële

5
00:00:17,280 --> 00:00:18,570
definisies.

6
00:00:18,570 --> 00:00:21,520
Rekursiewe data strukture, byvoorbeeld,
is data strukture wat

7
00:00:21,520 --> 00:00:23,990
sluit hulself in
hul definisies.

8
00:00:23,990 --> 00:00:27,160
Maar vandag gaan ons om te fokus
op rekursiewe funksies.

9
00:00:27,160 --> 00:00:31,160
>> Onthou dat funksies neem insette,
argumente en terugkeer 'n waarde as hul

10
00:00:31,160 --> 00:00:34,480
uitset verteenwoordig deur
hierdie diagram hier.

11
00:00:34,480 --> 00:00:38,060
Ons sal dink van die boks as die liggaam van
die funksie, wat die stel van

12
00:00:38,060 --> 00:00:42,340
instruksies wat interpreteer die
insette en gee 'n uitset.

13
00:00:42,340 --> 00:00:45,660
Neem 'n nader kyk binne-in die liggaam van
die funksie kan oproepe om te openbaar

14
00:00:45,660 --> 00:00:47,430
ander funksies.

15
00:00:47,430 --> 00:00:51,300
Neem hierdie eenvoudige funksie, cat, wat
neem 'n enkele string as invoer en

16
00:00:51,300 --> 00:00:54,630
afdrukke hoeveel letters
dat string het.

17
00:00:54,630 --> 00:00:58,490
Die funksie StrLen vir string lengte,
genoem word, waarvan die opbrengs is

18
00:00:58,490 --> 00:01:01,890
nodig is vir die oproep te printf.

19
00:01:01,890 --> 00:01:05,770
>> Nou, wat maak 'n rekursiewe funksie
spesiaal maak, is dat dit 'n beroep self.

20
00:01:05,770 --> 00:01:09,610
Ons kan hierdie rekursiewe verteenwoordig
noem met hierdie oranje pyl

21
00:01:09,610 --> 00:01:11,360
herhaling terug na homself.

22
00:01:11,360 --> 00:01:15,630
Maar self die uitvoering weer sal slegs
'n ander rekursiewe oproep, en

23
00:01:15,630 --> 00:01:17,150
'n ander en 'n ander.

24
00:01:17,150 --> 00:01:19,100
Maar rekursiewe funksies
kan nie oneindig wees.

25
00:01:19,100 --> 00:01:23,490
Hulle het een of ander manier eindig, of jou
program sal vir ewig hardloop.

26
00:01:23,490 --> 00:01:27,680
>> So het ons 'n manier om te breek om uit te vind
uit die rekursiewe oproepe.

27
00:01:27,680 --> 00:01:29,900
Ons noem dit die basis geval.

28
00:01:29,900 --> 00:01:33,570
Wanneer die basis geval voorwaarde voldoen word,
die funksie gee sonder om

29
00:01:33,570 --> 00:01:34,950
'n ander rekursiewe oproep.

30
00:01:34,950 --> 00:01:39,610
Neem hierdie funksie, hi, 'n leemte funksie
dit neem 'n int n as insette.

31
00:01:39,610 --> 00:01:41,260
Die basis saak kom eerste.

32
00:01:41,260 --> 00:01:46,220
As n is minder as nul, druk bye en
ruil vir al die ander gevalle, die

33
00:01:46,220 --> 00:01:49,400
funksie sal druk hi en uit te voer
die rekursiewe oproep.

34
00:01:49,400 --> 00:01:53,600
Nog 'n oproep om die funksie hi met
'n decremented insette waarde.

35
00:01:53,600 --> 00:01:56,790
>> Nou, selfs al het ons druk hi, die
funksie sal nie beëindig totdat ons

36
00:01:56,790 --> 00:02:00,370
terugkeer om sy terugkeer tipe,
In hierdie geval is leeg.

37
00:02:00,370 --> 00:02:04,830
So vir elke n ander as die basis geval,
hierdie funksie hi sal terugkeer hi

38
00:02:04,830 --> 00:02:06,890
N minus 1.

39
00:02:06,890 --> 00:02:10,050
Aangesien hierdie funksie is nietig al is, ons
sal nie uitdruklik tik terugkeer hier.

40
00:02:10,050 --> 00:02:12,000
Ons sal net die funksie uit te voer.

41
00:02:12,000 --> 00:02:16,960
So roep hi (3) sal druk hi en
voer hi (2) wat voer hi (1) 'n

42
00:02:16,960 --> 00:02:20,560
wat voer hi (0), waar die
basis geval voorwaarde voldoen word.

43
00:02:20,560 --> 00:02:24,100
So hi (0) druk bye en opbrengste.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
So nou dat ons verstaan ​​die basiese beginsels van
rekursiewe funksies, wat hulle nodig het

46
00:02:28,690 --> 00:02:32,730
ten minste een basis geval, sowel as 'n
rekursiewe oproep, laat ons beweeg na 'n

47
00:02:32,730 --> 00:02:34,120
meer betekenisvolle voorbeeld.

48
00:02:34,120 --> 00:02:37,830
Een wat nie net terug
nietig maak nie saak wat.

49
00:02:37,830 --> 00:02:41,340
>> Kom ons neem 'n blik op die faktoriaal
werking gebruik mees algemeen in

50
00:02:41,340 --> 00:02:43,660
waarskynlikheid berekeninge.

51
00:02:43,660 --> 00:02:48,120
Faktoriaal van n is die produk van elke
positiewe heelgetal minder as

52
00:02:48,120 --> 00:02:49,400
en gelyk aan n.

53
00:02:49,400 --> 00:02:56,731
So faktoriaal vyf is 5 keer 4 keer
3 keer 2 keer 1 120 te gee.

54
00:02:56,731 --> 00:03:01,400
Vier faktoriaal is 4 keer 3 keer
2 keer 1 te gee 24.

55
00:03:01,400 --> 00:03:04,910
En dieselfde reël geld
aan enige positiewe heelgetal.

56
00:03:04,910 --> 00:03:08,670
>> So, hoe kan ons skryf 'n rekursiewe
funksie wat bereken die faktoriaal

57
00:03:08,670 --> 00:03:09,960
van 'n getal?

58
00:03:09,960 --> 00:03:14,700
Wel, ons sal moet identifiseer beide die
basis geval en die rekursiewe oproep.

59
00:03:14,700 --> 00:03:18,250
Die rekursiewe sal dieselfde wees
vir alle gevalle behalwe vir die basis

60
00:03:18,250 --> 00:03:21,420
geval, wat beteken dat ons sal moet
vind 'n patroon wat ons sal gee ons

61
00:03:21,420 --> 00:03:23,350
gewenste resultaat.

62
00:03:23,350 --> 00:03:30,270
>> Vir hierdie voorbeeld, sien hoe 5 faktoriaal
behels vermenigvuldig 4 deur 3 by 2 deur 1

63
00:03:30,270 --> 00:03:33,010
En daardie selfde vermenigvuldiging
is hier gevind, die

64
00:03:33,010 --> 00:03:35,430
definisie van 4 faktoriaal.

65
00:03:35,430 --> 00:03:39,810
So sien ons dat 5 faktoriaal is
net 5 keer 4 faktoriaal.

66
00:03:39,810 --> 00:03:43,360
Nou het hierdie patroon van toepassing
4 faktoriaal asook?

67
00:03:43,360 --> 00:03:44,280
Ja.

68
00:03:44,280 --> 00:03:49,120
Ons sien dat 4 faktoriaal bevat die
vermenigvuldiging 3 keer 2 keer 1, die

69
00:03:49,120 --> 00:03:51,590
selfde definisie as 3 faktoriaal.

70
00:03:51,590 --> 00:03:56,950
So 4 faktoriaal is gelyk aan 4 keer 3
faktoriaal, en so aan en so voort ons

71
00:03:56,950 --> 00:04:02,170
patroon stokke tot 1 faktoriaal, wat
per definisie is gelyk aan 1.

72
00:04:02,170 --> 00:04:04,950
>> Daar is geen ander positiewe
heelgetalle gelaat.

73
00:04:04,950 --> 00:04:07,870
So het ons die patroon vir
ons rekursiewe oproep.

74
00:04:07,870 --> 00:04:13,260
n faktoriale is gelyk aan n keer
die faktoriaal van n minus 1.

75
00:04:13,260 --> 00:04:14,370
En ons basis geval?

76
00:04:14,370 --> 00:04:17,370
Dit sal net ons definisie
1 faktoriaal.

77
00:04:17,370 --> 00:04:19,995
>> So nou kan ons aanbeweeg na skriftelike
kode vir die funksie.

78
00:04:19,995 --> 00:04:24,110
Vir die basis geval is, sal ons die
voorwaarde n gelyk gelykes 1, waar

79
00:04:24,110 --> 00:04:25,780
ons sal terugkeer 1.

80
00:04:25,780 --> 00:04:29,280
Dan beweeg op die rekursiewe oproep,
ons sal terugkeer n keer die

81
00:04:29,280 --> 00:04:32,180
faktoriaal van n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Kom ons toets hierdie ons nou.

83
00:04:33,590 --> 00:04:35,900
Kom ons probeer faktoriaal 4.

84
00:04:35,900 --> 00:04:39,420
Per ons funksie dit is gelyk
4 keer faktoriaal (3).

85
00:04:39,420 --> 00:04:43,040
Faktoriaal (3) is gelyk aan
3 keer faktoriaal (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriaal (2) is gelyk aan 2 keer
faktoriaal (1), wat terugkeer 1.

87
00:04:48,700 --> 00:04:52,490
Faktoriaal (2) keer terug nou 2 keer 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktoriaal (3) kan nou terugkeer
3 keer 2, 6.

89
00:04:55,960 --> 00:05:02,490
En uiteindelik, faktoriaal (4)
terug 4 keer 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> As jy enige probleme ondervind
met die rekursiewe oproep, voorgee dat

91
00:05:06,780 --> 00:05:09,660
die funksie werk reeds.

92
00:05:09,660 --> 00:05:13,450
Wat ek bedoel met dit is dat jy
vertrou jou rekursiewe oproepe om terug te keer

93
00:05:13,450 --> 00:05:15,100
die regte waardes.

94
00:05:15,100 --> 00:05:18,960
Byvoorbeeld, as ek weet dat
faktoriaal (5) is gelyk aan 5 keer

95
00:05:18,960 --> 00:05:24,870
faktoriaal (4), ek gaan om dit te vertrou
faktoriaal (4) gee my 24.

96
00:05:24,870 --> 00:05:28,510
Dink aan dit as 'n veranderlike, as jy
sal, asof jy reeds gedefinieer

97
00:05:28,510 --> 00:05:30,070
faktoriaal (4).

98
00:05:30,070 --> 00:05:33,850
So vir enige faktoriaal (n), is dit
die produk van N en

99
00:05:33,850 --> 00:05:35,360
die vorige faktoriaal.

100
00:05:35,360 --> 00:05:38,130
En hierdie vorige faktoriaal
verkry word deur die roeping

101
00:05:38,130 --> 00:05:41,330
faktoriaal van n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Nou, kyk of jy kan implementeer om 'n
n rekursiewe funksie jouself.

103
00:05:45,130 --> 00:05:50,490
Laai jou terminale, of run.cs50.net,
en skryf 'n funksie som

104
00:05:50,490 --> 00:05:54,770
dit neem 'n heelgetal n en gee die
som van alle opeenvolgende positiewe

105
00:05:54,770 --> 00:05:57,490
heelgetalle vanaf N tot 1.

106
00:05:57,490 --> 00:06:01,000
Ek het geskryf die somme van 'n paar
waardes om jou te help om ons.

107
00:06:01,000 --> 00:06:04,030
Eerstens, vind uit die
basis geval toestand.

108
00:06:04,030 --> 00:06:06,170
Dan, kyk na bedrag (5).

109
00:06:06,170 --> 00:06:09,270
Kan jy dit uit te druk in terme
van 'n ander som?

110
00:06:09,270 --> 00:06:11,290
Nou, wat oor die som (4)?

111
00:06:11,290 --> 00:06:15,630
Hoe kan jy druk som (4)
in terme van 'n ander som?

112
00:06:15,630 --> 00:06:19,655
>> Sodra jy 'n som (5) en som (4)
uitgedruk in terme van ander somme, sien

113
00:06:19,655 --> 00:06:22,970
As jy 'n kan identifiseer
patroon vir som (n).

114
00:06:22,970 --> 00:06:26,190
Indien nie, probeer om 'n paar ander getalle
en hul somme in

115
00:06:26,190 --> 00:06:28,410
terme van 'n ander getalle.

116
00:06:28,410 --> 00:06:31,930
Deur die identifisering van patrone vir diskrete
getalle, is jy goed op jou pad na

117
00:06:31,930 --> 00:06:34,320
die identifisering van die patroon vir enige n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursie is 'n baie kragtige instrument,
so dit is natuurlik nie beperk tot

119
00:06:38,040 --> 00:06:39,820
wiskundige funksies.

120
00:06:39,820 --> 00:06:44,040
Rekursie kan baie effektief gebruik word om
wanneer met bome byvoorbeeld.

121
00:06:44,040 --> 00:06:47,210
Check uit die kort op die bome vir 'n
meer deeglike hersiening, maar vir nou

122
00:06:47,210 --> 00:06:51,140
onthou dat binêre soek bome, in
besonder, is saamgestel uit nodes, elk

123
00:06:51,140 --> 00:06:53,820
met 'n waarde en twee knoop wysers.

124
00:06:53,820 --> 00:06:57,270
Gewoonlik word hierdie verteenwoordig deur die
voorgangernode met een lyn wat

125
00:06:57,270 --> 00:07:01,870
aan die linkerkant kind knoop en een
aan die regterkant kind knoop.

126
00:07:01,870 --> 00:07:04,510
Die struktuur van 'n binêre soek
boom leen hom goed

127
00:07:04,510 --> 00:07:05,940
'n rekursiewe soek.

128
00:07:05,940 --> 00:07:09,730
Die rekursiewe oproep gaan óf in die
linker-of die regterkant knoop, maar meer

129
00:07:09,730 --> 00:07:10,950
van daardie in die boom kort.

130
00:07:10,950 --> 00:07:15,690
>> Sê jy wil 'n operasie uit te voer op
elke enkele knoop in 'n binêre boom.

131
00:07:15,690 --> 00:07:17,410
Hoe kan jy te werk gaan dit?

132
00:07:17,410 --> 00:07:20,600
Wel, jy kan 'n rekursiewe skryf
funksie wat die operasie uitvoer

133
00:07:20,600 --> 00:07:24,450
op die voorgangernode en maak 'n rekursiewe
bel om dieselfde funksie,

134
00:07:24,450 --> 00:07:27,630
verby in die linker-en
regte kind nodes.

135
00:07:27,630 --> 00:07:31,650
Byvoorbeeld, hierdie funksie, cat, wat
verander die waarde van 'n gegewe knoop en

136
00:07:31,650 --> 00:07:33,830
al sy kinders 1.

137
00:07:33,830 --> 00:07:37,400
Die basis geval van 'n nul-knoop oorsake
die funksie om terug te keer, wat aandui

138
00:07:37,400 --> 00:07:41,290
dat daar nie enige nodes
links in daardie sub-boom.

139
00:07:41,290 --> 00:07:42,620
>> Kom ons loop deur dit.

140
00:07:42,620 --> 00:07:44,340
Die eerste ouer is 13.

141
00:07:44,340 --> 00:07:47,930
Ons verander die waarde tot 1, en dan bel
ons funksie aan die linkerkant asook

142
00:07:47,930 --> 00:07:49,600
as die regterkant.

143
00:07:49,600 --> 00:07:53,910
Die funksie, cat, is 'n beroep op die linker
sub-boom eerste, sodat die linker-knoop

144
00:07:53,910 --> 00:07:57,730
sal oorgeplaas word na 1 en cat sal
word 'n beroep op die knoop se kinders,

145
00:07:57,730 --> 00:08:01,900
eerste links en dan regs,
en so aan en so voort.

146
00:08:01,900 --> 00:08:05,630
En hulle vertel dat takke het nie
nog kinders so dieselfde proses

147
00:08:05,630 --> 00:08:09,700
sal voortgaan om vir die reg om kinders
totdat die hele boom se knope is

148
00:08:09,700 --> 00:08:11,430
oorgeplaas na 1.

149
00:08:11,430 --> 00:08:15,390
>> Soos jy kan sien, is jy nie beperk
om net een rekursiewe oproep.

150
00:08:15,390 --> 00:08:17,930
Net soveel as die werk gedoen te kry.

151
00:08:17,930 --> 00:08:21,200
Wat gebeur as jy 'n boom het waar elke
node het drie kinders,

152
00:08:21,200 --> 00:08:23,100
Links, middel, en reg?

153
00:08:23,100 --> 00:08:24,886
Hoe sal jy cat wysig?

154
00:08:24,886 --> 00:08:25,860
Wel, eenvoudig.

155
00:08:25,860 --> 00:08:30,250
Net nog 'n rekursiewe oproep en
slaag in die middel knoop wyser.

156
00:08:30,250 --> 00:08:34,549
>> Rekursie is baie sterk en nie te
noem elegant, maar dit kan 'n wees

157
00:08:34,549 --> 00:08:38,010
moeilike konsep op die eerste, so wees
pasiënt en neem jou tyd.

158
00:08:38,010 --> 00:08:39,370
Begin met die basis geval.

159
00:08:39,370 --> 00:08:42,650
Dit is gewoonlik die maklikste om te identifiseer,
en dan kan jy die werk

160
00:08:42,650 --> 00:08:43,830
terug van daar af.

161
00:08:43,830 --> 00:08:46,190
Jy weet wat jy nodig het om te bereik jou
basis geval, sodat mag

162
00:08:46,190 --> 00:08:47,760
gee jou 'n paar wenke.

163
00:08:47,760 --> 00:08:53,120
Probeer om een ​​spesifieke geval in te druk
terme van ander gevalle, of in sub-stelle.

164
00:08:53,120 --> 00:08:54,700
>> Dankie vir jou kyk hierdie kort.

165
00:08:54,700 --> 00:08:58,920
Op die heel minste, nou kan jy
grappies soos hierdie te verstaan.

166
00:08:58,920 --> 00:09:01,250
My naam is Zamyla, en dit is cs50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Neem hierdie funksie, hi, 'n
leemte funksie wat '

169
00:09:07,170 --> 00:09:09,212
'n int, N, as insette.

170
00:09:09,212 --> 00:09:11,020
Die basis saak kom eerste.

171
00:09:11,020 --> 00:09:14,240
As n is minder as 0, druk
"Bye" en terugkeer.

172
00:09:14,240 --> 00:09:15,490