1
00:00:00,000 --> 00:00:05,860
>> [Muziek]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Je denkt waarschijnlijk dat
code wordt alleen gebruikt om een ​​taak te volbrengen.

3
00:00:09,530 --> 00:00:10,450
Je schrijft het uit.

4
00:00:10,450 --> 00:00:11,664
Het doet iets.

5
00:00:11,664 --> 00:00:12,580
Dat is vrij veel.

6
00:00:12,580 --> 00:00:13,160
>> U compileren.

7
00:00:13,160 --> 00:00:13,993
U start het programma.

8
00:00:13,993 --> 00:00:15,370
Je bent goed om te gaan.

9
00:00:15,370 --> 00:00:17,520
>> Maar geloof het of niet, als
u coderen voor een lange tijd,

10
00:00:17,520 --> 00:00:20,550
je eigenlijk zou kunnen komen te zien
code als iets dat is prachtig.

11
00:00:20,550 --> 00:00:23,275
Het lost een probleem
een zeer interessante manier,

12
00:00:23,275 --> 00:00:26,510
of er is gewoon iets echt
keurige over de manier waarop het eruit ziet.

13
00:00:26,510 --> 00:00:28,750
Je zou kunnen lachen
bij mij, maar het is waar.

14
00:00:28,750 --> 00:00:31,530
En recursie is een manier
om een ​​soort van krijgen dit idee

15
00:00:31,530 --> 00:00:34,090
van mooie, elegante ogende code.

16
00:00:34,090 --> 00:00:37,740
Het lost problemen op manieren die
zijn interessant, gemakkelijk te visualiseren,

17
00:00:37,740 --> 00:00:39,810
en verrassend kort.

18
00:00:39,810 --> 00:00:43,190
>> De manier waarop recursie werken
is een recursieve functie

19
00:00:43,190 --> 00:00:49,291
wordt gedefinieerd als een functie die oproepen
zich als onderdeel van de uitvoering.

20
00:00:49,291 --> 00:00:51,790
Dat lijkt misschien een beetje vreemd,
en we zullen een beetje zien

21
00:00:51,790 --> 00:00:53,750
over hoe dit werkt in een moment.

22
00:00:53,750 --> 00:00:55,560
Maar nogmaals, deze
recursieve procedures

23
00:00:55,560 --> 00:00:57,730
ga zo elegant te zijn
omdat ze gaan

24
00:00:57,730 --> 00:01:00,410
dit probleem op te lossen zonder
hebben al deze andere functies

25
00:01:00,410 --> 00:01:02,710
of deze lange lussen.

26
00:01:02,710 --> 00:01:06,310
Je zult zien dat deze recursieve
procedures zullen zo kort kijken.

27
00:01:06,310 --> 00:01:10,610
En ze echt gaan maken
uw code er een stuk mooier.

28
00:01:10,610 --> 00:01:12,560
>> Ik zal u een voorbeeld geven
dit om te zien hoe

29
00:01:12,560 --> 00:01:14,880
een recursieve procedure kan worden vastgesteld.

30
00:01:14,880 --> 00:01:18,202
Dus als je vertrouwd zijn met deze bent
van wiskunde klasse vele jaren geleden,

31
00:01:18,202 --> 00:01:20,910
Er is iets genaamd de
faculteit-functie, die meestal

32
00:01:20,910 --> 00:01:25,340
aangeduid als een uitroepteken, die
is gedefinieerd over alle positieve gehele getallen.

33
00:01:25,340 --> 00:01:28,850
En de manier waarop n
factorial berekend

34
00:01:28,850 --> 00:01:31,050
wordt u alle vermenigvuldigen
de getallen kleiner dan

35
00:01:31,050 --> 00:01:33,750
of gelijk aan n together--
alle getallen lager dan

36
00:01:33,750 --> 00:01:34,880
of gelijk aan n samen.

37
00:01:34,880 --> 00:01:39,850
>> Dus 5 faculteit is 5 keer
4 maal 3 keer 2 keer 1.

38
00:01:39,850 --> 00:01:43,020
En 4 faculteit is 4 keer
3 keer 2 keer 1 enzovoort.

39
00:01:43,020 --> 00:01:44,800
Je krijgt het idee.

40
00:01:44,800 --> 00:01:47,060
>> Als programmeurs, doen we niet
Gebruik n, uitroepteken.

41
00:01:47,060 --> 00:01:51,840
Dus we de faculteit definiëren
functie feit n.

42
00:01:51,840 --> 00:01:56,897
En we zullen faculteit gebruiken voor het maken
een recursieve oplossing voor een probleem.

43
00:01:56,897 --> 00:01:59,230
En ik denk dat je zou kunnen vinden
dat het een veel meer visueel

44
00:01:59,230 --> 00:02:02,380
aantrekkelijk dan de iteratieve
versie van deze, waarvan

45
00:02:02,380 --> 00:02:05,010
We zullen ook een kijkje nemen op in een moment.

46
00:02:05,010 --> 00:02:08,310
>> Dus hier zijn een paar
facts-- woordspeling intended--

47
00:02:08,310 --> 00:02:10,169
over de factorial--
faculteit-functie.

48
00:02:10,169 --> 00:02:13,090
De faculteit van 1, zoals ik al zei, is 1.

49
00:02:13,090 --> 00:02:15,690
De faculteit van 2 is 2 keer 1.

50
00:02:15,690 --> 00:02:18,470
De faculteit van 3 3
tijden 2 keer 1, enzovoorts.

51
00:02:18,470 --> 00:02:20,810
We spraken over 4 en 5 al.

52
00:02:20,810 --> 00:02:23,940
>> Maar te kijken naar dit, is dit niet waar is?

53
00:02:23,940 --> 00:02:28,220
Wordt niet faculteit van 2 net
2 maal de faculteit van 1?

54
00:02:28,220 --> 00:02:31,130
Ik bedoel, de faculteit van 1: 1.

55
00:02:31,130 --> 00:02:34,940
Dus waarom kunnen we zeggen alleen dat,
aangezien faculteit van 2 is 2 maal 1,

56
00:02:34,940 --> 00:02:38,520
het is eigenlijk gewoon 2 keer
de faculteit van 1?

57
00:02:38,520 --> 00:02:40,900
>> En dan de uitbreiding van dat idee,
is de faculteit van 3

58
00:02:40,900 --> 00:02:44,080
slechts 3 maal de faculteit van 2?

59
00:02:44,080 --> 00:02:50,350
En de faculteit van 4 is 4 keer
de faculteit van 3, enzovoorts?

60
00:02:50,350 --> 00:02:52,530
In feite is de faculteit
van een willekeurig aantal kan gewoon

61
00:02:52,530 --> 00:02:54,660
Als we worden uitgedrukt soort
van te voeren dit uit voor altijd.

62
00:02:54,660 --> 00:02:56,870
We kunnen soort generaliseren
de faculteit probleem

63
00:02:56,870 --> 00:02:59,910
aangezien het n keer de
faculteit van n minus 1.

64
00:02:59,910 --> 00:03:04,840
Het is n maal het product van
alle nummers minder dan ik.

65
00:03:04,840 --> 00:03:08,890
>> Dit idee, deze
veralgemening van het probleem,

66
00:03:08,890 --> 00:03:13,410
stelt ons in staat om recursief
definiëren de faculteit-functie.

67
00:03:13,410 --> 00:03:15,440
Wanneer u een functie definieert
recursief, er is

68
00:03:15,440 --> 00:03:17,470
twee dingen die moeten een deel van het zijn.

69
00:03:17,470 --> 00:03:20,990
Je nodig hebt om een ​​zogenaamde
base case, die, als je het triggeren,

70
00:03:20,990 --> 00:03:22,480
zal het recursieve proces te stoppen.

71
00:03:22,480 --> 00:03:25,300
>> Anders, een functie die oproepen
itself-- zoals je misschien imagine--

72
00:03:25,300 --> 00:03:26,870
zou kunnen blijven vertellen.

73
00:03:26,870 --> 00:03:29,047
Functie noemt de functie
roept de functie oproepen

74
00:03:29,047 --> 00:03:30,380
de functie roept de functie.

75
00:03:30,380 --> 00:03:32,380
Als u niet beschikt over een manier hebben
om het te stoppen, je programma

76
00:03:32,380 --> 00:03:34,760
zal effectief worden geplakt
in een oneindige lus.

77
00:03:34,760 --> 00:03:37,176
Het zal uiteindelijk crashen,
want het zal uit het geheugen draaien.

78
00:03:37,176 --> 00:03:38,990
Maar dat is naast het punt.

79
00:03:38,990 --> 00:03:42,210
>> We moeten een andere manier om te stoppen hebben
dingen naast ons programma crashen,

80
00:03:42,210 --> 00:03:46,010
omdat een programma dat crasht is
waarschijnlijk niet mooi of elegant.

81
00:03:46,010 --> 00:03:47,690
En dus hebben we dit de basis geval noemen.

82
00:03:47,690 --> 00:03:50,610
Dit is een eenvoudige oplossing
een probleem dat stopt

83
00:03:50,610 --> 00:03:52,770
het recursieve proces optreedt.

84
00:03:52,770 --> 00:03:55,220
Dus dat is een deel van
een recursieve functie.

85
00:03:55,220 --> 00:03:56,820
>> Het tweede deel is de recursieve geval.

86
00:03:56,820 --> 00:03:59,195
En dit is waar de recursie
zal daadwerkelijk plaatsvinden.

87
00:03:59,195 --> 00:04:02,200
Dit is waar de
functie zal zichzelf noemen.

88
00:04:02,200 --> 00:04:05,940
>> Het zal zich niet precies noemen
Op dezelfde manier werd het genoemd.

89
00:04:05,940 --> 00:04:08,880
Het zal een lichte variatie
dat maakt het probleem is het

90
00:04:08,880 --> 00:04:11,497
proberen om een ​​piepklein beetje kleiner te lossen.

91
00:04:11,497 --> 00:04:14,330
Maar het gaat over het algemeen van de bok
oplossing van de bulk van de oplossing

92
00:04:14,330 --> 00:04:17,450
naar een ander gesprek langs de lijn.

93
00:04:17,450 --> 00:04:20,290
>> Welke van deze looks
zoals de base case hier?

94
00:04:20,290 --> 00:04:25,384
Welke van deze lijkt op het
eenvoudigste oplossing voor een probleem?

95
00:04:25,384 --> 00:04:27,550
We hebben een heleboel faculteiten,
en we konden blijven

96
00:04:27,550 --> 00:04:30,470
gaan on-- 6, 7, 8, 9, 10, enzovoort.

97
00:04:30,470 --> 00:04:34,130
>> Maar een van deze ziet eruit als een
goede zaak naar de basis geval te zijn.

98
00:04:34,130 --> 00:04:35,310
Het is een heel eenvoudige oplossing.

99
00:04:35,310 --> 00:04:37,810
We hoeven niet om iets bijzonders te doen.

100
00:04:37,810 --> 00:04:40,560
>> De faculteit van 1 ligt op slechts 1.

101
00:04:40,560 --> 00:04:42,790
We hoeven niet elke doen
vermenigvuldigen helemaal.

102
00:04:42,790 --> 00:04:45,248
Het lijkt alsof we gaan
om te proberen dit probleem op te lossen,

103
00:04:45,248 --> 00:04:47,600
en we naar de halte nodig
Recursion ergens,

104
00:04:47,600 --> 00:04:50,610
waarschijnlijk willen we stoppen
wanneer we naar 1.

105
00:04:50,610 --> 00:04:54,580
We willen niet stoppen voordat dat.

106
00:04:54,580 --> 00:04:56,660
>> Dus als we het definiëren
onze faculteit-functie,

107
00:04:56,660 --> 00:04:58,690
hier is een skelet voor
hoe we dat zouden kunnen doen.

108
00:04:58,690 --> 00:05:03,110
We moeten aansluiten in die twee things--
de base case en het recursieve geval.

109
00:05:03,110 --> 00:05:04,990
Wat is de base case?

110
00:05:04,990 --> 00:05:10,150
Als n gelijk is aan 1, dat is terug 1--
een heel eenvoudig probleem op te lossen.

111
00:05:10,150 --> 00:05:11,890
>> De faculteit van 1: 1.

112
00:05:11,890 --> 00:05:13,860
Het is niet 1 keer niets.

113
00:05:13,860 --> 00:05:15,020
Het is slechts 1.

114
00:05:15,020 --> 00:05:17,170
Het is een heel eenvoudig feit.

115
00:05:17,170 --> 00:05:19,620
En zodat u onze basis geval zijn.

116
00:05:19,620 --> 00:05:24,730
Als we voorbij 1 in deze
functie, zullen we gewoon terug 1.

117
00:05:24,730 --> 00:05:27,320
>> Wat is de recursieve
geval waarschijnlijk eruit?

118
00:05:27,320 --> 00:05:32,445
Voor elk ander nummer
behalve 1, wat is het patroon?

119
00:05:32,445 --> 00:05:35,780
Nou, als we nemen
de faculteit van n,

120
00:05:35,780 --> 00:05:38,160
het n keer de faculteit van n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Als we het nemen van de faculteit van 3,
het 3 keer de faculteit van 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
En dus als we niet
kijken 1, anders

124
00:05:47,330 --> 00:05:51,710
return n keer de
faculteit van n minus 1.

125
00:05:51,710 --> 00:05:53,210
Het is vrij eenvoudig.

126
00:05:53,210 --> 00:05:57,360
>> En omwille van het hebben lichtjes
schonere en meer elegante code,

127
00:05:57,360 --> 00:06:01,440
weten dat als we één regel lussen
of single-lijn voorwaardelijke takken,

128
00:06:01,440 --> 00:06:04,490
we kunnen ontdoen van alle
accolades om hen heen.

129
00:06:04,490 --> 00:06:06,850
Dus we kunnen deze te consolideren om dit.

130
00:06:06,850 --> 00:06:09,640
Deze heeft dezelfde
Deze functionaliteit.

131
00:06:09,640 --> 00:06:13,850
>> Ik ben gewoon het wegnemen van de krullend
bretels, want er is maar één regel

132
00:06:13,850 --> 00:06:18,500
binnenzijde van die voorwaardelijke sprongen.

133
00:06:18,500 --> 00:06:21,160
Dus deze gedragen zich identiek.

134
00:06:21,160 --> 00:06:23,800
Als n gelijk is aan 1, 1 terug.

135
00:06:23,800 --> 00:06:28,351
Anders terug n keer
de faculteit van n minus 1.

136
00:06:28,351 --> 00:06:29,850
Dus we maken het probleem kleiner.

137
00:06:29,850 --> 00:06:33,850
Als n begint als 5, we gaan
terug 5 keer de faculteit van 4.

138
00:06:33,850 --> 00:06:37,100
En we zullen zien in een minuut als we praten
over de oproep stack-- in een andere video

139
00:06:37,100 --> 00:06:39,390
waar we praten over de
noemen stack-- we leren

140
00:06:39,390 --> 00:06:41,630
waarom juist dit proces werkt.

141
00:06:41,630 --> 00:06:46,970
>> Maar terwijl faculteit van 5 zegt:
terug 5 keer faculteit van 4 en 4

142
00:06:46,970 --> 00:06:49,710
gaat zeggen, OK, goed, terug
4 maal de faculteit van 3.

143
00:06:49,710 --> 00:06:51,737
En zoals je kunt zien, zijn we
soort naderen 1.

144
00:06:51,737 --> 00:06:53,820
We zijn steeds dichter en
dichter bij die basisgeval.

145
00:06:53,820 --> 00:06:58,180
>> En zodra we de base case hit,
alle voorgaande functies

146
00:06:58,180 --> 00:07:00,540
het antwoord dat ze op zoek waren.

147
00:07:00,540 --> 00:07:03,900
Faculteit van 2 zei terugkeer
2 maal de faculteit van 1.

148
00:07:03,900 --> 00:07:06,760
Nou, faculteit van 1 rendementen 1.

149
00:07:06,760 --> 00:07:10,090
Zodat de oproep faculteit
van 2 kan 2 keer 1 terug,

150
00:07:10,090 --> 00:07:13,980
en geef die terug naar faculteit van
3, die om dat resultaat wacht.

151
00:07:13,980 --> 00:07:17,110
>> En dan kan het berekenen
het resultaat, 3 keer 2 is 6,

152
00:07:17,110 --> 00:07:18,907
en geef het terug naar faculteit van 4.

153
00:07:18,907 --> 00:07:20,740
En nogmaals, we hebben een
video op de oproep stack

154
00:07:20,740 --> 00:07:23,810
wanneer dit een beetje wordt geïllustreerd
meer dan wat ik nu zeg.

155
00:07:23,810 --> 00:07:25,300
Maar dit is het.

156
00:07:25,300 --> 00:07:29,300
Dit alleen is de oplossing voor
berekenen van de faculteit van een getal.

157
00:07:29,300 --> 00:07:31,527
>> Het is slechts vier regels code.

158
00:07:31,527 --> 00:07:32,610
Dat is wel cool, toch?

159
00:07:32,610 --> 00:07:35,480
Het is een beetje sexy.

160
00:07:35,480 --> 00:07:38,580
>> Dus in het algemeen, maar niet
altijd een recursieve functie

161
00:07:38,580 --> 00:07:41,190
kan een lus in een te vervangen
niet-recursieve functie.

162
00:07:41,190 --> 00:07:46,100
Dus hier, naast elkaar, is de iteratieve
versie van de faculteit-functie.

163
00:07:46,100 --> 00:07:49,650
Beide berekenen
precies hetzelfde.

164
00:07:49,650 --> 00:07:52,170
>> Beiden bereken de faculteit van n.

165
00:07:52,170 --> 00:07:54,990
De versie links
recursie gebruikt om het te doen.

166
00:07:54,990 --> 00:07:58,320
De versie rechts
iteratie gebruikt om het te doen.

167
00:07:58,320 --> 00:08:02,050
>> En bericht, we moeten verklaren
een variabele een integer product.

168
00:08:02,050 --> 00:08:02,940
En dan hebben we lus.

169
00:08:02,940 --> 00:08:06,790
Zolang n groter is dan 0, we
houden dat product door n vermenigvuldigen

170
00:08:06,790 --> 00:08:09,890
en aflopende n totdat
berekenen we het product.

171
00:08:09,890 --> 00:08:14,600
Dus deze twee functies, opnieuw,
doen precies hetzelfde.

172
00:08:14,600 --> 00:08:19,980
Maar ze doen het niet in
precies dezelfde manier.

173
00:08:19,980 --> 00:08:22,430
>> Nu is het mogelijk om
hebben meer dan een base

174
00:08:22,430 --> 00:08:25,770
case of meerdere
recursief geval, afhankelijk

175
00:08:25,770 --> 00:08:27,670
op wat uw functie probeert te doen.

176
00:08:27,670 --> 00:08:31,650
U bent niet per se alleen beperkt tot
een enkele base case of een enkele recursieve

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

178
00:08:32,370 --> 00:08:35,320
Dus een voorbeeld van iets
meerdere base cases

179
00:08:35,320 --> 00:08:37,830
misschien dit-- de
Fibonacci getallenreeks.

180
00:08:37,830 --> 00:08:41,549
>> U herinnert zich misschien uit
basisschool dagen

181
00:08:41,549 --> 00:08:45,740
dat de Fibonacci-reeks is gedefinieerd
zoals dit-- het eerste element is 0.

182
00:08:45,740 --> 00:08:46,890
Het tweede element is 1.

183
00:08:46,890 --> 00:08:49,230
Deze beide zijn per definitie.

184
00:08:49,230 --> 00:08:55,920
>> Dan elke andere wordt gedefinieerd
de som van n en n 1 min 2 min.

185
00:08:55,920 --> 00:09:00,330
Dus het derde element
zou 0 1 plus 1 is.

186
00:09:00,330 --> 00:09:03,280
En dan de vierde element
zou het tweede element, 1 zijn,

187
00:09:03,280 --> 00:09:06,550
plus het derde element, 1.

188
00:09:06,550 --> 00:09:08,507
En dat zou 2.

189
00:09:08,507 --> 00:09:09,340
En zo voort en zo verder.

190
00:09:09,340 --> 00:09:11,680
>> Dus in dit geval hebben we twee base gevallen.

191
00:09:11,680 --> 00:09:14,850
Als n gelijk is aan 1, 0 terug.

192
00:09:14,850 --> 00:09:18,560
Als n gelijk is aan 2, terug 1.

193
00:09:18,560 --> 00:09:25,930
Anders terugkeer van Fibonacci n
plus minus 1 Fibonacci n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Dus dat is meerdere base gevallen.

195
00:09:27,180 --> 00:09:29,271
Hoe zit het met meerdere recursieve gevallen?

196
00:09:29,271 --> 00:09:31,520
Nou, er is iets
genaamd de Collatz vermoeden.

197
00:09:31,520 --> 00:09:34,630
Ik ga niet zeggen,
je weet wat dat is,

198
00:09:34,630 --> 00:09:38,170
want het is eigenlijk onze laatste
probleem voor deze video.

199
00:09:38,170 --> 00:09:43,220
En het is onze oefening
samen te werken.

200
00:09:43,220 --> 00:09:46,760
>> Dus hier is wat de
Collatz vermoeden is--

201
00:09:46,760 --> 00:09:48,820
het geldt voor elk positief geheel getal.

202
00:09:48,820 --> 00:09:51,500
En speculeert dat het
altijd mogelijk om terug te krijgen

203
00:09:51,500 --> 00:09:55,060
1 als u de volgende stappen.

204
00:09:55,060 --> 00:09:57,560
Wanneer n is 1, stoppen.

205
00:09:57,560 --> 00:10:00,070
We moeten terug naar 1 als n 1 is.

206
00:10:00,070 --> 00:10:05,670
>> Anders, door deze
Werkwijze weer n gedeeld door 2.

207
00:10:05,670 --> 00:10:08,200
En kijk of je kunt terug naar 1.

208
00:10:08,200 --> 00:10:13,260
Anders, als n oneven is, gaan door
Dit proces weer 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
of 3 maal n plus 1.

210
00:10:15,552 --> 00:10:17,010
Dus hier hebben we een enkele base case.

211
00:10:17,010 --> 00:10:18,430
Als n gelijk is aan 1, stoppen.

212
00:10:18,430 --> 00:10:20,230
We zijn niet te doen meer recursie.

213
00:10:20,230 --> 00:10:23,730
>> Maar we hebben twee recursieve gevallen.

214
00:10:23,730 --> 00:10:28,750
Als n even is, doen we een recursieve
geval roeping n gedeeld door 2.

215
00:10:28,750 --> 00:10:33,950
Als n oneven is, doen we een andere
recursieve geval op 3 maal n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> En zo het doel van deze video is
om een ​​tweede te nemen, de video te pauzeren,

217
00:10:39,120 --> 00:10:42,440
en probeer dit schrijf
recursieve functie Collatz

218
00:10:42,440 --> 00:10:47,640
waar u passeren een waarde n en
berekent hoeveel stappen die zij

219
00:10:47,640 --> 00:10:52,430
neemt tot 1 te krijgen als u begint met n
en volg je die stappen boven.

220
00:10:52,430 --> 00:10:56,660
Wanneer n is 1, duurt 0 stappen.

221
00:10:56,660 --> 00:11:00,190
Anders gaat het om
een stap plus nochtans

222
00:11:00,190 --> 00:11:06,200
vele stappen die nodig aan beide n
gedeeld door 2 als n even of 3n plus 1

223
00:11:06,200 --> 00:11:08,100
als n oneven is.

224
00:11:08,100 --> 00:11:11,190
>> Nu, ik heb op het scherm zetten hier
een paar van de test dingen voor je,

225
00:11:11,190 --> 00:11:15,690
een paar testen gevallen voor u, om te zien
Wat deze verschillende Collatz getallen,

226
00:11:15,690 --> 00:11:17,440
alsmede een illustratie
van de stappen die

227
00:11:17,440 --> 00:11:20,390
moet door middel van dus je kunt om zijn gegaan
soort van zien dit proces in actie.

228
00:11:20,390 --> 00:11:24,222
Als n gelijk is aan
1, Collatz van n is 0.

229
00:11:24,222 --> 00:11:26,180
Je hoeft niet te doen
alles om terug te gaan naar 1.

230
00:11:26,180 --> 00:11:27,600
Je bent er al.

231
00:11:27,600 --> 00:11:30,550
>> Wanneer n 2 is, duurt
een stap naar 1 te krijgen.

232
00:11:30,550 --> 00:11:31,810
Je begint met 2.

233
00:11:31,810 --> 00:11:33,100
Welnu, 2 niet gelijk is aan 1.

234
00:11:33,100 --> 00:11:36,580
Dus het gaat om één stap
plus hoeveel stappen die zij

235
00:11:36,580 --> 00:11:38,015
neemt n gedeeld door 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 gedeeld door 2: 1.

238
00:11:42,910 --> 00:11:47,200
Dus het duurt een stap plus nochtans
vele stappen die nodig is om 1.

239
00:11:47,200 --> 00:11:49,720
1 neemt nul stappen.

240
00:11:49,720 --> 00:11:52,370
>> 3, zoals u kunt zien, is er
een flink aantal stappen die betrokken.

241
00:11:52,370 --> 00:11:53,590
Je gaat van 3.

242
00:11:53,590 --> 00:11:56,710
En dan ga je naar
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Het duurt zeven stappen om terug te keren naar 1.

244
00:11:58,804 --> 00:12:01,220
En zoals je kunt zien, is er een
paar andere testcases hier

245
00:12:01,220 --> 00:12:02,470
aan het testen van uw programma.

246
00:12:02,470 --> 00:12:03,970
Dus nogmaals, pauzeren de video.

247
00:12:03,970 --> 00:12:09,210
En ik ga terugspringen nu
Wat het eigenlijke proces hier

248
00:12:09,210 --> 00:12:11,390
wat dit vermoeden is.

249
00:12:11,390 --> 00:12:14,140
>> Kijk of je kunt achterhalen
hoe Collatz n definiëren

250
00:12:14,140 --> 00:12:19,967
zodat het berekent hoeveel
de stappen die het duurt om 1 te krijgen.

251
00:12:19,967 --> 00:12:23,050
Dus hopelijk, u de video onderbroken hebben
en je bent niet alleen op me te wachten

252
00:12:23,050 --> 00:12:25,820
u hier het antwoord te geven.

253
00:12:25,820 --> 00:12:29,120
Maar als je, nou ja,
hier is het antwoord toch.

254
00:12:29,120 --> 00:12:33,070
>> Dus hier is een mogelijke definitie
het Collatz functie.

255
00:12:33,070 --> 00:12:35,610
Onze basis case-- als n
gelijk aan 1, we terugkeren 0.

256
00:12:35,610 --> 00:12:38,250
Het bevat geen te nemen
stappen om terug te keren naar 1.

257
00:12:38,250 --> 00:12:42,710
>> Anders, we hebben twee recursieve cases--
één voor de even nummers en één voor de oneven.

258
00:12:42,710 --> 00:12:47,164
De manier waarop ik te testen voor even getallen
is om te controleren of n mod 2 gelijk is aan 0.

259
00:12:47,164 --> 00:12:49,080
Dit is in principe weer,
de vraag te stellen,

260
00:12:49,080 --> 00:12:54,050
als je herinneren wat mod is-- als ik
kloof n door 2 is er geen rest?

261
00:12:54,050 --> 00:12:55,470
Dat zou een even getal.

262
00:12:55,470 --> 00:13:01,370
>> En dus als n mod 2 is gelijk aan 0 is
testen is dit een even getal.

263
00:13:01,370 --> 00:13:04,250
Als dat zo is, wil ik terugkeren 1,
want dit is zeker

264
00:13:04,250 --> 00:13:09,270
het nemen van een stap plus Collatz van
welk getal is de helft van mij.

265
00:13:09,270 --> 00:13:13,910
Anders, ik wil terugkeren 1
plus Collatz 3 keer n plus 1.

266
00:13:13,910 --> 00:13:16,060
Dat was de andere
recursieve stap die we

267
00:13:16,060 --> 00:13:19,470
kunnen nemen om het te berekenen
Collatz-- het aantal stappen

268
00:13:19,470 --> 00:13:22,610
het duurt om terug te krijgen
1 een nummer.

269
00:13:22,610 --> 00:13:24,610
Dus hopelijk, dit voorbeeld
gaf je een beetje

270
00:13:24,610 --> 00:13:26,620
van een voorproefje van recursieve procedures.

271
00:13:26,620 --> 00:13:30,220
Hopelijk je denkt code is een
beetje mooier indien uitgevoerd

272
00:13:30,220 --> 00:13:32,760
in een elegante, recursieve manier.

273
00:13:32,760 --> 00:13:35,955
Maar zelfs indien niet, recursie is een
echt krachtige tool toch.

274
00:13:35,955 --> 00:13:38,330
En dus is het zeker iets
om je hoofd rond te krijgen,

275
00:13:38,330 --> 00:13:41,360
want je zult in staat zijn om te creëren
pretty cool programma's met behulp van recursie

276
00:13:41,360 --> 00:13:45,930
die anders ingewikkeld te schrijven
als je met behulp van loops en iteratie.

277
00:13:45,930 --> 00:13:46,980
Ik ben Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Dit is CS50.

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