1
00:00:00,000 --> 00:00:05,860
>> [MUSIC SPILLE]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Du tenker sikkert at
koden er bare brukt til å utføre en oppgave.

3
00:00:09,530 --> 00:00:10,450
Du skriver det ut.

4
00:00:10,450 --> 00:00:11,664
Det gjør noe.

5
00:00:11,664 --> 00:00:12,580
Det er ganske mye det.

6
00:00:12,580 --> 00:00:13,160
>> Du kompilere den.

7
00:00:13,160 --> 00:00:13,993
Du kjører programmet.

8
00:00:13,993 --> 00:00:15,370
Du er flink til å gå.

9
00:00:15,370 --> 00:00:17,520
>> Men tro det eller ei, hvis
innkoding i lang tid,

10
00:00:17,520 --> 00:00:20,550
du faktisk kan komme til å se
kode som noe som er vakkert.

11
00:00:20,550 --> 00:00:23,275
Det løser et problem i
en meget interessant måte,

12
00:00:23,275 --> 00:00:26,510
eller er det bare noe virkelig
pen om hvordan det ser ut.

13
00:00:26,510 --> 00:00:28,750
Du kan være ler
på meg, men det er sant.

14
00:00:28,750 --> 00:00:31,530
Og rekursjon er en vei
å liksom få denne ideen

15
00:00:31,530 --> 00:00:34,090
av vakker, elegant utseende kode.

16
00:00:34,090 --> 00:00:37,740
Det løser problemer på måter som
er interessante, lett å visualisere,

17
00:00:37,740 --> 00:00:39,810
og overraskende kort.

18
00:00:39,810 --> 00:00:43,190
>> Måten rekursjon verk
er, en rekursiv funksjon

19
00:00:43,190 --> 00:00:49,291
er definert som en funksjon som kaller
seg selv som en del av sin utførelse.

20
00:00:49,291 --> 00:00:51,790
Det kan virke litt rart,
og vi får se en liten bit

21
00:00:51,790 --> 00:00:53,750
om hvordan dette fungerer i et øyeblikk.

22
00:00:53,750 --> 00:00:55,560
Men igjen, disse
rekursive prosedyrer er

23
00:00:55,560 --> 00:00:57,730
kommer til å være så elegant
fordi de kommer

24
00:00:57,730 --> 00:01:00,410
å løse dette problem uten
å ha alle disse andre funksjoner

25
00:01:00,410 --> 00:01:02,710
eller disse lange sløyfer.

26
00:01:02,710 --> 00:01:06,310
Du vil se at disse rekursiv
prosedyrer skal se så kort.

27
00:01:06,310 --> 00:01:10,610
Og de virkelig kommer til å gjøre
koden ser mye vakrere.

28
00:01:10,610 --> 00:01:12,560
>> Jeg skal gi deg et eksempel
av dette for å se hvordan

29
00:01:12,560 --> 00:01:14,880
en rekursiv prosedyre kan defineres.

30
00:01:14,880 --> 00:01:18,202
Så hvis du er kjent med dette
fra matte klassen for mange år siden,

31
00:01:18,202 --> 00:01:20,910
Det er noe som heter det
faktoriell funksjon, som vanligvis

32
00:01:20,910 --> 00:01:25,340
betegnet som et utropstegn, som
er definert i løpet av alle positive heltall.

33
00:01:25,340 --> 00:01:28,850
Og måten n
fakultetet beregnes

34
00:01:28,850 --> 00:01:31,050
er du multipliserer alle
tallene mindre enn

35
00:01:31,050 --> 00:01:33,750
eller lik n together--
alle heltall mindre enn

36
00:01:33,750 --> 00:01:34,880
eller lik n sammen.

37
00:01:34,880 --> 00:01:39,850
>> Så 5 fakultet er 5 ganger
4 ganger 3 ganger 2 ganger 1.

38
00:01:39,850 --> 00:01:43,020
Og fire fakultet er 4 ganger
3 ganger 2 ganger 1 og så videre.

39
00:01:43,020 --> 00:01:44,800
Du får ideen.

40
00:01:44,800 --> 00:01:47,060
>> Som programmerere, gjør vi ikke
bruke n, utropstegn.

41
00:01:47,060 --> 00:01:51,840
Så vi vil definere fakultet
funksjon som fakta av n.

42
00:01:51,840 --> 00:01:56,897
Og vi vil bruke fakultet til å opprette
en rekursiv løsning på et problem.

43
00:01:56,897 --> 00:01:59,230
Og jeg tror du kan finne
at det er mye mer visuelt

44
00:01:59,230 --> 00:02:02,380
tiltalende enn den iterative
versjon av denne, hvilken

45
00:02:02,380 --> 00:02:05,010
Vi vil også ta en titt på i et øyeblikk.

46
00:02:05,010 --> 00:02:08,310
>> Så her er et par
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
om factorial-- den
faktoriell funksjon.

48
00:02:10,169 --> 00:02:13,090
Fakultetet av en, som jeg sa, er en.

49
00:02:13,090 --> 00:02:15,690
Fakultetet av to er 2 ganger 1.

50
00:02:15,690 --> 00:02:18,470
Fakultetet av tre er tre
ganger 2 ganger 1, og så videre.

51
00:02:18,470 --> 00:02:20,810
Vi snakket om 4 og 5 allerede.

52
00:02:20,810 --> 00:02:23,940
>> Men ser på dette, er ikke dette sant?

53
00:02:23,940 --> 00:02:28,220
Er ikke fakultetet av to like
2 ganger fakultetet av en?

54
00:02:28,220 --> 00:02:31,130
Jeg mener, er fakultetet av en 1.

55
00:02:31,130 --> 00:02:34,940
Så hvorfor kan vi ikke bare si det,
siden fakultetet av to er 2 ganger 1,

56
00:02:34,940 --> 00:02:38,520
Det er egentlig bare 2 ganger
fakultetet av en?

57
00:02:38,520 --> 00:02:40,900
>> Og deretter utvide den ideen,
er ikke fakultetet av 3

58
00:02:40,900 --> 00:02:44,080
bare 3 ganger fakultetet for to?

59
00:02:44,080 --> 00:02:50,350
Og fakultetet av 4 er 4 ganger
fakultetet av tre, og så videre?

60
00:02:50,350 --> 00:02:52,530
Faktisk fakultetet
av en rekke kan bare

61
00:02:52,530 --> 00:02:54,660
uttrykkes hvis vi kind
av gjennomføre dette for alltid.

62
00:02:54,660 --> 00:02:56,870
Vi kan slags general
fakultetet problem

63
00:02:56,870 --> 00:02:59,910
Som det er n ganger
fakultetet av n minus en.

64
00:02:59,910 --> 00:03:04,840
Det er n ganger produktet av
alle tallene mindre enn meg.

65
00:03:04,840 --> 00:03:08,890
>> Denne ideen, denne
generalisering av problemet,

66
00:03:08,890 --> 00:03:13,410
tillater oss å rekursivt
definere fakultet funksjon.

67
00:03:13,410 --> 00:03:15,440
Når du definerer en funksjon
rekursivt, det er

68
00:03:15,440 --> 00:03:17,470
to ting som må være en del av det.

69
00:03:17,470 --> 00:03:20,990
Du må ha noe som kalles en
basisprosessen, noe som, når man utløser den,

70
00:03:20,990 --> 00:03:22,480
vil stoppe rekursiv prosess.

71
00:03:22,480 --> 00:03:25,300
>> Ellers er en funksjon som kaller
itself-- som du kanskje imagine--

72
00:03:25,300 --> 00:03:26,870
kunne fortsette i det uendelige.

73
00:03:26,870 --> 00:03:29,047
Funksjonen kaller funksjonen
kaller funksjonskall

74
00:03:29,047 --> 00:03:30,380
funksjonen kaller funksjonen.

75
00:03:30,380 --> 00:03:32,380
Hvis du ikke har en måte
å stoppe det, programmet

76
00:03:32,380 --> 00:03:34,760
bli effektivt fast
på en uendelig loop.

77
00:03:34,760 --> 00:03:37,176
Det vil krasje slutt,
fordi det vil gå tom for minne.

78
00:03:37,176 --> 00:03:38,990
Men det er ikke poenget.

79
00:03:38,990 --> 00:03:42,210
>> Vi må ha noen annen måte å stoppe
ting i tillegg til vårt program krasjer,

80
00:03:42,210 --> 00:03:46,010
fordi et program som krasjer er
sannsynligvis ikke vakker eller elegant.

81
00:03:46,010 --> 00:03:47,690
Og så vi kaller dette base case.

82
00:03:47,690 --> 00:03:50,610
Dette er en enkel løsning
til et problem som stopper

83
00:03:50,610 --> 00:03:52,770
den rekursive prosessen oppstår.

84
00:03:52,770 --> 00:03:55,220
Så det er en del av
en rekursiv funksjon.

85
00:03:55,220 --> 00:03:56,820
>> Den andre delen er den tilbakevendende tilfelle.

86
00:03:56,820 --> 00:03:59,195
Og det er her rekursjon
faktisk vil finne sted.

87
00:03:59,195 --> 00:04:02,200
Det er her
Funksjonen vil kalle seg.

88
00:04:02,200 --> 00:04:05,940
>> Det vil ikke kalle seg selv på nøyaktig
på samme måte som det ble kalt.

89
00:04:05,940 --> 00:04:08,880
Det vil være en liten variasjon
som gjør problemet er det

90
00:04:08,880 --> 00:04:11,497
prøver å løse en teeny litt mindre.

91
00:04:11,497 --> 00:04:14,330
Men det vanligvis passerer the buck
å løse mesteparten av oppløsningen

92
00:04:14,330 --> 00:04:17,450
til en annen samtale ned linjen.

93
00:04:17,450 --> 00:04:20,290
>> Hvilke av disse ser
som basistilfellet her?

94
00:04:20,290 --> 00:04:25,384
Hvilken av disse ser ut som den
enkleste løsningen på et problem?

95
00:04:25,384 --> 00:04:27,550
Vi har en haug med fakultetene,
og vi kunne fortsette

96
00:04:27,550 --> 00:04:30,470
går on-- 6, 7, 8, 9, 10, og så videre.

97
00:04:30,470 --> 00:04:34,130
>> Men en av disse ser ut som en
god sak å være basistilfellet.

98
00:04:34,130 --> 00:04:35,310
Det er en veldig enkel løsning.

99
00:04:35,310 --> 00:04:37,810
Vi trenger ikke å gjøre noe spesielt.

100
00:04:37,810 --> 00:04:40,560
>> Fakultetet av en er bare en.

101
00:04:40,560 --> 00:04:42,790
Vi trenger ikke å gjøre noe
multiplikasjon i det hele tatt.

102
00:04:42,790 --> 00:04:45,248
Det virker som om vi kommer
å prøve og løse dette problemet,

103
00:04:45,248 --> 00:04:47,600
og vi må stoppe
Rekursjon et sted,

104
00:04:47,600 --> 00:04:50,610
vi sannsynligvis vil stoppe
det når vi kommer til en.

105
00:04:50,610 --> 00:04:54,580
Vi ønsker ikke å stoppe før det.

106
00:04:54,580 --> 00:04:56,660
>> Så hvis vi definerer
vår faktoriell funksjon,

107
00:04:56,660 --> 00:04:58,690
her er et skjelett for
hvordan vi kan gjøre det.

108
00:04:58,690 --> 00:05:03,110
Vi trenger å koble disse to things--
basistilfellet og den tilbakevendende tilfelle.

109
00:05:03,110 --> 00:05:04,990
Hva er base case?

110
00:05:04,990 --> 00:05:10,150
Hvis n er lik 1, returnere 1-- det er
et veldig enkelt problem å løse.

111
00:05:10,150 --> 00:05:11,890
>> Fakultetet av en er en.

112
00:05:11,890 --> 00:05:13,860
Det er ikke 1 ganger noe.

113
00:05:13,860 --> 00:05:15,020
Det er bare en.

114
00:05:15,020 --> 00:05:17,170
Det er et veldig enkelt faktum.

115
00:05:17,170 --> 00:05:19,620
Og slik som kan være vår base case.

116
00:05:19,620 --> 00:05:24,730
Hvis vi får gått en inn i dette
funksjon, vil vi bare tilbake en.

117
00:05:24,730 --> 00:05:27,320
>> Hva er rekursive
tilfellet sannsynligvis se ut?

118
00:05:27,320 --> 00:05:32,445
For alle andre tall
foruten en, hva er oppskriften?

119
00:05:32,445 --> 00:05:35,780
Vel, hvis vi tar
fakultetet av n,

120
00:05:35,780 --> 00:05:38,160
det er n ganger fakultetet av n minus en.

121
00:05:38,160 --> 00:05:42,130
>> Hvis vi tar fakultetet av tre,
det er 3 ganger fakultetet av 3 minus 1,

122
00:05:42,130 --> 00:05:43,070
eller to.

123
00:05:43,070 --> 00:05:47,330
Og så hvis vi ikke er
ser på en, ellers

124
00:05:47,330 --> 00:05:51,710
avkastning n ganger de
fakultetet av n minus en.

125
00:05:51,710 --> 00:05:53,210
Det er ganske grei.

126
00:05:53,210 --> 00:05:57,360
>> Og for å få til å ha litt
renere og mer elegant kode

127
00:05:57,360 --> 00:06:01,440
vet at hvis vi har én linje sløyfer
eller én linje betingede grener,

128
00:06:01,440 --> 00:06:04,490
vi kan bli kvitt alle de
klammeparentes rundt dem.

129
00:06:04,490 --> 00:06:06,850
Så vi kan konsolidere dette til dette.

130
00:06:06,850 --> 00:06:09,640
Dette har nøyaktig den samme
funksjonalitet som dette.

131
00:06:09,640 --> 00:06:13,850
>> Jeg bare tar bort den krøllete
seler, fordi det er bare én linje

132
00:06:13,850 --> 00:06:18,500
innsiden av de betingede grener.

133
00:06:18,500 --> 00:06:21,160
Så disse oppfører seg likt.

134
00:06:21,160 --> 00:06:23,800
Hvis n er lik 1, returnere en.

135
00:06:23,800 --> 00:06:28,351
Ellers returnere n ganger
fakultetet av n minus en.

136
00:06:28,351 --> 00:06:29,850
Så vi gjøre problemet mindre.

137
00:06:29,850 --> 00:06:33,850
Hvis n starter som fem, skal vi
tilbake 5 ganger fakultetet av fire.

138
00:06:33,850 --> 00:06:37,100
Og vi vil se i et minutt når vi snakker
om samtalen stack-- i en annen video

139
00:06:37,100 --> 00:06:39,390
hvor vi snakker om
kaller stack-- vi vil lære

140
00:06:39,390 --> 00:06:41,630
om hvorfor akkurat denne prosessen fungerer.

141
00:06:41,630 --> 00:06:46,970
>> Men mens fakultetet av fem sier
tilbake 5 ganger fakultetet av fire, og fire

142
00:06:46,970 --> 00:06:49,710
kommer til å si, OK, vel, retur
4 ganger fakultetet av tre.

143
00:06:49,710 --> 00:06:51,737
Og som du kan se, er vi
slags nærmer en.

144
00:06:51,737 --> 00:06:53,820
Vi kommer nærmere og
nærmere den til basistilfellet.

145
00:06:53,820 --> 00:06:58,180
>> Og når vi treffer base case,
alle av de tidligere funksjoner

146
00:06:58,180 --> 00:07:00,540
har svaret de var ute etter.

147
00:07:00,540 --> 00:07:03,900
Fakultetet av to sa retur
2 ganger fakultetet av en.

148
00:07:03,900 --> 00:07:06,760
Vel, fakultetet av 1 returnerer 1.

149
00:07:06,760 --> 00:07:10,090
Så samtalen for fakultet
2 kan returnere 2 ganger 1,

150
00:07:10,090 --> 00:07:13,980
og gi den tilbake til fakultetet for
3, som venter på dette resultatet.

151
00:07:13,980 --> 00:07:17,110
>> Og så kan det regne
resultatet, 3 ganger 2 er 6,

152
00:07:17,110 --> 00:07:18,907
og gi det tilbake til fakultetet av fire.

153
00:07:18,907 --> 00:07:20,740
Og igjen, vi har en
video på kallstakken

154
00:07:20,740 --> 00:07:23,810
hvor det er vist en litt
mer enn hva jeg sier akkurat nå.

155
00:07:23,810 --> 00:07:25,300
Men dette er det.

156
00:07:25,300 --> 00:07:29,300
Dette alene er løsningen på
beregne fakultetet til et tall.

157
00:07:29,300 --> 00:07:31,527
>> Det er bare fire linjer med kode.

158
00:07:31,527 --> 00:07:32,610
Det er ganske kult, ikke sant?

159
00:07:32,610 --> 00:07:35,480
Det er litt sexy.

160
00:07:35,480 --> 00:07:38,580
>> Så generelt, men ikke
alltid, en rekursiv funksjon

161
00:07:38,580 --> 00:07:41,190
kan erstatte en loop i et
non-rekursiv funksjon.

162
00:07:41,190 --> 00:07:46,100
Så her, side ved side, er den iterative
versjon av fakultetet funksjonen.

163
00:07:46,100 --> 00:07:49,650
Begge disse beregne
akkurat det samme.

164
00:07:49,650 --> 00:07:52,170
>> Begge beregne fakultetet av n.

165
00:07:52,170 --> 00:07:54,990
Versjonen til venstre
bruker rekursjon til å gjøre det.

166
00:07:54,990 --> 00:07:58,320
Versjonen til høyre
bruker iterasjon for å gjøre det.

167
00:07:58,320 --> 00:08:02,050
>> Og legg merke til, må vi erklære
en variabel et heltall produkt.

168
00:08:02,050 --> 00:08:02,940
Og da er vi loop.

169
00:08:02,940 --> 00:08:06,790
Så lenge n er større enn 0, vi
holde multiplisere at produktet av n

170
00:08:06,790 --> 00:08:09,890
og minske n inntil
vi beregne produktet.

171
00:08:09,890 --> 00:08:14,600
Slik at disse to funksjonene, igjen,
gjøre akkurat det samme.

172
00:08:14,600 --> 00:08:19,980
Men de gjør det ikke i
nøyaktig samme måte.

173
00:08:19,980 --> 00:08:22,430
>> Nå er det mulig å
har mer enn en basis

174
00:08:22,430 --> 00:08:25,770
Ved eller mer enn ett
rekursive tilfelle, avhengig

175
00:08:25,770 --> 00:08:27,670
på hva din funksjon prøver å gjøre.

176
00:08:27,670 --> 00:08:31,650
Du er ikke nødvendigvis bare begrenset til
en enkelt base sak eller et enkelt rekursivt

177
00:08:31,650 --> 00:08:32,370
case.

178
00:08:32,370 --> 00:08:35,320
Slik at et eksempel på noe
med flere base tilfeller

179
00:08:35,320 --> 00:08:37,830
kan være dette-- den
Fibonacci tallrekken.

180
00:08:37,830 --> 00:08:41,549
>> Du husker kanskje fra
grunnskole dager

181
00:08:41,549 --> 00:08:45,740
at Fibonacci-sekvensen er definert
dette-- som det første elementet er 0.

182
00:08:45,740 --> 00:08:46,890
Det andre element er en.

183
00:08:46,890 --> 00:08:49,230
Begge disse er bare per definisjon.

184
00:08:49,230 --> 00:08:55,920
>> Så alle andre element er definert
som summen av n minus 1 og n minus 2.

185
00:08:55,920 --> 00:09:00,330
Slik det tredje elementet
ville være 0 pluss 1 er en.

186
00:09:00,330 --> 00:09:03,280
Og da det fjerde elementet
vil være det andre element, 1,

187
00:09:03,280 --> 00:09:06,550
pluss den tredje element, en.

188
00:09:06,550 --> 00:09:08,507
Og det ville være to.

189
00:09:08,507 --> 00:09:09,340
Og så videre og så videre.

190
00:09:09,340 --> 00:09:11,680
>> Så i dette tilfellet har vi to base tilfeller.

191
00:09:11,680 --> 00:09:14,850
Hvis n er lik 1, retur 0.

192
00:09:14,850 --> 00:09:18,560
Hvis n er lik 2, returnere en.

193
00:09:18,560 --> 00:09:25,930
Ellers returnere Fibonacci av n
minus en pluss Fibonacci n minus to.

194
00:09:25,930 --> 00:09:27,180
>> Så det er flere base tilfeller.

195
00:09:27,180 --> 00:09:29,271
Hva om flere rekursive tilfeller?

196
00:09:29,271 --> 00:09:31,520
Vel, det er noe
kalt Collatz gjetninger.

197
00:09:31,520 --> 00:09:34,630
Jeg har ikke tenkt å si,
du vet hva det er,

198
00:09:34,630 --> 00:09:38,170
fordi det er faktisk vår endelige
Problemet for denne video.

199
00:09:38,170 --> 00:09:43,220
Og det er vår oppgave
å jobbe med sammen.

200
00:09:43,220 --> 00:09:46,760
>> Så her er hva
Collatz formodning er--

201
00:09:46,760 --> 00:09:48,820
det gjelder for alle positive heltall.

202
00:09:48,820 --> 00:09:51,500
Og det spekulerer at det er
alltid mulig å få tilbake

203
00:09:51,500 --> 00:09:55,060
1 hvis du følger disse trinnene.

204
00:09:55,060 --> 00:09:57,560
Hvis n er 1, stopp.

205
00:09:57,560 --> 00:10:00,070
Vi har fått tilbake til 1 hvis n er en.

206
00:10:00,070 --> 00:10:05,670
>> Ellers går gjennom denne
prosessen igjen på n dividert med to.

207
00:10:05,670 --> 00:10:08,200
Og se om du kan komme tilbake til en.

208
00:10:08,200 --> 00:10:13,260
Ellers, hvis n er et oddetall, gå gjennom
denne prosessen igjen på 3n pluss 1,

209
00:10:13,260 --> 00:10:15,552
eller 3 ganger n pluss 1.

210
00:10:15,552 --> 00:10:17,010
Så her har vi en enkelt base case.

211
00:10:17,010 --> 00:10:18,430
Hvis n er lik 1, stopp.

212
00:10:18,430 --> 00:10:20,230
Vi gjør ikke noe mer rekursjon.

213
00:10:20,230 --> 00:10:23,730
>> Men vi har to rekursive tilfeller.

214
00:10:23,730 --> 00:10:28,750
Hvis n er enda, gjør vi en rekursiv
tilfelle, ringer n delt på to.

215
00:10:28,750 --> 00:10:33,950
Hvis n er et oddetall, gjør vi en annen
rekursiv saken på 3 ganger n pluss en.

216
00:10:33,950 --> 00:10:39,120
>> Og så målet for denne videoen er
å ta en andre, sette videoen

217
00:10:39,120 --> 00:10:42,440
og prøve og skrive dette
rekursiv funksjon Collatz

218
00:10:42,440 --> 00:10:47,640
hvor du passerer i en verdi n, og
det beregner hvor mange skritt det

219
00:10:47,640 --> 00:10:52,430
tar å komme til en hvis du starter fra n
og du følger disse trinnene opp ovenfor.

220
00:10:52,430 --> 00:10:56,660
Hvis n er 1, tar det 0 trinn.

221
00:10:56,660 --> 00:11:00,190
Ellers kommer det til å
ta ett skritt pluss imidlertid

222
00:11:00,190 --> 00:11:06,200
mange skritt det tar på hver n
dividert med 2 når n er et partall eller 3n pluss 1

223
00:11:06,200 --> 00:11:08,100
hvis n er et oddetall.

224
00:11:08,100 --> 00:11:11,190
>> Nå har jeg satt opp på skjermen her
et par test ting for deg,

225
00:11:11,190 --> 00:11:15,690
et par tester saker for deg, for å se
hva disse ulike Collatz tallene er,

226
00:11:15,690 --> 00:11:17,440
og også en illustrasjon
av trinnene som

227
00:11:17,440 --> 00:11:20,390
trenger å bli gått gjennom så du kan
liksom se denne prosessen i aksjon.

228
00:11:20,390 --> 00:11:24,222
Slik at hvis n er lik
1, Collatz n er 0.

229
00:11:24,222 --> 00:11:26,180
Du trenger ikke å gjøre
noe for å komme tilbake til en.

230
00:11:26,180 --> 00:11:27,600
Du er allerede der.

231
00:11:27,600 --> 00:11:30,550
>> Dersom n er 2, det tar
ett skritt for å få til en.

232
00:11:30,550 --> 00:11:31,810
Du starter med to.

233
00:11:31,810 --> 00:11:33,100
Vel, er to ikke lik en.

234
00:11:33,100 --> 00:11:36,580
Så det kommer til å være ett skritt
pluss imidlertid mange skritt det

235
00:11:36,580 --> 00:11:38,015
tar på n delt på to.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 dividert med 2 er en.

238
00:11:42,910 --> 00:11:47,200
Så det tar ett skritt pluss imidlertid
mange skritt det tar for en.

239
00:11:47,200 --> 00:11:49,720
En tar null trinn.

240
00:11:49,720 --> 00:11:52,370
>> For tre, som du kan se, er det
ganske få skritt involvert.

241
00:11:52,370 --> 00:11:53,590
Du går fra tre.

242
00:11:53,590 --> 00:11:56,710
Og så du går til
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Det tar sju trinn for å komme tilbake til en.

244
00:11:58,804 --> 00:12:01,220
Og som du kan se, det er en
par andre testtilfeller her

245
00:12:01,220 --> 00:12:02,470
å teste ut programmet.

246
00:12:02,470 --> 00:12:03,970
Så igjen, pause videoen.

247
00:12:03,970 --> 00:12:09,210
Og jeg skal gå hoppe tilbake nå til
hva selve prosessen er her,

248
00:12:09,210 --> 00:12:11,390
hva dette formodning er.

249
00:12:11,390 --> 00:12:14,140
>> Se om du kan finne ut
hvordan du definerer Collatz av n

250
00:12:14,140 --> 00:12:19,967
slik at det beregner hvor mange
skritt som trengs for å få til en.

251
00:12:19,967 --> 00:12:23,050
Så forhåpentligvis har du stoppet videoen
og du er ikke bare venter på meg

252
00:12:23,050 --> 00:12:25,820
for å gi deg svaret her.

253
00:12:25,820 --> 00:12:29,120
Men hvis du er, vel,
her er svaret uansett.

254
00:12:29,120 --> 00:12:33,070
>> Så her er en mulig definisjon
av Collatz funksjonen.

255
00:12:33,070 --> 00:12:35,610
Vår base case-- hvis n er
lik 1, returnerer vi 0.

256
00:12:35,610 --> 00:12:38,250
Det tar ikke noen
trinn for å komme tilbake til en.

257
00:12:38,250 --> 00:12:42,710
>> Ellers har vi to rekursive cases--
en for partall og en for Odd.

258
00:12:42,710 --> 00:12:47,164
Måten jeg teste for partall
er å sjekke om n mod to lik 0.

259
00:12:47,164 --> 00:12:49,080
Dette er i utgangspunktet igjen,
stille spørsmålet,

260
00:12:49,080 --> 00:12:54,050
hvis du husker hva mod er-- om jeg
dividere n av to er det ingen resten?

261
00:12:54,050 --> 00:12:55,470
Det ville være et partall.

262
00:12:55,470 --> 00:13:01,370
>> Og så hvis n mod 2 er lik 0 er
testing er dette et partall.

263
00:13:01,370 --> 00:13:04,250
Hvis så, jeg ønsker å returnere en,
fordi det er absolutt

264
00:13:04,250 --> 00:13:09,270
ta ett skritt pluss Collatz av
uansett hvor mange er halvparten av meg.

265
00:13:09,270 --> 00:13:13,910
Ellers ønsker jeg å returnere en
pluss Collatz av 3 ganger n pluss 1.

266
00:13:13,910 --> 00:13:16,060
Det var den andre
rekursive skritt som vi

267
00:13:16,060 --> 00:13:19,470
kunne ta for å beregne
Collatz-- antall skritt

268
00:13:19,470 --> 00:13:22,610
det tar å komme tilbake
til en gitt et nummer.

269
00:13:22,610 --> 00:13:24,610
Så forhåpentligvis, dette eksempelet
ga deg litt

270
00:13:24,610 --> 00:13:26,620
av en smak av rekursive prosedyrer.

271
00:13:26,620 --> 00:13:30,220
Forhåpentligvis, tror du koden er en
litt vakrere hvis implementert

272
00:13:30,220 --> 00:13:32,760
i en elegant, rekursiv måte.

273
00:13:32,760 --> 00:13:35,955
Men selv om ikke, er rekursjon en
virkelig kraftig verktøy likevel.

274
00:13:35,955 --> 00:13:38,330
Og så det er definitivt noe
å få hodet rundt,

275
00:13:38,330 --> 00:13:41,360
fordi du vil være i stand til å skape
ganske kule programmer ved hjelp av rekursjon

276
00:13:41,360 --> 00:13:45,930
som ellers kan være komplisert å skrive
hvis du bruker loops og gjentakelse.

277
00:13:45,930 --> 00:13:46,980
Jeg er Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Dette er CS50.

279
00:13:48,780 --> 00:13:50,228