1
00:00:00,000 --> 00:00:05,860
>> [Musik spiller]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Du tror sikkert, at
kode bare bruges til at udføre en opgave.

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

4
00:00:10,450 --> 00:00:11,664
Det gør noget.

5
00:00:11,664 --> 00:00:12,580
Det er temmelig meget det.

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

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

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

9
00:00:15,370 --> 00:00:17,520
>> Men tro det eller ej, hvis
du kode i lang tid,

10
00:00:17,520 --> 00:00:20,550
du faktisk kan komme til at se
kode som noget, der er smukt.

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

12
00:00:23,275 --> 00:00:26,510
eller der er bare noget rigtig
pæn om den måde, det ser ud.

13
00:00:26,510 --> 00:00:28,750
Du kan være griner
på mig, men det er sandt.

14
00:00:28,750 --> 00:00:31,530
Og rekursion er en måde
at slags få denne idé

15
00:00:31,530 --> 00:00:34,090
af smukke, elegante udseende kode.

16
00:00:34,090 --> 00:00:37,740
Det løser problemer på en måde,
er interessante, let at visualisere,

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

18
00:00:39,810 --> 00:00:43,190
>> VEJEN rekursionsudtryk værker
er en rekursiv funktion

19
00:00:43,190 --> 00:00:49,291
er defineret som en funktion, der kræver
selv som en del af dens fuldbyrdelse.

20
00:00:49,291 --> 00:00:51,790
Det kan virke lidt mærkeligt,
og vi vil se en lille smule

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

22
00:00:53,750 --> 00:00:55,560
Men igen, disse
rekursive procedurer er

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

24
00:00:57,730 --> 00:01:00,410
at løse dette problem uden
have alle disse andre funktioner

25
00:01:00,410 --> 00:01:02,710
eller disse lange loops.

26
00:01:02,710 --> 00:01:06,310
Du vil se, at disse rekursive
procedurer kommer til at se så kort.

27
00:01:06,310 --> 00:01:10,610
Og de virkelig vil gøre
din kode ser meget smukkere.

28
00:01:10,610 --> 00:01:12,560
>> Jeg vil give dig et eksempel
dette for at se, hvordan

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

30
00:01:14,880 --> 00:01:18,202
Så hvis du er fortrolig med dette
fra matematik klasse for mange år siden,

31
00:01:18,202 --> 00:01:20,910
der hedder noget
faktoriel funktion, der normalt er

32
00:01:20,910 --> 00:01:25,340
betegnet som et udråbstegn, som
er defineret i alle positive heltal.

33
00:01:25,340 --> 00:01:28,850
Og den måde, n
fakultet beregnes

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

35
00:01:31,050 --> 00:01:33,750
eller lig med n together--
alle heltal mindre end

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

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

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

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

40
00:01:44,800 --> 00:01:47,060
>> Som programmører, gør vi ikke
bruge n, udråbstegn.

41
00:01:47,060 --> 00:01:51,840
Så vi vil definere fakultet
funktion som faktisk af n.

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

43
00:01:56,897 --> 00:01:59,230
Og jeg tror, ​​du kan finde
at det er meget mere visuelt

44
00:01:59,230 --> 00:02:02,380
tiltrækkende end den iterative
version af denne, som

45
00:02:02,380 --> 00:02:05,010
Vi vil også tage et kig på et øjeblik.

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

47
00:02:08,310 --> 00:02:10,169
om factorial-- den
faktoriel funktion.

48
00:02:10,169 --> 00:02:13,090
Fakultet af 1, som jeg sagde, er 1.

49
00:02:13,090 --> 00:02:15,690
Fakultet af 2 er 2 gange 1.

50
00:02:15,690 --> 00:02:18,470
Fakultet af 3 er 3
gange 2 gange 1, og så videre.

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

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

53
00:02:23,940 --> 00:02:28,220
Er det ikke fakultet af 2 lige
2 gange fakultet af en?

54
00:02:28,220 --> 00:02:31,130
Jeg mener, fakultet af 1 er 1.

55
00:02:31,130 --> 00:02:34,940
Så hvorfor kan vi ikke bare sige,
da fakultet af 2 er 2 gange 1,

56
00:02:34,940 --> 00:02:38,520
det er virkelig kun 2 gange
fakultet af en?

57
00:02:38,520 --> 00:02:40,900
>> Og derefter at udvide denne idé,
er ikke fakultet af 3

58
00:02:40,900 --> 00:02:44,080
kun 3 gange fakultet af 2?

59
00:02:44,080 --> 00:02:50,350
Og fakultet af 4 er 4 gange
fakultet af 3 og så videre?

60
00:02:50,350 --> 00:02:52,530
Faktisk fakulteten
af et vilkårligt antal kan bare

61
00:02:52,530 --> 00:02:54,660
udtrykkes hvis vi slags
af udføre dette for evigt.

62
00:02:54,660 --> 00:02:56,870
Vi kan slags generalisere
fakultet problem

63
00:02:56,870 --> 00:02:59,910
da det er n gange
fakultet af n minus 1.

64
00:02:59,910 --> 00:03:04,840
Det er n gange produktet af
alle tal mindre end mig.

65
00:03:04,840 --> 00:03:08,890
>> Denne idé, dette
generalisering af problemet,

66
00:03:08,890 --> 00:03:13,410
tillader os at rekursivt
definerer fakultet funktion.

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

68
00:03:15,440 --> 00:03:17,470
to ting, der skal være en del af det.

69
00:03:17,470 --> 00:03:20,990
Du skal have noget, der hedder en
base case, som, når du udløser det,

70
00:03:20,990 --> 00:03:22,480
vil stoppe den rekursive proces.

71
00:03:22,480 --> 00:03:25,300
>> Ellers en funktion, der kræver
itself-- som du måske imagine--

72
00:03:25,300 --> 00:03:26,870
kunne blive ved for evigt.

73
00:03:26,870 --> 00:03:29,047
Funktion kalder funktionen
kalder funktionskald

74
00:03:29,047 --> 00:03:30,380
funktionen kalder funktionen.

75
00:03:30,380 --> 00:03:32,380
Hvis du ikke har en måde
at stoppe det, dit program

76
00:03:32,380 --> 00:03:34,760
vil effektivt blive hængende
ved en uendelig løkke.

77
00:03:34,760 --> 00:03:37,176
Det vil gå ned til sidst,
fordi det vil løbe tør for hukommelse.

78
00:03:37,176 --> 00:03:38,990
Men det er ved siden af ​​punktet.

79
00:03:38,990 --> 00:03:42,210
>> Vi er nødt til at have en anden måde at stoppe
ting udover vores program bryder sammen,

80
00:03:42,210 --> 00:03:46,010
fordi et program, der går ned er
sandsynligvis ikke smuk eller elegant.

81
00:03:46,010 --> 00:03:47,690
Og så kalder vi det basisscenariet.

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

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

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

85
00:03:55,220 --> 00:03:56,820
>> Den anden del er den rekursive tilfældet.

86
00:03:56,820 --> 00:03:59,195
Og det er her, rekursion
rent faktisk vil finde sted.

87
00:03:59,195 --> 00:04:02,200
Det er her den
funktion vil kalde sig selv.

88
00:04:02,200 --> 00:04:05,940
>> Det vil ikke kalde sig på nøjagtig
på samme måde, det blev kaldt.

89
00:04:05,940 --> 00:04:08,880
Det vil være en lille variation
der gør det problem, det er

90
00:04:08,880 --> 00:04:11,497
forsøger at løse en teeny smule mindre.

91
00:04:11,497 --> 00:04:14,330
Men det generelt passerer buck
løse størstedelen af ​​opløsningen

92
00:04:14,330 --> 00:04:17,450
til et andet opkald ned linjen.

93
00:04:17,450 --> 00:04:20,290
>> Hvilke af disse udseende
ligesom basen tilfældet her?

94
00:04:20,290 --> 00:04:25,384
Hvilken en af ​​disse ligner
enkleste løsning på et problem?

95
00:04:25,384 --> 00:04:27,550
Vi har en flok af fakulteterne,
og vi kunne fortsætte

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

97
00:04:30,470 --> 00:04:34,130
>> Men en af ​​disse ligner en
god sag til at være base tilfældet.

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

99
00:04:35,310 --> 00:04:37,810
Vi behøver ikke at gøre noget særligt.

100
00:04:37,810 --> 00:04:40,560
>> Fakultet af 1 er kun 1.

101
00:04:40,560 --> 00:04:42,790
Vi behøver ikke at gøre noget
multiplikation overhovedet.

102
00:04:42,790 --> 00:04:45,248
Det ser ud som om vi skal hen
at forsøge at løse dette problem,

103
00:04:45,248 --> 00:04:47,600
og vi er nødt til at stoppe
Rekursion et eller andet sted,

104
00:04:47,600 --> 00:04:50,610
vi sandsynligvis ønsker at stoppe
det, når vi kommer til en.

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

106
00:04:54,580 --> 00:04:56,660
>> Så hvis vi definerer
vores faktoriel funktion,

107
00:04:56,660 --> 00:04:58,690
her er et skelet til
hvordan vi kan gøre det.

108
00:04:58,690 --> 00:05:03,110
Vi er nødt til at tilslutte de to things--
grundscenariet og rekursive sagen.

109
00:05:03,110 --> 00:05:04,990
Hvad er basisscenariet?

110
00:05:04,990 --> 00:05:10,150
Hvis n er lig med 1, returnere 1-- det er
et virkelig simpelt problem at løse.

111
00:05:10,150 --> 00:05:11,890
>> Fakultet af 1 er 1.

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

113
00:05:13,860 --> 00:05:15,020
Det er kun 1.

114
00:05:15,020 --> 00:05:17,170
Det er en meget nem kendsgerning.

115
00:05:17,170 --> 00:05:19,620
Og så kan være vores base tilfældet.

116
00:05:19,620 --> 00:05:24,730
Hvis vi bliver passeret 1 ind i denne
funktion, vil vi bare vende tilbage 1.

117
00:05:24,730 --> 00:05:27,320
>> Hvad er den rekursive
tilfælde formentlig se ud?

118
00:05:27,320 --> 00:05:32,445
For hver anden række
foruden 1, hvad er mønstret?

119
00:05:32,445 --> 00:05:35,780
Tja, hvis vi tager
fakultet af n,

120
00:05:35,780 --> 00:05:38,160
det er n gange fakultet af n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Hvis vi tager fakultet af 3,
det er 3 gange fakultet af 3 minus 1,

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

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

124
00:05:47,330 --> 00:05:51,710
tilbagevenden n gange
fakultet af n minus 1.

125
00:05:51,710 --> 00:05:53,210
Det er ret ligetil.

126
00:05:53,210 --> 00:05:57,360
>> Og af hensyn til at have lidt
renere og mere elegant kode,

127
00:05:57,360 --> 00:06:01,440
ved, at hvis vi har en enkelt linje loops
eller single-line betingede grene,

128
00:06:01,440 --> 00:06:04,490
vi kan slippe af med alle de
krøllede parenteser omkring dem.

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

130
00:06:06,850 --> 00:06:09,640
Dette har nøjagtig samme
funktionalitet som dette.

131
00:06:09,640 --> 00:06:13,850
>> Jeg er bare at tage væk krøllede
seler, for der er kun én linje

132
00:06:13,850 --> 00:06:18,500
indersiden af ​​disse betingede grene.

133
00:06:18,500 --> 00:06:21,160
Så disse opfører sig ens.

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

135
00:06:23,800 --> 00:06:28,351
Ellers returnerer n gange
fakultet af n minus 1.

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

137
00:06:29,850 --> 00:06:33,850
Hvis n starter som 5, vil vi
tilbage 5 gange fakultet af 4.

138
00:06:33,850 --> 00:06:37,100
Og vi vil se i et minut, når vi taler
om opkaldet stack-- i en anden video

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

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

141
00:06:41,630 --> 00:06:46,970
>> Men mens fakultet af 5 siger
tilbage 5 gange fakultet af 4, og 4

142
00:06:46,970 --> 00:06:49,710
kommer til at sige, OK, godt, afkast
4 gange fakultet af 3.

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

144
00:06:51,737 --> 00:06:53,820
Vi kommer tættere og
tættere på base case.

145
00:06:53,820 --> 00:06:58,180
>> Og når vi ramte bunden tilfældet,
alle de tidligere funktioner

146
00:06:58,180 --> 00:07:00,540
har svaret, de ledte efter.

147
00:07:00,540 --> 00:07:03,900
Fakultet af 2 sagde afkast
2 gange fakultet af 1.

148
00:07:03,900 --> 00:07:06,760
Nå, fakultet af 1 giver 1.

149
00:07:06,760 --> 00:07:10,090
Så opfordringen til fakultet
2 kan returnere 2 gange 1,

150
00:07:10,090 --> 00:07:13,980
og give det tilbage til fakultet af
3, som venter på dette resultat.

151
00:07:13,980 --> 00:07:17,110
>> Og så kan det beregne
dens resultat, 3 gange 2 er 6,

152
00:07:17,110 --> 00:07:18,907
og give det tilbage til fakultet af 4.

153
00:07:18,907 --> 00:07:20,740
Og igen, vi har en
video på opkald stakken

154
00:07:20,740 --> 00:07:23,810
hvor dette er illustreret en lille
mere end hvad jeg siger lige nu.

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

156
00:07:25,300 --> 00:07:29,300
Dette alene er løsningen på
beregning fakultet af et tal.

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

158
00:07:31,527 --> 00:07:32,610
Det er ret cool, ikke?

159
00:07:32,610 --> 00:07:35,480
Det er lidt sexet.

160
00:07:35,480 --> 00:07:38,580
>> Så i almindelighed, men ikke
altid, en rekursiv funktion

161
00:07:38,580 --> 00:07:41,190
kan erstatte en løkke i en
ikke-rekursiv funktion.

162
00:07:41,190 --> 00:07:46,100
Så her, ved siden af ​​hinanden, er den iterative
version af fakulteten funktion.

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

164
00:07:49,650 --> 00:07:52,170
>> De har begge beregne fakultet af n.

165
00:07:52,170 --> 00:07:54,990
Versionen til venstre
bruger rekursion til at gøre det.

166
00:07:54,990 --> 00:07:58,320
Versionen til højre
bruger iteration til at gøre det.

167
00:07:58,320 --> 00:08:02,050
>> Og varsel, vi er nødt til at erklære
en variabel et heltal produkt.

168
00:08:02,050 --> 00:08:02,940
Og så har vi løkke.

169
00:08:02,940 --> 00:08:06,790
Så længe n er større end 0, vi
holde multiplicere resultatet med n

170
00:08:06,790 --> 00:08:09,890
og dekrementere n indtil
beregner vi produktet.

171
00:08:09,890 --> 00:08:14,600
Så disse to funktioner, igen,
gør præcis det samme.

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

173
00:08:19,980 --> 00:08:22,430
>> Nu er det muligt at
har mere end én base

174
00:08:22,430 --> 00:08:25,770
tilfælde eller mere end en
rekursiv tilfælde afhængigt

175
00:08:25,770 --> 00:08:27,670
om, hvad din funktion er at forsøge at gøre.

176
00:08:27,670 --> 00:08:31,650
Du er ikke nødvendigvis kun begrænset til
en enkelt base case eller en enkelt rekursiv

177
00:08:31,650 --> 00:08:32,370
tilfælde.

178
00:08:32,370 --> 00:08:35,320
Så et eksempel på noget
med flere baser sager

179
00:08:35,320 --> 00:08:37,830
kunne være denne-- den
Fibonacci-talrækken.

180
00:08:37,830 --> 00:08:41,549
>> Du husker måske fra
elementære skoledage

181
00:08:41,549 --> 00:08:45,740
at Fibonacci sekvensen er defineret
ligesom denne-- det første element er 0.

182
00:08:45,740 --> 00:08:46,890
Det andet element er 1.

183
00:08:46,890 --> 00:08:49,230
Begge disse er blot ved definition.

184
00:08:49,230 --> 00:08:55,920
>> Derefter hver andet element er defineret
som summen af ​​n minus 1, og n minus 2.

185
00:08:55,920 --> 00:09:00,330
Så det tredje element
ville være 0 plus 1 er 1.

186
00:09:00,330 --> 00:09:03,280
Og så det fjerde element
ville være det andet element, 1,

187
00:09:03,280 --> 00:09:06,550
plus det tredje element, 1.

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

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 tilfælde, har vi to base-sager.

191
00:09:11,680 --> 00:09:14,850
Hvis n er lig med 1, returnere 0.

192
00:09:14,850 --> 00:09:18,560
Hvis n er lig med 2, returnere 1.

193
00:09:18,560 --> 00:09:25,930
Ellers returnerer Fibonacci n
minus 1 plus Fibonacci n minus 2.

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

195
00:09:27,180 --> 00:09:29,271
Hvad med flere rekursive tilfælde?

196
00:09:29,271 --> 00:09:31,520
Tja, der er noget
kaldet Collatz formodninger.

197
00:09:31,520 --> 00:09:34,630
Jeg har ikke tænkt mig at sige,
du ved, hvad det er,

198
00:09:34,630 --> 00:09:38,170
fordi det er faktisk vores endelige
problem for denne særlige video.

199
00:09:38,170 --> 00:09:43,220
Og det er vores øvelse
at arbejde på sammen.

200
00:09:43,220 --> 00:09:46,760
>> Så her er hvad
Collatz formodninger is--

201
00:09:46,760 --> 00:09:48,820
det gælder for ethvert positivt heltal.

202
00:09:48,820 --> 00:09:51,500
Og det gætter på, at det er
altid muligt at komme tilbage

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

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

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

206
00:10:00,070 --> 00:10:05,670
>> Ellers skal du gå gennem denne
processen igen på n divideres med 2.

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

208
00:10:08,200 --> 00:10:13,260
Ellers, hvis n er ulige, gå gennem
denne proces igen på 3n + 1,

209
00:10:13,260 --> 00:10:15,552
eller 3 gange n plus 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 lig med 1, stop.

212
00:10:18,430 --> 00:10:20,230
Vi laver ikke noget mere rekursion.

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

214
00:10:23,730 --> 00:10:28,750
Hvis n er lige, vi gør en rekursiv
tilfælde, kaldte n divideres med 2.

215
00:10:28,750 --> 00:10:33,950
Hvis n er ulige, gør vi en anden
rekursive tilfælde på 3 gange n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Og så målet for denne video er
at tage en anden, pause videoen,

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

218
00:10:42,440 --> 00:10:47,640
hvor du passerer en værdi n, og
Det beregner, hvor mange skridt det

219
00:10:47,640 --> 00:10:52,430
tager at komme til 1, hvis du starter fra n
og du følger disse trin op ovenfor.

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

221
00:10:56,660 --> 00:11:00,190
Ellers går det til
tager et skridt plus imidlertid

222
00:11:00,190 --> 00:11:06,200
mange skridt det tager enten n
divideret med 2, hvis n er lige, eller 3n plus 1

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

224
00:11:08,100 --> 00:11:11,190
>> Nu har jeg sat op på skærmen her
et par test ting for dig,

225
00:11:11,190 --> 00:11:15,690
et par test sager for dig, for at se
hvad disse forskellige Collatz tal er,

226
00:11:15,690 --> 00:11:17,440
og også en illustration
af de skridt,

227
00:11:17,440 --> 00:11:20,390
nødt til at være gået igennem så kan du
slags se denne proces i aktion.

228
00:11:20,390 --> 00:11:24,222
Så hvis n er lig med
1, Collatz n er 0.

229
00:11:24,222 --> 00:11:26,180
Du behøver ikke at gøre
noget at komme tilbage til en.

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

231
00:11:27,600 --> 00:11:30,550
>> Hvis n er 2, det tager
et skridt for at komme til 1.

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

233
00:11:31,810 --> 00:11:33,100
Tja, 2 er ikke lig med 1.

234
00:11:33,100 --> 00:11:36,580
Så det vil være et skridt
plus dog mange skridt det

235
00:11:36,580 --> 00:11:38,015
tager på n divideres med 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 divideret med 2 er 1.

238
00:11:42,910 --> 00:11:47,200
Så det tager et skridt plus dog
mange trin, det tager for en.

239
00:11:47,200 --> 00:11:49,720
1 tager nul trin.

240
00:11:49,720 --> 00:11:52,370
>> For 3, som du kan se, er der
involveret et par skridt.

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

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

243
00:11:56,710 --> 00:11:58,804
Det tager syv trin til at komme tilbage til 1.

244
00:11:58,804 --> 00:12:01,220
Og som du kan se, er der en
par andre prøvesager her

245
00:12:01,220 --> 00:12:02,470
at teste dit program.

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

247
00:12:03,970 --> 00:12:09,210
Og jeg vil gå hoppe tilbage nu
hvad selve processen er her,

248
00:12:09,210 --> 00:12:11,390
hvad denne formodning er.

249
00:12:11,390 --> 00:12:14,140
>> Se om du kan finde ud af
hvordan man definerer Collatz n

250
00:12:14,140 --> 00:12:19,967
så den beregner, hvor mange
skridt det tager at komme til 1.

251
00:12:19,967 --> 00:12:23,050
Så forhåbentlig har du sat på pause videoen
og du er ikke bare venter på mig

252
00:12:23,050 --> 00:12:25,820
at give dig svaret her.

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

254
00:12:29,120 --> 00:12:33,070
>> Så her er en mulig definition
af Collatz funktionen.

255
00:12:33,070 --> 00:12:35,610
Vores base case-- hvis n er
lig med 1, vender vi tilbage 0.

256
00:12:35,610 --> 00:12:38,250
Det tager ikke nogen
skridt til at komme tilbage til en.

257
00:12:38,250 --> 00:12:42,710
>> Ellers har vi to rekursive cases--
én for lige numre og en for ulige.

258
00:12:42,710 --> 00:12:47,164
Den måde jeg teste for lige numre
er at kontrollere, om n mod 2 er lig med 0.

259
00:12:47,164 --> 00:12:49,080
Dette er dybest set igen,
stille spørgsmålet,

260
00:12:49,080 --> 00:12:54,050
hvis du huske, hvad mod is-- hvis jeg
kløft n med 2 er der ingen resten?

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

262
00:12:55,470 --> 00:13:01,370
>> Og så hvis n mod 2 er lig med 0 er
test er det et lige antal.

263
00:13:01,370 --> 00:13:04,250
Hvis ja, jeg ønsker at vende tilbage 1,
fordi dette er absolut

264
00:13:04,250 --> 00:13:09,270
tager et skridt plus Collatz af
hvad nummer er halvdelen af ​​mig.

265
00:13:09,270 --> 00:13:13,910
Ellers vil jeg vende tilbage 1
plus Collatz af 3 gange n plus 1.

266
00:13:13,910 --> 00:13:16,060
Det var den anden
rekursiv skridt, vi

267
00:13:16,060 --> 00:13:19,470
kunne tage at beregne
Collatz-- antallet af trin

268
00:13:19,470 --> 00:13:22,610
det tager at komme tilbage
1 gives et nummer.

269
00:13:22,610 --> 00:13:24,610
Så forhåbentlig, dette eksempel
gav dig en lille smule

270
00:13:24,610 --> 00:13:26,620
af en smag af rekursive procedurer.

271
00:13:26,620 --> 00:13:30,220
Forhåbentlig du synes kode er en
lidt smukkere hvis de gennemføres

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

273
00:13:32,760 --> 00:13:35,955
Men selv om det ikke, rekursion er en
virkelig kraftfuldt værktøj alligevel.

274
00:13:35,955 --> 00:13:38,330
Og så det er helt sikkert noget
at få dit hoved rundt,

275
00:13:38,330 --> 00:13:41,360
fordi du vil være i stand til at skabe
pretty cool programmer ved hjælp rekursion

276
00:13:41,360 --> 00:13:45,930
som ellers kunne være kompliceret at skrive
hvis du bruger loops og iteration.

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

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

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