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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: For å forstå
rekursjon, må du

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

4
00:00:13,820 --> 00:00:17,280
Å ha rekursjon i programmet design midler
at du har selv-referensiell

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

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

7
00:00:21,520 --> 00:00:23,990
inkludere seg selv i
sine definisjoner.

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

9
00:00:27,160 --> 00:00:31,160
>> Husker at funksjoner ta innganger,
argumenter, og returnerer en verdi som deres

10
00:00:31,160 --> 00:00:34,480
utgang representert ved
dette diagrammet her.

11
00:00:34,480 --> 00:00:38,060
Vi vil tenke på boksen som kroppen av
funksjon, som inneholder et sett av

12
00:00:38,060 --> 00:00:42,340
instruksjoner som tolker den
inngangen og gir et utgangssignal.

13
00:00:42,340 --> 00:00:45,660
Å ta en nærmere titt på innsiden av kroppen av
funksjonen kunne avsløre samtaler til

14
00:00:45,660 --> 00:00:47,430
andre funksjoner i tillegg.

15
00:00:47,430 --> 00:00:51,300
Ta denne enkle funksjonen, foo, at
tar en enkelt streng som input og

16
00:00:51,300 --> 00:00:54,630
utskrifter hvor mange bokstaver
at strengen har.

17
00:00:54,630 --> 00:00:58,490
Funksjonen strlen, for streng lengde,
heter, hvis utgang er

18
00:00:58,490 --> 00:01:01,890
nødvendig for kallet til printf.

19
00:01:01,890 --> 00:01:05,770
>> Nå, hva som gjør en rekursiv funksjon
spesielle er at det kaller seg.

20
00:01:05,770 --> 00:01:09,610
Vi kan representere denne rekursive
ringe med denne oransje pil

21
00:01:09,610 --> 00:01:11,360
sløyfe tilbake til seg selv.

22
00:01:11,360 --> 00:01:15,630
Men gjennomføring seg igjen bare vil
foreta en ny rekursive kall, og

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

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

25
00:01:19,100 --> 00:01:23,490
De har å ende en eller annen måte, eller din
programmet vil kjøre for alltid.

26
00:01:23,490 --> 00:01:27,680
>> Så vi må finne en måte å bryte
ut av den rekursive anrop.

27
00:01:27,680 --> 00:01:29,900
Vi kaller dette base case.

28
00:01:29,900 --> 00:01:33,570
Når basen tilfelle betingelsen er oppfylt,
returnerer funksjonen uten å gjøre

29
00:01:33,570 --> 00:01:34,950
annen rekursive kall.

30
00:01:34,950 --> 00:01:39,610
Ta denne funksjonen, hi, et tomrom funksjon
som tar en int n som input.

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

32
00:01:41,260 --> 00:01:46,220
Hvis n er mindre enn null, print bye og
returnere For alle andre tilfeller,

33
00:01:46,220 --> 00:01:49,400
Funksjonen vil skrive hei og utføre
den rekursive kall.

34
00:01:49,400 --> 00:01:53,600
Et annet kall til funksjonen hi med
en dekrementert inngangsverdi.

35
00:01:53,600 --> 00:01:56,790
>> Nå, selv om vi skriver ut hi, den
Funksjonen vil ikke opphøre før vi

36
00:01:56,790 --> 00:02:00,370
returnere sin returtype,
i dette tilfellet ugyldig.

37
00:02:00,370 --> 00:02:04,830
Slik at for hver n annen enn basis tilfellet
denne funksjonen hi vil returnere hi

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

39
00:02:06,890 --> 00:02:10,050
Siden denne funksjonen er ugyldig skjønt, vi
vil ikke eksplisitt skriver retur her.

40
00:02:10,050 --> 00:02:12,000
Vi skal bare utføre funksjonen.

41
00:02:12,000 --> 00:02:16,960
Så ringer hi (3) vil skrive ut hi og
utføre hi (2) som utfører hi (1) en

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

43
00:02:20,560 --> 00:02:24,100
Så hi (0) skriver bye og avkastning.

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

45
00:02:24,990 --> 00:02:28,690
Så nå som vi forstår det grunnleggende
rekursive funksjoner, som de trenger

46
00:02:28,690 --> 00:02:32,730
i det minste en basis tilfelle, så vel som en
rekursive kall, la oss gå videre til en

47
00:02:32,730 --> 00:02:34,120
mer meningsfylt eksempel.

48
00:02:34,120 --> 00:02:37,830
En som ikke bare returnere
ugyldig uansett hva.

49
00:02:37,830 --> 00:02:41,340
>> La oss ta en titt på fakultetet
drift brukes oftest i

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

51
00:02:43,660 --> 00:02:48,120
Factorial av n er produktet av hvert
positive heltall mindre enn

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

53
00:02:49,400 --> 00:02:56,731
Så faktoriell fem er fem ganger fire ganger
3 ganger 2 ganger 1 for å gi 120.

54
00:02:56,731 --> 00:03:01,400
Fire fakultet er fire ganger tre ganger
2 ganger en å gi 24.

55
00:03:01,400 --> 00:03:04,910
Og den samme regelen gjelder
til noe positivt heltall.

56
00:03:04,910 --> 00:03:08,670
>> Så hvordan kan vi skrive en rekursiv
funksjon som beregner fakultet

57
00:03:08,670 --> 00:03:09,960
av et tall?

58
00:03:09,960 --> 00:03:14,700
Vel, vi trenger å identifisere både
base case og rekursive kall.

59
00:03:14,700 --> 00:03:18,250
Den rekursive kall vil være den samme
i alle tilfeller bortsett fra base

60
00:03:18,250 --> 00:03:21,420
saken, noe som betyr at vi må
finne et mønster som vil gi oss vår

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

62
00:03:23,350 --> 00:03:30,270
>> For dette eksempelet, se hvordan fem fakultet
innebærer multiplisere fire av tre med to av en

63
00:03:30,270 --> 00:03:33,010
Og det samme multiplikasjon
er funnet her,

64
00:03:33,010 --> 00:03:35,430
definisjon av fire fakultet.

65
00:03:35,430 --> 00:03:39,810
Så vi ser at fem fakultet er
bare fem ganger fire fakultet.

66
00:03:39,810 --> 00:03:43,360
Nå gjelder dette mønsteret
til 4 faktoriell også?

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

68
00:03:44,280 --> 00:03:49,120
Vi ser at fire fakultet inneholder
multiplikasjon 3 ganger 2 ganger 1, den

69
00:03:49,120 --> 00:03:51,590
samme definisjon som tre fakultet.

70
00:03:51,590 --> 00:03:56,950
Så fire fakultet er lik fire ganger tre
fakultetet, og så videre og så videre vår

71
00:03:56,950 --> 00:04:02,170
mønster stikker frem en fakultet, som
ved definisjon er lik 1.

72
00:04:02,170 --> 00:04:04,950
>> Det er ingen annen positiv
heltall igjen.

73
00:04:04,950 --> 00:04:07,870
Så vi har et mønster for
vår rekursive kall.

74
00:04:07,870 --> 00:04:13,260
n fakultet er lik n ganger
fakultetet av n minus en.

75
00:04:13,260 --> 00:04:14,370
Og vår base case?

76
00:04:14,370 --> 00:04:17,370
Det vil bare være vår definisjon
av en fakultet.

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

78
00:04:19,995 --> 00:04:24,110
For base case, vil vi ha
betingelse n er lik 1, hvor likeverdige

79
00:04:24,110 --> 00:04:25,780
vi vil komme tilbake en.

80
00:04:25,780 --> 00:04:29,280
Deretter går videre til den rekursive kall,
vi vil komme tilbake n ganger

81
00:04:29,280 --> 00:04:32,180
fakultetet av n minus en.

82
00:04:32,180 --> 00:04:33,590
>> Nå la oss teste denne vår.

83
00:04:33,590 --> 00:04:35,900
La oss prøve faktoriell 4.

84
00:04:35,900 --> 00:04:39,420
Per vår funksjon det er lik
til 4 ganger faktoriell (3).

85
00:04:39,420 --> 00:04:43,040
Fakultet (3) er lik
3 ganger faktorielle (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) er lik to ganger
fakultet (1), som returnerer en.

87
00:04:48,700 --> 00:04:52,490
Fakultet (2) returnerer nå 2 ganger 1, 2.

88
00:04:52,490 --> 00:04:55,960
Fakultet (3) kan nå gå tilbake
3 ganger 2, 6.

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

90
00:05:02,490 --> 00:05:06,780
>> Hvis du støter på noen problemer
med den rekursive kall, late som

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

92
00:05:09,660 --> 00:05:13,450
Hva jeg mener med dette er at du bør
stole på dine rekursive kall til å vende tilbake

93
00:05:13,450 --> 00:05:15,100
de rette verdiene.

94
00:05:15,100 --> 00:05:18,960
For eksempel, hvis jeg vet at
fakultet (5) er lik fem ganger

95
00:05:18,960 --> 00:05:24,870
fakultet (4), kommer jeg til å stole på at
fakultet (4) vil gi meg 24.

96
00:05:24,870 --> 00:05:28,510
Tenk på det som en variabel, hvis du
vil, som om du allerede har definert

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

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

99
00:05:33,850 --> 00:05:35,360
forrige fakultet.

100
00:05:35,360 --> 00:05:38,130
Og dette forrige fakultet
oppnås ved å ringe

101
00:05:38,130 --> 00:05:41,330
fakultetet av n minus en.

102
00:05:41,330 --> 00:05:45,130
>> Nå, se om du kan gjennomføre en
rekursiv fungere selv.

103
00:05:45,130 --> 00:05:50,490
Laste opp din terminal, eller run.cs50.net,
og skrive en funksjon sum

104
00:05:50,490 --> 00:05:54,770
som tar et helt tall n og returnerer
Summen av alt sammenhengende positiv

105
00:05:54,770 --> 00:05:57,490
heltall fra n til 1.

106
00:05:57,490 --> 00:06:01,000
Jeg har skrevet ut summene av noen
verdier for å hjelpe deg vår.

107
00:06:01,000 --> 00:06:04,030
Først finne ut av
base case tilstand.

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

109
00:06:06,170 --> 00:06:09,270
Kan du uttrykke det i form
av en annen sum?

110
00:06:09,270 --> 00:06:11,290
Nå, hva om sum (4)?

111
00:06:11,290 --> 00:06:15,630
Hvordan kan du uttrykke sum (4)
i forhold til en annen sum?

112
00:06:15,630 --> 00:06:19,655
>> Når du har sum (5) og sum (4)
uttrykkes i form av andre summer, se

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

114
00:06:22,970 --> 00:06:26,190
Hvis ikke, kan du prøve noen andre tall
og uttrykke sine summer i

115
00:06:26,190 --> 00:06:28,410
forhold til en annen tall.

116
00:06:28,410 --> 00:06:31,930
Ved å identifisere mønstre for diskret
tall, er du godt på vei til å

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

118
00:06:34,320 --> 00:06:38,040
>> Rekursjon er en veldig kraftig verktøy,
så selvfølgelig det ikke er begrenset til

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

120
00:06:39,820 --> 00:06:44,040
Rekursjon kan brukes svært effektivt
når du arbeider med trær for eksempel.

121
00:06:44,040 --> 00:06:47,210
Sjekk ut kort på trær for en
mer grundig gjennomgang, men for nå

122
00:06:47,210 --> 00:06:51,140
Husker at binære søketrær, i
Spesielt er bygget opp av knutepunkter som hver

123
00:06:51,140 --> 00:06:53,820
med en verdi og to nodepekere.

124
00:06:53,820 --> 00:06:57,270
Vanligvis er dette representert ved
forelder node ha en linje som peker

125
00:06:57,270 --> 00:07:01,870
til venstre for barnenode og en
til høyre barnenode.

126
00:07:01,870 --> 00:07:04,510
Strukturen av et binært søk
tre egner seg godt

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

128
00:07:05,940 --> 00:07:09,730
Den rekursive kall enten går i
venstre eller høyre node, men mer

129
00:07:09,730 --> 00:07:10,950
av det i treet kort.

130
00:07:10,950 --> 00:07:15,690
>> Si at du ønsker å utføre en operasjon på
hver eneste node i et binært tre.

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

132
00:07:17,410 --> 00:07:20,600
Vel, kan du skrive en rekursiv
funksjon som utfører operasjonen

133
00:07:20,600 --> 00:07:24,450
på foreldrenoden og gjør en rekursiv
ring til den samme funksjon,

134
00:07:24,450 --> 00:07:27,630
passering i den venstre og
høyre barn noder.

135
00:07:27,630 --> 00:07:31,650
For eksempel denne funksjonen, foo, at
endrer verdien av en gitt node og

136
00:07:31,650 --> 00:07:33,830
alle sine barn til en.

137
00:07:33,830 --> 00:07:37,400
Basen tilfelle av en nullnode årsaker
funksjonen for å gå tilbake, noe som indikerer

138
00:07:37,400 --> 00:07:41,290
at det ikke er noen noder
igjen i det sub-treet.

139
00:07:41,290 --> 00:07:42,620
>> La oss gå gjennom den.

140
00:07:42,620 --> 00:07:44,340
Den første av foreldrene er 13.

141
00:07:44,340 --> 00:07:47,930
Vi endrer verdien til 1, og deretter ringe
vår funksjon på venstre så vel

142
00:07:47,930 --> 00:07:49,600
som den riktige.

143
00:07:49,600 --> 00:07:53,910
Funksjonen, foo, kalles på venstre
sub-treet først, slik at den venstre noden

144
00:07:53,910 --> 00:07:57,730
vil bli overført til en og foo vil
kalles på at node barn,

145
00:07:57,730 --> 00:08:01,900
første til venstre og deretter til høyre,
og så videre og så videre.

146
00:08:01,900 --> 00:08:05,630
Og fortell dem at grenene ikke har
noen flere barn slik at den samme prosessen

147
00:08:05,630 --> 00:08:09,700
vil fortsette for de riktige barn
inntil hele treets noder er

148
00:08:09,700 --> 00:08:11,430
omplassert til en.

149
00:08:11,430 --> 00:08:15,390
>> Som du kan se, er du ikke begrenset
til bare én rekursive kall.

150
00:08:15,390 --> 00:08:17,930
Like mange som vil få jobben gjort.

151
00:08:17,930 --> 00:08:21,200
Hva hvis du hadde et tre der hver
node hadde tre barn,

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

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

154
00:08:24,886 --> 00:08:25,860
Vel, enkelt.

155
00:08:25,860 --> 00:08:30,250
Bare å legge til rekursive kall og
passere i midten nodepekeren.

156
00:08:30,250 --> 00:08:34,549
>> Rekursjon er veldig kraftig, og ikke til
nevne elegant, men det kan være en

157
00:08:34,549 --> 00:08:38,010
vanskelig begrep i begynnelsen, så vær
tålmodig og ta deg god tid.

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

159
00:08:39,370 --> 00:08:42,650
Det er som regel lettest å identifisere,
og da kan du jobbe

160
00:08:42,650 --> 00:08:43,830
bakover derfra.

161
00:08:43,830 --> 00:08:46,190
Du vet at du trenger for å nå dine
base case, slik at makt

162
00:08:46,190 --> 00:08:47,760
gi deg noen hint.

163
00:08:47,760 --> 00:08:53,120
Prøv å uttrykke en konkret sak i
vilkårene i andre tilfeller, eller i sub-sett.

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

165
00:08:54,700 --> 00:08:58,920
I det minste, nå kan du
forstå vitser som dette.

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

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

168
00:09:04,306 --> 00:09:07,170
>> Ta denne funksjonen, hi, en
void funksjon som tar

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

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

171
00:09:11,020 --> 00:09:14,240
Hvis n er mindre enn 0, print
"Bye" og avkastning.

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