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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: For at forstå
rekursion, skal du

3
00:00:10,190 --> 00:00:13,820
først forstå rekursion.

4
00:00:13,820 --> 00:00:17,280
Under rekursion i programmets design betyder
at du har selvrefererende

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

6
00:00:18,570 --> 00:00:21,520
Rekursive datastrukturer, for eksempel,
er datastrukturer,

7
00:00:21,520 --> 00:00:23,990
omfatte sig i
deres definitioner.

8
00:00:23,990 --> 00:00:27,160
Men i dag, vi kommer til at fokusere
på rekursive funktioner.

9
00:00:27,160 --> 00:00:31,160
>> Husk på, at funktioner tager input,
argumenter, og returnerer en værdi som deres

10
00:00:31,160 --> 00:00:34,480
output repræsenteret ved
dette diagram her.

11
00:00:34,480 --> 00:00:38,060
Vi vil tænke på boksen som kroppen af
funktion, der indeholder sættet af

12
00:00:38,060 --> 00:00:42,340
instruktioner, der fortolker
input og giver et output.

13
00:00:42,340 --> 00:00:45,660
Tage et nærmere kig ind i kroppen af
funktionen kan afsløre opkald til

14
00:00:45,660 --> 00:00:47,430
andre funktioner samt.

15
00:00:47,430 --> 00:00:51,300
Tag denne enkle funktion, foo, at
tager en enkelt streng som input og

16
00:00:51,300 --> 00:00:54,630
prints, hvor mange breve
denne streng har.

17
00:00:54,630 --> 00:00:58,490
Funktionen strlen for streng længde,
kaldes, hvis produktion er

18
00:00:58,490 --> 00:01:01,890
kræves for opkaldet til printf.

19
00:01:01,890 --> 00:01:05,770
>> Nu, hvad der gør en rekursiv funktion
specielle er, at det kalder sig.

20
00:01:05,770 --> 00:01:09,610
Vi kan repræsentere denne rekursive
kalde med denne orange pil

21
00:01:09,610 --> 00:01:11,360
looping tilbage til sig selv.

22
00:01:11,360 --> 00:01:15,630
Men udfører selv igen kun vil
foretage endnu en rekursivt kald, og

23
00:01:15,630 --> 00:01:17,150
en anden og en anden.

24
00:01:17,150 --> 00:01:19,100
Men rekursive funktioner
kan ikke være uendelig.

25
00:01:19,100 --> 00:01:23,490
De skal ende med en eller anden måde, eller din
Programmet vil køre for evigt.

26
00:01:23,490 --> 00:01:27,680
>> Så vi er nødt til at finde en måde at bryde
ud af de rekursive kald.

27
00:01:27,680 --> 00:01:29,900
Vi kalder denne base case.

28
00:01:29,900 --> 00:01:33,570
Når basen sagen betingelse er opfyldt,
returnerer funktionen uden at foretage

29
00:01:33,570 --> 00:01:34,950
et rekursivt kald.

30
00:01:34,950 --> 00:01:39,610
Tag denne funktion, hej, en void funktion
der tager en int n som input.

31
00:01:39,610 --> 00:01:41,260
Basen sag kommer først.

32
00:01:41,260 --> 00:01:46,220
Hvis n er mindre end nul, print farvel og
tilbage For alle andre tilfælde

33
00:01:46,220 --> 00:01:49,400
funktion udskrives hi og udføre
rekursive kald.

34
00:01:49,400 --> 00:01:53,600
Et andet opkald til funktionen hi med
en dekrementeres inputværdi.

35
00:01:53,600 --> 00:01:56,790
>> Nu, selv om vi udskriver hej, det
Funktionen vil ikke opsige indtil vi

36
00:01:56,790 --> 00:02:00,370
returnere dens returtype,
i dette tilfælde ugyldig.

37
00:02:00,370 --> 00:02:04,830
Så for hver n andet end basisscenariet,
denne funktion hi vender hi

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

39
00:02:06,890 --> 00:02:10,050
Da denne funktion er ugyldig, selvom vi
vil ikke eksplicit skrive tilbagevenden her.

40
00:02:10,050 --> 00:02:12,000
Vi vil bare udføre funktionen.

41
00:02:12,000 --> 00:02:16,960
Så at kalde hi (3) udskrives hi og
udføre hi (2), som udfører hi (1) en

42
00:02:16,960 --> 00:02:20,560
som udfører hi (0), hvor
base case betingelse er opfyldt.

43
00:02:20,560 --> 00:02:24,100
Så hej (0) udskriver farvel og afkast.

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

45
00:02:24,990 --> 00:02:28,690
Så nu, at vi forstår det grundlæggende i
rekursive funktioner, som de har brug for

46
00:02:28,690 --> 00:02:32,730
mindst en base sag samt en
rekursivt kald, lad os gå videre til en

47
00:02:32,730 --> 00:02:34,120
mere meningsfuld eksempel.

48
00:02:34,120 --> 00:02:37,830
En, der ikke bare vender tilbage
ugyldig uanset hvad.

49
00:02:37,830 --> 00:02:41,340
>> Lad os tage et kig på fakulteten
operation mest almindeligt i

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

51
00:02:43,660 --> 00:02:48,120
Factorial n er produktet af hver
positivt heltal mindre end

52
00:02:48,120 --> 00:02:49,400
og lige til n.

53
00:02:49,400 --> 00:02:56,731
Så factorial fem er 5 gange 4 gange
3 gange 2 gange 1 for at give 120.

54
00:02:56,731 --> 00:03:01,400
Fire factorial er 4 gange 3 gange
2 gange 1 for at give 24.

55
00:03:01,400 --> 00:03:04,910
Og det samme gælder
til et positivt heltal.

56
00:03:04,910 --> 00:03:08,670
>> Så hvordan kan vi skriver en rekursiv
funktion, der beregner fakultet

57
00:03:08,670 --> 00:03:09,960
af et nummer?

58
00:03:09,960 --> 00:03:14,700
Nå, vi bliver nødt til at identificere både
base case og rekursive kald.

59
00:03:14,700 --> 00:03:18,250
Den rekursive kald vil være den samme
for alle tilfælde med undtagelse af bunden

60
00:03:18,250 --> 00:03:21,420
tilfælde, hvilket betyder, at vi bliver nødt til at
finde et mønster, der vil give os vores

61
00:03:21,420 --> 00:03:23,350
ønskede resultat.

62
00:03:23,350 --> 00:03:30,270
>> For dette eksempel, se hvordan 5 factorial
består i at gange 4 til 3 med 2 af 1

63
00:03:30,270 --> 00:03:33,010
Og det samme multiplikation
findes her, den

64
00:03:33,010 --> 00:03:35,430
definition af 4 faktoriel.

65
00:03:35,430 --> 00:03:39,810
Så vi kan se, at 5 factorial er
kun 5 gange 4 fakultet.

66
00:03:39,810 --> 00:03:43,360
Nu gør dette mønster gælder
til 4 faktoriel så godt?

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

68
00:03:44,280 --> 00:03:49,120
Vi ser, at 4 factorial indeholder
multiplikation 3 gange 2 gange 1, den

69
00:03:49,120 --> 00:03:51,590
meget samme definition som 3 fakultet.

70
00:03:51,590 --> 00:03:56,950
Så 4 fakultet er lig med 4 gange 3
faktoriel, og så videre og så videre vores

71
00:03:56,950 --> 00:04:02,170
mønster stikker indtil 1. faktoriel, som
definition er lig med 1.

72
00:04:02,170 --> 00:04:04,950
>> Der er ingen andre positive
heltal venstre.

73
00:04:04,950 --> 00:04:07,870
Så vi har mønsteret for
vores rekursivt kald.

74
00:04:07,870 --> 00:04:13,260
n fakultet er lig med n gange
fakultet af n minus 1.

75
00:04:13,260 --> 00:04:14,370
Og vores base case?

76
00:04:14,370 --> 00:04:17,370
Det vil bare være vores definition
1 faktoriel.

77
00:04:17,370 --> 00:04:19,995
>> Så nu kan vi gå videre til at skrive
kode for funktionen.

78
00:04:19,995 --> 00:04:24,110
For basisscenariet, vil vi have det
betingelse n er lig med lig 1, hvor

79
00:04:24,110 --> 00:04:25,780
vi 1 tilbage.

80
00:04:25,780 --> 00:04:29,280
Så flytter ind på det rekursive kald,
vi vil vende tilbage n gange den

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

82
00:04:32,180 --> 00:04:33,590
>> Lad os nu teste dette vores.

83
00:04:33,590 --> 00:04:35,900
Lad os prøve factorial 4.

84
00:04:35,900 --> 00:04:39,420
Per vores funktion det er lig
til 4 gange factorial (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) er lig med
3 gange faktoreffekter (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) er lig med 2 gange
fakultet (1), som returnerer 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) returnerer nu 2 gange 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3), kan nu vende tilbage
3 gange 2, 6.

89
00:04:55,960 --> 00:05:02,490
Og endelig, fakultet (4)
returnerer 4 gange 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Hvis du støder på nogen problemer
med det rekursive kald, foregive, at

91
00:05:06,780 --> 00:05:09,660
funktionen fungerer allerede.

92
00:05:09,660 --> 00:05:13,450
Hvad jeg mener med dette er, at du skal
tillid til dine rekursive kald til at vende tilbage

93
00:05:13,450 --> 00:05:15,100
de rette værdier.

94
00:05:15,100 --> 00:05:18,960
For eksempel, hvis jeg ved, at
factorial (5) er lig med 5 gange

95
00:05:18,960 --> 00:05:24,870
fakultet (4), vil jeg tillid til, at
fakultet (4) vil give mig 24.

96
00:05:24,870 --> 00:05:28,510
Tænk på det som en variabel, hvis du
vil, som hvis du allerede defineret

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

98
00:05:30,070 --> 00:05:33,850
Så for enhver fakultet (n), er det
produktet af n og

99
00:05:33,850 --> 00:05:35,360
forrige faktorforsøg.

100
00:05:35,360 --> 00:05:38,130
Og denne tidligere factorial
opnås ved at kalde

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

102
00:05:41,330 --> 00:05:45,130
>> Nu, se om du kan gennemføre en
rekursiv funktion selv.

103
00:05:45,130 --> 00:05:50,490
Indlæse din terminal, eller run.cs50.net,
og skrive en sumfunktion

104
00:05:50,490 --> 00:05:54,770
der tager et heltal n og returnerer
summen af ​​alle på hinanden følgende positive

105
00:05:54,770 --> 00:05:57,490
heltal fra N til 1.

106
00:05:57,490 --> 00:06:01,000
Jeg har skrevet ud summerne af nogle
værdier til at hjælpe dig vores.

107
00:06:01,000 --> 00:06:04,030
Først finde ud af det
base case tilstand.

108
00:06:04,030 --> 00:06:06,170
Så se på sum (5).

109
00:06:06,170 --> 00:06:09,270
Kan du udtrykke det i form
anden sum?

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

111
00:06:11,290 --> 00:06:15,630
Hvordan kan du udtrykke sum (4)
i form af en anden sum?

112
00:06:15,630 --> 00:06:19,655
>> Når du har sum (5) og sum (4)
udtrykt i andre beløb, se

113
00:06:19,655 --> 00:06:22,970
hvis du kan identificere en
mønster for sum (n).

114
00:06:22,970 --> 00:06:26,190
Hvis ikke, så prøv et par andre numre
og udtrykke deres beløb i

115
00:06:26,190 --> 00:06:28,410
form af et andet tal.

116
00:06:28,410 --> 00:06:31,930
Ved at identificere mønstre for diskrete
numre, er du godt på vej til

117
00:06:31,930 --> 00:06:34,320
identificere mønsteret for enhver n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursion er en virkelig kraftfuldt værktøj,
så det er selvfølgelig ikke begrænset til

119
00:06:38,040 --> 00:06:39,820
matematiske funktioner.

120
00:06:39,820 --> 00:06:44,040
Rekursion kan bruges meget effektivt
når der beskæftiger sig med træer for eksempel.

121
00:06:44,040 --> 00:06:47,210
Tjek kort på træerne for en
mere grundig gennemgang, men for nu

122
00:06:47,210 --> 00:06:51,140
erindre om, at binære søgetræer, i
især består af knuder, der hver

123
00:06:51,140 --> 00:06:53,820
med en værdi og to node pointere.

124
00:06:53,820 --> 00:06:57,270
Normalt er denne repræsenteret ved
forælder node har en linie peger

125
00:06:57,270 --> 00:07:01,870
til venstre barneknudepunkt og en
til højre barneknudepunkt.

126
00:07:01,870 --> 00:07:04,510
Strukturen af ​​en binær søgning
træ egner sig godt

127
00:07:04,510 --> 00:07:05,940
en rekursiv søgning.

128
00:07:05,940 --> 00:07:09,730
Den rekursivt kald passerer enten i
højre eller venstre knudepunkt, men mere

129
00:07:09,730 --> 00:07:10,950
af, at træet kort.

130
00:07:10,950 --> 00:07:15,690
>> Sig du ønsker at udføre en operation på
hver enkelt node i et binært træ.

131
00:07:15,690 --> 00:07:17,410
Hvordan kan du gå om det?

132
00:07:17,410 --> 00:07:20,600
Nå, kan du skrive en rekursiv
funktion, der udfører operationen

133
00:07:20,600 --> 00:07:24,450
på den overordnede node og gør en rekursiv
ringe til den samme funktion,

134
00:07:24,450 --> 00:07:27,630
passerer i venstre
rigtige barn noder.

135
00:07:27,630 --> 00:07:31,650
For eksempel denne funktion foo, at
ændrer værdien af ​​en bestemt node og

136
00:07:31,650 --> 00:07:33,830
alle sine børn til 1..

137
00:07:33,830 --> 00:07:37,400
Basen tilfælde af en Null-node årsager
funktionen til at vende tilbage, hvilket indikerer,

138
00:07:37,400 --> 00:07:41,290
at der ikke er nogen knuder
til venstre i denne sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Lad os gå igennem det.

140
00:07:42,620 --> 00:07:44,340
Den første forælder er 13..

141
00:07:44,340 --> 00:07:47,930
Vi ændre værdien til 1, og derefter kalde
vores funktion til venstre så godt

142
00:07:47,930 --> 00:07:49,600
som højre.

143
00:07:49,600 --> 00:07:53,910
Den funktion, foo, kaldes til venstre
sub-tree først, så det venstre knudepunkt

144
00:07:53,910 --> 00:07:57,730
vil blive overført til 1 og foo vil
blive kaldt på nodens børn

145
00:07:57,730 --> 00:08:01,900
først venstre og derefter højre,
og så videre og så videre.

146
00:08:01,900 --> 00:08:05,630
Og fortælle dem, at filialer ikke har
nogen flere børn, så den samme proces

147
00:08:05,630 --> 00:08:09,700
vil fortsætte i de rigtige børn
indtil hele træets knudepunkter er

148
00:08:09,700 --> 00:08:11,430
omfordelt til 1..

149
00:08:11,430 --> 00:08:15,390
>> Som du kan se, er du ikke begrænset
til blot én rekursivt kald.

150
00:08:15,390 --> 00:08:17,930
Lige så mange, som vil få arbejdet gjort.

151
00:08:17,930 --> 00:08:21,200
Hvad hvis du havde et træ, hvor hver
node havde tre børn,

152
00:08:21,200 --> 00:08:23,100
Venstre, midterste og højre?

153
00:08:23,100 --> 00:08:24,886
Hvordan ville du redigere foo?

154
00:08:24,886 --> 00:08:25,860
Nå, enkel.

155
00:08:25,860 --> 00:08:30,250
Blot tilføje en anden rekursivt kald og
passerer i midten node pointer.

156
00:08:30,250 --> 00:08:34,549
>> Rekursion er meget stærk og ikke
nævne elegant, men det kan være en

157
00:08:34,549 --> 00:08:38,010
vanskeligt begreb i første omgang, så vær
patient og tage din tid.

158
00:08:38,010 --> 00:08:39,370
Start med basisscenariet.

159
00:08:39,370 --> 00:08:42,650
Det er normalt den nemmeste at identificere,
og derefter kan du arbejde

160
00:08:42,650 --> 00:08:43,830
baglæns derfra.

161
00:08:43,830 --> 00:08:46,190
Du ved, du har brug for at nå dine
base case, så måske

162
00:08:46,190 --> 00:08:47,760
give dig et par hints.

163
00:08:47,760 --> 00:08:53,120
Prøv at udtrykke en konkret sag i
form af andre sager, eller i sub-sæt.

164
00:08:53,120 --> 00:08:54,700
>> Tak for at se denne korte.

165
00:08:54,700 --> 00:08:58,920
I det mindste, nu kan du
forstå vittigheder som denne.

166
00:08:58,920 --> 00:09:01,250
Mit navn er Zamyla, og det er CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Tag denne funktion, hej, et
void funktion, der tager

169
00:09:07,170 --> 00:09:09,212
en int, n, som input.

170
00:09:09,212 --> 00:09:11,020
Basen sag kommer først.

171
00:09:11,020 --> 00:09:14,240
Hvis n er mindre end 0, print
"Farvel", og tilbagevenden.

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