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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Om te begrijpen
recursie, moet u

3
00:00:10,190 --> 00:00:13,820
eerst begrijpen recursie.

4
00:00:13,820 --> 00:00:17,280
Met recursie in programma-ontwerp middelen
dat je zelf-referentiële

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

6
00:00:18,570 --> 00:00:21,520
Recursieve datastructuren, bijvoorbeeld
data structuren zijn

7
00:00:21,520 --> 00:00:23,990
behoren zich in
hun definities.

8
00:00:23,990 --> 00:00:27,160
Maar vandaag, we gaan richten
op recursieve functies.

9
00:00:27,160 --> 00:00:31,160
>> Bedenk dat functies nemen ingangen,
argumenten, en terug een waarde als hun

10
00:00:31,160 --> 00:00:34,480
uitgang vertegenwoordigers
dit schema hier.

11
00:00:34,480 --> 00:00:38,060
We bedenken de doos als het lichaam van
de functie, bevat de set van

12
00:00:38,060 --> 00:00:42,340
aanwijzingen dat de interpretatie van de
input en een output geven.

13
00:00:42,340 --> 00:00:45,660
Het nemen van een kijkje in het lichaam van
de functie zou kunnen oproepen om te onthullen

14
00:00:45,660 --> 00:00:47,430
andere functies.

15
00:00:47,430 --> 00:00:51,300
Neem deze eenvoudige functie, foo, dat
neemt een enkele string als input en

16
00:00:51,300 --> 00:00:54,630
prints hoeveel letters
die string heeft.

17
00:00:54,630 --> 00:00:58,490
De functie strlen, voor strijkkwartet lengte,
wordt genoemd, waarvan de uitvoer

18
00:00:58,490 --> 00:01:01,890
nodig is voor de oproep om printf.

19
00:01:01,890 --> 00:01:05,770
>> Nu, wat maakt een recursieve functie
bijzonder is dat het zelf noemt.

20
00:01:05,770 --> 00:01:09,610
We kunnen dit recursieve vertegenwoordigen
bellen met deze oranje pijl

21
00:01:09,610 --> 00:01:11,360
looping terug naar zichzelf.

22
00:01:11,360 --> 00:01:15,630
Maar zich opnieuw uitvoeren alleen zal
andere recursieve bellen, en

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

24
00:01:17,150 --> 00:01:19,100
Maar recursieve functies
kan niet oneindig.

25
00:01:19,100 --> 00:01:23,490
Ze moeten een of andere manier te beëindigen, of uw
programma zal voor altijd draaien.

26
00:01:23,490 --> 00:01:27,680
>> Dus moeten we een manier om te breken vinden
uit de recursieve oproepen.

27
00:01:27,680 --> 00:01:29,900
We noemen dit het nulalternatief.

28
00:01:29,900 --> 00:01:33,570
Wanneer de base case voorwaarde is voldaan,
retourneert de functie zonder

29
00:01:33,570 --> 00:01:34,950
andere recursieve aanroep.

30
00:01:34,950 --> 00:01:39,610
Neem deze functie, hi, een leegte functie
dat neemt een int n als invoer.

31
00:01:39,610 --> 00:01:41,260
Het nulalternatief komt eerst.

32
00:01:41,260 --> 00:01:46,220
Als n kleiner is dan nul, print-bye en
terug Voor alle andere gevallen, de

33
00:01:46,220 --> 00:01:49,400
functie wordt afgedrukt hi en uitvoeren
de recursieve aanroep.

34
00:01:49,400 --> 00:01:53,600
Ander gesprek om de functie hi met
een verlaagd invoerwaarde.

35
00:01:53,600 --> 00:01:56,790
>> Nu, hoewel we drukken hi, de
functie zal niet eindigen totdat we

36
00:01:56,790 --> 00:02:00,370
terug zijn return type,
in dit geval vervallen.

37
00:02:00,370 --> 00:02:04,830
Dus voor elke n ander dan het basisscenario,
deze functie hi zal terugkeren hi

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

39
00:02:06,890 --> 00:02:10,050
Omdat deze functie is nietig hoewel, we
zal hier niet expliciet return type.

40
00:02:10,050 --> 00:02:12,000
We zullen gewoon de functie uit te voeren.

41
00:02:12,000 --> 00:02:16,960
Dus bellen hi (3) wordt afgedrukt hi en
voeren hi (2), die hi voert (1) een

42
00:02:16,960 --> 00:02:20,560
die hi uitvoert (0), waarbij de
base case voorwaarde wordt voldaan.

43
00:02:20,560 --> 00:02:24,100
Dus hi (0) drukt bye en rendement.

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

45
00:02:24,990 --> 00:02:28,690
Dus nu dat we begrijpen de basis van
recursieve functies, die ze nodig hebben

46
00:02:28,690 --> 00:02:32,730
minstens een referentiemodel en een
recursieve aanroep, laten we overgaan tot een

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

48
00:02:34,120 --> 00:02:37,830
Een die niet alleen terug
vervalt er ook gebeurt.

49
00:02:37,830 --> 00:02:41,340
>> Laten we eens een kijkje nemen op de faculteit
operatie gebruikt meestal in

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

51
00:02:43,660 --> 00:02:48,120
Faculteit van n is het product van elke
positief geheel getal kleiner dan

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

53
00:02:49,400 --> 00:02:56,731
Dus faculteit vijf is 5 keer 4 keer
3 maal 2 maal 1 geven 120.

54
00:02:56,731 --> 00:03:01,400
Vier faculteit is 4 keer 3 keer
2 maal 1 tot 24 geven.

55
00:03:01,400 --> 00:03:04,910
En hetzelfde geldt
elk positief geheel getal.

56
00:03:04,910 --> 00:03:08,670
>> Dus hoe kunnen we schrijven een recursieve
functie die de faculteit berekent

57
00:03:08,670 --> 00:03:09,960
van een nummer?

58
00:03:09,960 --> 00:03:14,700
Nou, we moeten identificeren zowel de
base case en de recursieve aanroep.

59
00:03:14,700 --> 00:03:18,250
De recursieve aanroep zal hetzelfde zijn
voor alle gevallen, behalve de basis

60
00:03:18,250 --> 00:03:21,420
geval, wat betekent dat we zullen moeten
vind een patroon dat ons zal geven onze

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

62
00:03:23,350 --> 00:03:30,270
>> Voor dit voorbeeld zien hoe 5 faculteit
gaat vermenigvuldigen 4 bij 3 bij 2 bij 1

63
00:03:30,270 --> 00:03:33,010
En diezelfde vermenigvuldiging
is hier te vinden, de

64
00:03:33,010 --> 00:03:35,430
definitie van 4 factorial.

65
00:03:35,430 --> 00:03:39,810
Zo zien we dat 5 faculteit is
slechts 5 keer 4 faculteit.

66
00:03:39,810 --> 00:03:43,360
Nu heeft dit patroon van toepassing
4 faculteit ook?

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

68
00:03:44,280 --> 00:03:49,120
We zien dat 4 faculteit bevat het
vermenigvuldiging 3 maal 2 maal 1, de

69
00:03:49,120 --> 00:03:51,590
zeer dezelfde definitie als 3 faculteit.

70
00:03:51,590 --> 00:03:56,950
Dus 4 faculteit is gelijk aan 4 maal 3
faculteit, en zo verder en zo voort onze

71
00:03:56,950 --> 00:04:02,170
patroon stokken tot 1 faculteit, die
per definitie gelijk is aan 1.

72
00:04:02,170 --> 00:04:04,950
>> Er is geen andere positieve
getallen links.

73
00:04:04,950 --> 00:04:07,870
Dus hebben we het patroon voor
onze recursieve aanroep.

74
00:04:07,870 --> 00:04:13,260
n faculteit is gelijk aan n keer
de faculteit van n minus 1.

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

76
00:04:14,370 --> 00:04:17,370
Dat zal alleen onze definitie
1 factorial.

77
00:04:17,370 --> 00:04:19,995
>> Dus nu kunnen we overgaan tot het schrijven
code voor de functie.

78
00:04:19,995 --> 00:04:24,110
Voor het nulalternatief, moeten we de
voorwaarde n gelijk gelijken 1, waar

79
00:04:24,110 --> 00:04:25,780
we zullen 1 terugkeren.

80
00:04:25,780 --> 00:04:29,280
Dan verplaatsen naar de recursieve aanroep,
we zullen n keer terug de

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

82
00:04:32,180 --> 00:04:33,590
>> Nu laten we dit testen onze.

83
00:04:33,590 --> 00:04:35,900
Laten we proberen faculteit 4.

84
00:04:35,900 --> 00:04:39,420
Per onze functie het gelijk
4 keer factorial (3).

85
00:04:39,420 --> 00:04:43,040
Faculteit (3) is gelijk aan
3 keer factorial (2).

86
00:04:43,040 --> 00:04:48,700
Faculteit (2) is gelijk aan 2 keer
faculteit (1), die terugkeert 1.

87
00:04:48,700 --> 00:04:52,490
Faculteit (2) geeft nu 2 maal 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faculteit (3) kan nu terugkeren
3 maal 2, 6.

89
00:04:55,960 --> 00:05:02,490
En tenslotte, faculteit (4)
geeft 4 keer 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Als je ondervindt enige moeite
met de recursieve aanroep, doen alsof

91
00:05:06,780 --> 00:05:09,660
de functie werkt reeds.

92
00:05:09,660 --> 00:05:13,450
Wat ik bedoel is dat je moet
vertrouw op je recursieve oproepen om terug te keren

93
00:05:13,450 --> 00:05:15,100
de juiste waarden.

94
00:05:15,100 --> 00:05:18,960
Bijvoorbeeld, als ik weet dat
faculteit (5) is gelijk aan 5 keer

95
00:05:18,960 --> 00:05:24,870
faculteit (4), ga ik ervan uit dat
faculteit (4) zal me 24 geven.

96
00:05:24,870 --> 00:05:28,510
Zie het als een variabele, als je
zal, alsof je al gedefinieerd

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

98
00:05:30,070 --> 00:05:33,850
Dus voor elke faculteit (n), het
het product van n en

99
00:05:33,850 --> 00:05:35,360
de vorige faculteit.

100
00:05:35,360 --> 00:05:38,130
En dit vorige faculteit
wordt verkregen door te bellen naar

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

102
00:05:41,330 --> 00:05:45,130
>> Nu, kijk of je kunt implementeren van een
recursieve functie zelf.

103
00:05:45,130 --> 00:05:50,490
Laad je terminal, of run.cs50.net,
en schrijf een functie sum

104
00:05:50,490 --> 00:05:54,770
dat neemt een geheel getal n en geeft de
som van alle opeenvolgende positieve

105
00:05:54,770 --> 00:05:57,490
gehele getallen van 1 tot n.

106
00:05:57,490 --> 00:06:01,000
Ik heb geschreven uit de sommen van sommige
waarden om u te helpen ons.

107
00:06:01,000 --> 00:06:04,030
Eerste, figuur uit de
base case conditie.

108
00:06:04,030 --> 00:06:06,170
Dan, kijk naar sum (5).

109
00:06:06,170 --> 00:06:09,270
Kun je het uitdrukken in termen
ander som?

110
00:06:09,270 --> 00:06:11,290
Nu, hoe zit sum (4)?

111
00:06:11,290 --> 00:06:15,630
Hoe kun je uitdrukken sum (4)
in termen van een ander bedrag?

112
00:06:15,630 --> 00:06:19,655
>> Zodra u een bedrag (5) en sum (4)
uitgedrukt in termen van andere bedragen, zie

113
00:06:19,655 --> 00:06:22,970
als je kunt identificeren van een
patroon voor sum (n).

114
00:06:22,970 --> 00:06:26,190
Zo niet, probeer dan een paar andere nummers
en uiten hun sommen in

115
00:06:26,190 --> 00:06:28,410
termen van een ander nummer.

116
00:06:28,410 --> 00:06:31,930
Door het identificeren van patronen voor discrete
nummers, je bent goed op weg naar

117
00:06:31,930 --> 00:06:34,320
het identificeren van de patroon voor elke n.

118
00:06:34,320 --> 00:06:38,040
>> Recursie is echt een krachtig hulpmiddel,
dus natuurlijk is het niet beperkt tot

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

120
00:06:39,820 --> 00:06:44,040
Recursie kan zeer effectief worden gebruikt
bij het omgaan met bomen bijvoorbeeld.

121
00:06:44,040 --> 00:06:47,210
Bekijk de korte op bomen voor een
meer grondige herziening, maar voor nu

122
00:06:47,210 --> 00:06:51,140
herinneren dat binary search bomen,
bijzonder zijn opgebouwd uit knooppunten die elk

123
00:06:51,140 --> 00:06:53,820
met een waarde en twee knooppunt pointers.

124
00:06:53,820 --> 00:06:57,270
Meestal wordt dit weergegeven door de
parent node met een lijn wijzend

125
00:06:57,270 --> 00:07:01,870
naar links kind knooppunt en een
rechts onderliggende node.

126
00:07:01,870 --> 00:07:04,510
De structuur van een binary search
boom leent zich goed

127
00:07:04,510 --> 00:07:05,940
een recursieve zoekopdracht.

128
00:07:05,940 --> 00:07:09,730
De recursieve aanroep ofwel passen in de
links of rechts knooppunt, maar

129
00:07:09,730 --> 00:07:10,950
van dat de boom kort.

130
00:07:10,950 --> 00:07:15,690
>> Stel dat je wilt om een ​​operatie uit te voeren op
elk knooppunt in een binaire boom.

131
00:07:15,690 --> 00:07:17,410
Hoe zou je over dat?

132
00:07:17,410 --> 00:07:20,600
Nou, je kan een recursieve schrijven
functie die de operatie uitvoert

133
00:07:20,600 --> 00:07:24,450
op het bovenliggende knooppunt en maakt een recursieve
roepen om dezelfde functie,

134
00:07:24,450 --> 00:07:27,630
passeren in de linker en
rechts kind knooppunten.

135
00:07:27,630 --> 00:07:31,650
Bijvoorbeeld, deze functie foo, dat
verandert de waarde van een bepaald knooppunt en

136
00:07:31,650 --> 00:07:33,830
al zijn kinderen 1.

137
00:07:33,830 --> 00:07:37,400
Het basisscenario van een null knooppunt oorzaken
de functie weer te geven

138
00:07:37,400 --> 00:07:41,290
dat er geen knopen
links in die sub-boom.

139
00:07:41,290 --> 00:07:42,620
>> Laten we er doorheen lopen.

140
00:07:42,620 --> 00:07:44,340
De eerste ouder is 13.

141
00:07:44,340 --> 00:07:47,930
We veranderen de waarde op 1, en dan bellen
onze functie links en

142
00:07:47,930 --> 00:07:49,600
als rechts.

143
00:07:49,600 --> 00:07:53,910
De functie, foo, wordt een beroep op de linker
sub-boom voor het eerst, dus de linker knooppunt

144
00:07:53,910 --> 00:07:57,730
zullen worden toegewezen aan 1 en foo zal
worden opgeroepen kinderen dat knooppunt,

145
00:07:57,730 --> 00:08:01,900
eerst links en dan rechts,
en zo verder en zo voort.

146
00:08:01,900 --> 00:08:05,630
En vertel hen dat takken niet hebben
meer kinderen dus hetzelfde proces

147
00:08:05,630 --> 00:08:09,700
zal blijven voor de juiste kinderen
tot knooppunten van de hele boom zijn

148
00:08:09,700 --> 00:08:11,430
toegewezen aan 1.

149
00:08:11,430 --> 00:08:15,390
>> Zoals je kunt zien, bent u niet beperkt
slechts een recursieve aanroep.

150
00:08:15,390 --> 00:08:17,930
Net zoveel als zal de klus te klaren.

151
00:08:17,930 --> 00:08:21,200
Wat als je een boom had waar elke
knooppunt had drie kinderen,

152
00:08:21,200 --> 00:08:23,100
Links, midden en rechts?

153
00:08:23,100 --> 00:08:24,886
Hoe zou u foo bewerken?

154
00:08:24,886 --> 00:08:25,860
Nou, simpel.

155
00:08:25,860 --> 00:08:30,250
Voeg gewoon nog een recursieve aanroep en
passeren in het midden knooppunt aanwijzer.

156
00:08:30,250 --> 00:08:34,549
>> Recursie is zeer krachtig en niet te
noemen elegant, maar het kan een

157
00:08:34,549 --> 00:08:38,010
moeilijk concept op het eerste, dus wees
patiënt en neem de tijd.

158
00:08:38,010 --> 00:08:39,370
Begin met het nulalternatief.

159
00:08:39,370 --> 00:08:42,650
Het is meestal het makkelijkst te identificeren
en dan kun je werken

160
00:08:42,650 --> 00:08:43,830
achteruit vanaf daar.

161
00:08:43,830 --> 00:08:46,190
Je weet dat je nodig hebt om te bereiken uw
base case, zodat de macht

162
00:08:46,190 --> 00:08:47,760
geven je een paar tips.

163
00:08:47,760 --> 00:08:53,120
Proberen om een ​​specifiek geval te drukken in
termen van andere gevallen, of in sub-sets.

164
00:08:53,120 --> 00:08:54,700
>> Bedankt voor het kijken deze korte.

165
00:08:54,700 --> 00:08:58,920
Op zijn minst, nu kunt u
begrijpen grappen als deze.

166
00:08:58,920 --> 00:09:01,250
Mijn 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 deze functie, hi, een
leegte functie die neemt

169
00:09:07,170 --> 00:09:09,212
een int, n, als input.

170
00:09:09,212 --> 00:09:11,020
Het nulalternatief komt eerst.

171
00:09:11,020 --> 00:09:14,240
Als n kleiner is dan 0, afdrukken
"Bye" en terugkeer.

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