1
00:00:00,000 --> 00:00:05,860
>> [Speel van musiek]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Jy dink waarskynlik dat
kode is net gebruik om 'n taak uit te voer.

3
00:00:09,530 --> 00:00:10,450
Jy skryf dit uit.

4
00:00:10,450 --> 00:00:11,664
Dit doen iets.

5
00:00:11,664 --> 00:00:12,580
Dit is pretty much dit.

6
00:00:12,580 --> 00:00:13,160
>> Jy stel nie.

7
00:00:13,160 --> 00:00:13,993
Jy loop die program.

8
00:00:13,993 --> 00:00:15,370
Jy is goed om te gaan.

9
00:00:15,370 --> 00:00:17,520
>> Maar glo dit of nie, as
jy kode vir 'n lang tyd,

10
00:00:17,520 --> 00:00:20,550
jy eintlik kan kom om te sien
kode as iets wat mooi.

11
00:00:20,550 --> 00:00:23,275
Dit los 'n probleem in
'n baie interessante manier,

12
00:00:23,275 --> 00:00:26,510
of daar is net iets wat regtig
netjiese oor die manier waarop dit lyk.

13
00:00:26,510 --> 00:00:28,750
Jy kan lag
by my, maar dit is waar.

14
00:00:28,750 --> 00:00:31,530
En rekursie is een manier
om soort van kry hierdie idee

15
00:00:31,530 --> 00:00:34,090
pragtige, elegante-soek-kode.

16
00:00:34,090 --> 00:00:37,740
Dit los probleme op maniere wat
is interessant, maklik om te visualiseer,

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

18
00:00:39,810 --> 00:00:43,190
>> Die manier waarop rekursie werke
is, 'n rekursiewe funksie

19
00:00:43,190 --> 00:00:49,291
word gedefinieer as 'n funksie wat roep
homself as deel van die uitvoering daarvan.

20
00:00:49,291 --> 00:00:51,790
Dit lyk dalk 'n bietjie vreemd,
en ons sal 'n bietjie kyk

21
00:00:51,790 --> 00:00:53,750
oor hoe dit werk in 'n oomblik.

22
00:00:53,750 --> 00:00:55,560
Maar weereens, hierdie
rekursiewe prosedures

23
00:00:55,560 --> 00:00:57,730
gaan so elegant te wees
want hulle gaan

24
00:00:57,730 --> 00:01:00,410
om hierdie probleem op te los sonder
met al hierdie ander funksies

25
00:01:00,410 --> 00:01:02,710
of die lang lusse.

26
00:01:02,710 --> 00:01:06,310
Jy sal sien dat hierdie rekursiewe
prosedures gaan so kort lyk.

27
00:01:06,310 --> 00:01:10,610
En hulle het regtig gaan maak
jou kode lyk baie mooier.

28
00:01:10,610 --> 00:01:12,560
>> Ek sal jou 'n voorbeeld te gee
van hierdie om te sien hoe

29
00:01:12,560 --> 00:01:14,880
'n rekursiewe prosedure kan gedefinieer word.

30
00:01:14,880 --> 00:01:18,202
So as jy vertroud is met hierdie is
van wiskunde klas baie jare gelede,

31
00:01:18,202 --> 00:01:20,910
Daar is iets genoem die
faktoriaal funksie, wat gewoonlik

32
00:01:20,910 --> 00:01:25,340
aangedui as 'n uitroepteken, wat
word gedefinieer as alle positiewe heelgetalle.

33
00:01:25,340 --> 00:01:28,850
En die manier waarop N
faktoriaal bereken

34
00:01:28,850 --> 00:01:31,050
is jy al vermenigvuldig
die nommers minder as

35
00:01:31,050 --> 00:01:33,750
of gelyk aan N saam op
al die heelgetalle minder as

36
00:01:33,750 --> 00:01:34,880
of gelyk aan N saam.

37
00:01:34,880 --> 00:01:39,850
>> So 5 faktoriaal is 5 keer
4 keer 3 keer 2 keer 1.

38
00:01:39,850 --> 00:01:43,020
En 4 faktoriaal is 4 keer
3 keer 2 keer 1 en so aan.

39
00:01:43,020 --> 00:01:44,800
Jy kry die idee.

40
00:01:44,800 --> 00:01:47,060
>> As programmeerders, ons doen nie
gebruik n, uitroepteken.

41
00:01:47,060 --> 00:01:51,840
So sal ons die faktoriaal definieer
funksie as 'n feit van n.

42
00:01:51,840 --> 00:01:56,897
En ons sal faktoriaal gebruik om te skep
'n rekursiewe oplossing vir 'n probleem.

43
00:01:56,897 --> 00:01:59,230
En ek dink jy kan vind
dat dit 'n baie meer visueel

44
00:01:59,230 --> 00:02:02,380
beroep as die iteratiewe
weergawe van hierdie, wat

45
00:02:02,380 --> 00:02:05,010
Ons sal ook 'n blik op in 'n oomblik.

46
00:02:05,010 --> 00:02:08,310
>> So hier is 'n paar van die
facts-- woordspeling intended--

47
00:02:08,310 --> 00:02:10,169
oor die factorial--
faktoriaal funksie.

48
00:02:10,169 --> 00:02:13,090
Die faktoriaal van 1, soos ek gesê het, is 1.

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

50
00:02:15,690 --> 00:02:18,470
Die faktoriaal van 3 is 3
keer 2 keer 1, en so aan.

51
00:02:18,470 --> 00:02:20,810
Ons het gepraat oor 4 en 5 reeds.

52
00:02:20,810 --> 00:02:23,940
>> Maar kyk na hierdie, is dit nie so nie?

53
00:02:23,940 --> 00:02:28,220
Is dit nie faktoriaal van 2 net
2 keer die faktoriaal van 1?

54
00:02:28,220 --> 00:02:31,130
Ek bedoel, die faktoriaal van 1 is 1.

55
00:02:31,130 --> 00:02:34,940
So hoekom kan ons nie sê net dat,
sedert faktoriaal van 2 is 2 keer 1,

56
00:02:34,940 --> 00:02:38,520
Dit is regtig net 2 keer
die faktoriaal van 1?

57
00:02:38,520 --> 00:02:40,900
>> En dan brei die idee,
is nie die faktoriaal van 3

58
00:02:40,900 --> 00:02:44,080
net 3 keer die faktoriaal van 2?

59
00:02:44,080 --> 00:02:50,350
En die faktoriaal van 4 is 4 keer
die faktoriaal van 3, en so aan?

60
00:02:50,350 --> 00:02:52,530
Trouens, die faktoriaal
van enige aantal kan net

61
00:02:52,530 --> 00:02:54,660
as ons uitgedruk soort
van voer dit uit vir ewig.

62
00:02:54,660 --> 00:02:56,870
Ons kan soort van veralgemeen
die faktoriaal probleem

63
00:02:56,870 --> 00:02:59,910
as dit is n keer die
faktoriaal van N minus 1.

64
00:02:59,910 --> 00:03:04,840
Dit is n keer die produk van
al die getalle minder as ek.

65
00:03:04,840 --> 00:03:08,890
>> Hierdie idee, hierdie
veralgemening van die probleem,

66
00:03:08,890 --> 00:03:13,410
kan ons rekursief
definieer die faktoriaal funksie.

67
00:03:13,410 --> 00:03:15,440
Wanneer jy 'n funksie te definieer
rekursief, daar is

68
00:03:15,440 --> 00:03:17,470
twee dinge wat nodig is om 'n deel van dit te wees.

69
00:03:17,470 --> 00:03:20,990
Jy moet iets genoem 'n
basis geval, wat, wanneer jy dit aktiveer,

70
00:03:20,990 --> 00:03:22,480
sal die rekursiewe proses te stop.

71
00:03:22,480 --> 00:03:25,300
>> Anders, 'n funksie wat roep
itself-- as jy dalk imagine--

72
00:03:25,300 --> 00:03:26,870
kon vir ewig gaan.

73
00:03:26,870 --> 00:03:29,047
Funksie noem die funksie
noem die funksie oproepe

74
00:03:29,047 --> 00:03:30,380
die funksie noem die funksie.

75
00:03:30,380 --> 00:03:32,380
As jy nie 'n manier het
om dit te stop, jou program

76
00:03:32,380 --> 00:03:34,760
sal effektief vas
teen 'n oneindige lus.

77
00:03:34,760 --> 00:03:37,176
Dit sal uiteindelik crash,
want dit sal uit die geheue uit te voer.

78
00:03:37,176 --> 00:03:38,990
Maar dit is langs die punt.

79
00:03:38,990 --> 00:03:42,210
>> Ons moet 'n ander manier om te stop het
dinge behalwe ons program gekraak,

80
00:03:42,210 --> 00:03:46,010
omdat 'n program wat ineenstortings is
waarskynlik nie mooi of elegant.

81
00:03:46,010 --> 00:03:47,690
En so het ons dit die basis geval noem.

82
00:03:47,690 --> 00:03:50,610
Dit is 'n eenvoudige oplossing
om 'n probleem wat tot stilstand kom

83
00:03:50,610 --> 00:03:52,770
die rekursiewe proses te voorkom.

84
00:03:52,770 --> 00:03:55,220
So dit is 'n deel van
'n rekursiewe funksie.

85
00:03:55,220 --> 00:03:56,820
>> Die tweede deel is die rekursiewe geval.

86
00:03:56,820 --> 00:03:59,195
En dit is waar die rekursie
sal eintlik plaasvind.

87
00:03:59,195 --> 00:04:02,200
Dit is waar die
funksie sal self noem.

88
00:04:02,200 --> 00:04:05,940
>> Dit sal hom nie in presies noem
op dieselfde manier het dit genoem.

89
00:04:05,940 --> 00:04:08,880
Dit sal 'n effense variasie wees
dit maak die probleem is dit

90
00:04:08,880 --> 00:04:11,497
probeer om 'n bietjie kleiner Teeny op te los.

91
00:04:11,497 --> 00:04:14,330
Maar dit gaan oor die algemeen die bok
van die oplossing van die grootste deel van die oplossing

92
00:04:14,330 --> 00:04:17,450
na 'n ander oproep in die ry.

93
00:04:17,450 --> 00:04:20,290
>> Watter van hierdie lyk
soos die basis geval hier?

94
00:04:20,290 --> 00:04:25,384
Watter een van hierdie lyk soos die
eenvoudigste oplossing vir 'n probleem?

95
00:04:25,384 --> 00:04:27,550
Ons het 'n klomp van die factorials,
en ons kon voortgaan

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

97
00:04:30,470 --> 00:04:34,130
>> Maar een van hierdie lyk soos 'n
goeie saak na die basis geval te wees.

98
00:04:34,130 --> 00:04:35,310
Dit is 'n baie eenvoudige oplossing.

99
00:04:35,310 --> 00:04:37,810
Ons het nie iets spesiaals te doen.

100
00:04:37,810 --> 00:04:40,560
>> Die faktoriaal van 1 is net 1.

101
00:04:40,560 --> 00:04:42,790
Ons het nie nodig om enige te doen
vermenigvuldiging at all.

102
00:04:42,790 --> 00:04:45,248
Dit lyk asof ons gaan
om te probeer en hierdie probleem op te los,

103
00:04:45,248 --> 00:04:47,600
en ons na die stop nodig
rekursie iewers,

104
00:04:47,600 --> 00:04:50,610
waarskynlik wil ons om te stop
dit wanneer ons by 1.

105
00:04:50,610 --> 00:04:54,580
Ons wil nie om te stop voor dit.

106
00:04:54,580 --> 00:04:56,660
>> So as ons definieer
ons faktoriaal funksie,

107
00:04:56,660 --> 00:04:58,690
hier is 'n geraamte vir
hoe ons dit kan doen.

108
00:04:58,690 --> 00:05:03,110
Ons moet prop in daardie twee things--
die basis geval en die rekursiewe geval.

109
00:05:03,110 --> 00:05:04,990
Wat is die basis geval?

110
00:05:04,990 --> 00:05:10,150
As n is gelyk aan 1, terugkeer 1-- dis
'n baie eenvoudige probleem op te los.

111
00:05:10,150 --> 00:05:11,890
>> Die faktoriaal van 1 is 1.

112
00:05:11,890 --> 00:05:13,860
Dit is nie 1 keer nie.

113
00:05:13,860 --> 00:05:15,020
Dis net 1.

114
00:05:15,020 --> 00:05:17,170
Dit is 'n baie maklike feit.

115
00:05:17,170 --> 00:05:19,620
En so kan ons basis geval wees.

116
00:05:19,620 --> 00:05:24,730
As ons verby 1 na hierdie
funksie, sal ons net terug 1.

117
00:05:24,730 --> 00:05:27,320
>> Wat is die rekursiewe
geval waarskynlik lyk?

118
00:05:27,320 --> 00:05:32,445
Vir elke ander getal
Behalwe 1, wat is die patroon?

119
00:05:32,445 --> 00:05:35,780
Wel, as ons neem
die faktoriaal van n,

120
00:05:35,780 --> 00:05:38,160
dit is n keer die faktoriaal van N minus 1.

121
00:05:38,160 --> 00:05:42,130
>> As ons neem die faktoriaal van 3,
dit is 3 maal die faktoriaal 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 so as ons nie
op soek na 1, anders

124
00:05:47,330 --> 00:05:51,710
terugkeer N keer die
faktoriaal van N minus 1.

125
00:05:51,710 --> 00:05:53,210
Dit is redelik eenvoudig.

126
00:05:53,210 --> 00:05:57,360
>> En ter wille van 'n effens
skoner en meer elegante kode,

127
00:05:57,360 --> 00:06:01,440
weet dat as ons enkel-lyn loops
of enkel-line voorwaardelike takke,

128
00:06:01,440 --> 00:06:04,490
ons kan ontslae te raak van al die
krulhakies rondom hulle.

129
00:06:04,490 --> 00:06:06,850
So kan ons dit konsolideer om hierdie.

130
00:06:06,850 --> 00:06:09,640
Dit het presies dieselfde
funksie soos hierdie.

131
00:06:09,640 --> 00:06:13,850
>> Ek is net weg te neem die krullerige
draadjies, want daar is net een lyn

132
00:06:13,850 --> 00:06:18,500
binnekant van die voorwaardelike takke.

133
00:06:18,500 --> 00:06:21,160
So het hierdie gedra identies.

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

135
00:06:23,800 --> 00:06:28,351
Anders terugkeer N tye
die faktoriaal van N minus 1.

136
00:06:28,351 --> 00:06:29,850
Ons is so maak die probleem kleiner.

137
00:06:29,850 --> 00:06:33,850
As n begin as 5, gaan ons
terugkeer 5 keer die faktoriaal van 4.

138
00:06:33,850 --> 00:06:37,100
En ons sal sien in 'n minuut wanneer ons praat
oor die oproep stack-- in 'n ander video

139
00:06:37,100 --> 00:06:39,390
waar ons praat oor die
noem stack-- ons sal leer

140
00:06:39,390 --> 00:06:41,630
oor hoekom juis hierdie proses werk.

141
00:06:41,630 --> 00:06:46,970
>> Maar terwyl faktoriaal van 5 sê
terugkeer 5 keer faktoriaal van 4, en 4

142
00:06:46,970 --> 00:06:49,710
gaan om te sê, OK, goed, terugkeer
4 keer die faktoriaal van 3.

143
00:06:49,710 --> 00:06:51,737
En soos jy kan sien, is ons
soort van nader 1.

144
00:06:51,737 --> 00:06:53,820
Ons kry nader en
nader aan daardie basis geval.

145
00:06:53,820 --> 00:06:58,180
>> En sodra ons die basis geval getref,
al die vorige funksies

146
00:06:58,180 --> 00:07:00,540
het die antwoord hulle soek.

147
00:07:00,540 --> 00:07:03,900
Faktoriaal van 2 sê terugkeer
2 keer die faktoriaal van 1.

148
00:07:03,900 --> 00:07:06,760
Wel, faktoriaal van 1 opbrengste 1.

149
00:07:06,760 --> 00:07:10,090
So het die oproep vir faktoriaal
van 2 kan 2 keer 1 terugkeer,

150
00:07:10,090 --> 00:07:13,980
en gee dat terug na faktoriaal van
3, wat vir daardie gevolg wag.

151
00:07:13,980 --> 00:07:17,110
>> En dan kan dit te bereken
die resultaat, 3 keer 2 is 6,

152
00:07:17,110 --> 00:07:18,907
en gee dit terug na faktoriaal van 4.

153
00:07:18,907 --> 00:07:20,740
En weer, ons het 'n
video op die oproep stapel

154
00:07:20,740 --> 00:07:23,810
waar dit 'n bietjie geïllustreer
meer as wat ek nou sê.

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

156
00:07:25,300 --> 00:07:29,300
Dit alleen is die oplossing vir
die berekening van die faktoriaal van 'n aantal.

157
00:07:29,300 --> 00:07:31,527
>> Dit is slegs vier reëls van die kode.

158
00:07:31,527 --> 00:07:32,610
Dit is pretty cool, reg?

159
00:07:32,610 --> 00:07:35,480
Dit is soort van sexy.

160
00:07:35,480 --> 00:07:38,580
>> So in die algemeen, maar nie
altyd 'n rekursiewe funksie

161
00:07:38,580 --> 00:07:41,190
kan 'n lus in 'n plek van
nie-rekursiewe funksie.

162
00:07:41,190 --> 00:07:46,100
So hier, langs mekaar, is die iteratiewe
weergawe van die faktoriaal funksie.

163
00:07:46,100 --> 00:07:49,650
Beide van hierdie bereken
presies dieselfde ding.

164
00:07:49,650 --> 00:07:52,170
>> Hulle het albei bereken die faktoriaal van n.

165
00:07:52,170 --> 00:07:54,990
Die weergawe aan die linkerkant
gebruik rekursie om dit te doen.

166
00:07:54,990 --> 00:07:58,320
Die weergawe op die regte
gebruik iterasie om dit te doen.

167
00:07:58,320 --> 00:08:02,050
>> En kennis, ons het om te verklaar
'n veranderlike 'n heelgetal produk.

168
00:08:02,050 --> 00:08:02,940
En dan het ons lus.

169
00:08:02,940 --> 00:08:06,790
So lank as N groter as 0, ons
hou dat die produk deur te vermenigvuldig N

170
00:08:06,790 --> 00:08:09,890
en decrementing N totdat
Ons bereken die produk.

171
00:08:09,890 --> 00:08:14,600
So het hierdie twee funksies, weer,
doen presies dieselfde ding.

172
00:08:14,600 --> 00:08:19,980
Maar hulle doen dit nie in
presies dieselfde manier.

173
00:08:19,980 --> 00:08:22,430
>> Nou, is dit moontlik om
het meer as een basis

174
00:08:22,430 --> 00:08:25,770
geval of meer as een
rekursiewe geval, afhangende

175
00:08:25,770 --> 00:08:27,670
oor wat jou funksie is om te probeer doen.

176
00:08:27,670 --> 00:08:31,650
Jy is nie noodwendig net beperk tot
'n enkele basis geval of 'n enkele rekursiewe

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

178
00:08:32,370 --> 00:08:35,320
So 'n voorbeeld van iets
met verskeie base gevalle

179
00:08:35,320 --> 00:08:37,830
dalk this-- die
Fibonacci getal ry.

180
00:08:37,830 --> 00:08:41,549
>> Jy kan onthou uit
laerskool dae

181
00:08:41,549 --> 00:08:45,740
dat die Fibonacci-ry word gedefinieer
soos this-- die eerste element is 0.

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

183
00:08:46,890 --> 00:08:49,230
Beide van hulle is net per definisie.

184
00:08:49,230 --> 00:08:55,920
>> Dan elke ander element gedefinieer
as die som van N minus 1 en N minus 2.

185
00:08:55,920 --> 00:09:00,330
So die derde element
sou wees 0 plus 1 is 1.

186
00:09:00,330 --> 00:09:03,280
En dan die vierde element
sou die tweede element, 1 wees,

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

188
00:09:06,550 --> 00:09:08,507
En dit sou wees 2.

189
00:09:08,507 --> 00:09:09,340
En so aan en so aan.

190
00:09:09,340 --> 00:09:11,680
>> So in hierdie geval, het ons twee base gevalle.

191
00:09:11,680 --> 00:09:14,850
As n is gelyk aan 1, terugkeer 0.

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

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

194
00:09:25,930 --> 00:09:27,180
>> So dit is verskeie base gevalle.

195
00:09:27,180 --> 00:09:29,271
Wat van veelvuldige rekursiewe gevalle?

196
00:09:29,271 --> 00:09:31,520
Wel, daar is iets
genoem die Collatz veronderstelling.

197
00:09:31,520 --> 00:09:34,630
Ek gaan nie om te sê,
jy weet wat dit is,

198
00:09:34,630 --> 00:09:38,170
want dit is eintlik ons ​​finale
probleem vir hierdie spesifieke video.

199
00:09:38,170 --> 00:09:43,220
En dit is ons oefening
om saam te werk.

200
00:09:43,220 --> 00:09:46,760
>> So hier is wat die
Collatz veronderstelling is--

201
00:09:46,760 --> 00:09:48,820
dit is van toepassing op elke positiewe heelgetal.

202
00:09:48,820 --> 00:09:51,500
En dit bespiegel dat dit
altyd moontlik om terug te kry

203
00:09:51,500 --> 00:09:55,060
1 as jy volg hierdie stappe.

204
00:09:55,060 --> 00:09:57,560
Indien n '1, stop.

205
00:09:57,560 --> 00:10:00,070
Ons het terug na 1 as n 1.

206
00:10:00,070 --> 00:10:05,670
>> Andersins, gaan deur hierdie
proses weer op N gedeel deur 2.

207
00:10:05,670 --> 00:10:08,200
En kyk of jy kan terug te kry om 1.

208
00:10:08,200 --> 00:10:13,260
Anders, as n onewe, gaan deur
hierdie proses weer op 3n plus 1,

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

210
00:10:15,552 --> 00:10:17,010
So hier het ons 'n enkele basis geval.

211
00:10:17,010 --> 00:10:18,430
As n is gelyk aan 1, stop.

212
00:10:18,430 --> 00:10:20,230
Ons is nie om enige meer rekursie.

213
00:10:20,230 --> 00:10:23,730
>> Maar ons het twee rekursiewe gevalle.

214
00:10:23,730 --> 00:10:28,750
As n ewe, ons doen een rekursiewe
geval, bel N gedeel deur 2.

215
00:10:28,750 --> 00:10:33,950
As n onewe, ons doen 'n ander
rekursiewe geval op 3 keer n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> En so het die doel vir hierdie video is
om 'n tweede neem, breek die video,

217
00:10:39,120 --> 00:10:42,440
en probeer en skryf dit
rekursiewe funksie Collatz

218
00:10:42,440 --> 00:10:47,640
waar jy slaag in 'n waarde n, en
dit bereken hoeveel stappe dit

219
00:10:47,640 --> 00:10:52,430
neem om 1 te kry as jy begin van N
en jy volg die stappe bo.

220
00:10:52,430 --> 00:10:56,660
Indien n '1, neem dit 0 stappe.

221
00:10:56,660 --> 00:11:00,190
Andersins, dit gaan
neem 'n stap plus egter

222
00:11:00,190 --> 00:11:06,200
baie stappe wat dit neem op óf N
gedeel deur 2 as n ewe is, of 3n plus 1

223
00:11:06,200 --> 00:11:08,100
As n onewe.

224
00:11:08,100 --> 00:11:11,190
>> Nou, ek het op die skerm hier sit
'n paar van die toets dinge vir jou,

225
00:11:11,190 --> 00:11:15,690
'n paar van toetse gevalle vir jou, om te sien
wat hierdie verskillende Collatz getalle is,

226
00:11:15,690 --> 00:11:17,440
en ook 'n illustrasie
van die stappe wat

227
00:11:17,440 --> 00:11:20,390
moet deur sodat jy kan om weg
soort van sien hierdie proses in aksie.

228
00:11:20,390 --> 00:11:24,222
So as N is gelyk aan
1, Collatz van N is 0.

229
00:11:24,222 --> 00:11:26,180
Jy hoef nie te doen
niks om terug te kry om 1.

230
00:11:26,180 --> 00:11:27,600
Jy is reeds daar.

231
00:11:27,600 --> 00:11:30,550
>> As N is 2, dit neem
een stap na 1 te kry.

232
00:11:30,550 --> 00:11:31,810
Jy begin met 2.

233
00:11:31,810 --> 00:11:33,100
Wel, 2 is nie gelyk aan 1.

234
00:11:33,100 --> 00:11:36,580
So dit gaan 'n stap wees
plus egter baie stappe dit

235
00:11:36,580 --> 00:11:38,015
neem op N gedeel deur 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 gedeel deur 2 is 1.

238
00:11:42,910 --> 00:11:47,200
So dit neem 'n stap plus egter
baie stappe wat dit neem vir 1.

239
00:11:47,200 --> 00:11:49,720
1 neem nul stappe.

240
00:11:49,720 --> 00:11:52,370
>> Vir 3, soos jy kan sien, is daar
nogal 'n paar stappe wat betrokke is.

241
00:11:52,370 --> 00:11:53,590
Jy gaan van 3.

242
00:11:53,590 --> 00:11:56,710
En dan gaan jy na
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Dit neem sewe stappe om terug te kry om 1.

244
00:11:58,804 --> 00:12:01,220
En soos jy kan sien, is daar 'n
paar ander toets gevalle hier

245
00:12:01,220 --> 00:12:02,470
om te toets jou program.

246
00:12:02,470 --> 00:12:03,970
So weer, breek die video.

247
00:12:03,970 --> 00:12:09,210
En ek gaan spring nou terug om
wat die werklike proses is hier,

248
00:12:09,210 --> 00:12:11,390
wat hierdie vermoede is.

249
00:12:11,390 --> 00:12:14,140
>> Kyk of jy kan uitvind
hoe om Collatz van N definieer

250
00:12:14,140 --> 00:12:19,967
sodat dit bereken hoeveel
stappe wat dit neem om 1 te kry.

251
00:12:19,967 --> 00:12:23,050
So hopelik jy die video gestop het
en jy is nie net wag vir my

252
00:12:23,050 --> 00:12:25,820
om vir jou die antwoord hier gee.

253
00:12:25,820 --> 00:12:29,120
Maar as jy, wel,
Hier is die antwoord in elk geval.

254
00:12:29,120 --> 00:12:33,070
>> So hier is 'n moontlike definisie
van die Collatz funksie.

255
00:12:33,070 --> 00:12:35,610
Ons basis case-- as n
gelyk aan 1, ons terugkeer 0.

256
00:12:35,610 --> 00:12:38,250
Dit maak nie neem
stappe om terug te kry om 1.

257
00:12:38,250 --> 00:12:42,710
>> Andersins, het ons twee rekursiewe cases--
een vir ewe getalle en een vir vreemd.

258
00:12:42,710 --> 00:12:47,164
Die manier waarop ek toets vir ewe getalle
is om te kyk of n mod 2 is gelyk aan 0.

259
00:12:47,164 --> 00:12:49,080
Dit is basies, weer,
vra die vraag,

260
00:12:49,080 --> 00:12:54,050
as jy onthou wat mod is-- as ek
verdeel N 2 deur daar is geen res?

261
00:12:54,050 --> 00:12:55,470
Dit sou 'n ewe getal wees.

262
00:12:55,470 --> 00:13:01,370
>> En so as N mod 2 is gelyk aan 0 is
toets is dit 'n ewe getal.

263
00:13:01,370 --> 00:13:04,250
As dit so is, wil ek teruggaan 1,
want dit is beslis

264
00:13:04,250 --> 00:13:09,270
neem 'n stap plus Collatz van
watter getal is die helfte van my.

265
00:13:09,270 --> 00:13:13,910
Anders, ek wil om terug te keer 1
plus Collatz van 3 keer n plus 1.

266
00:13:13,910 --> 00:13:16,060
Dit was die ander
rekursiewe stap dat ons

267
00:13:16,060 --> 00:13:19,470
kan neem om die te bereken
Collatz-- die aantal stappe

268
00:13:19,470 --> 00:13:22,610
dit neem om terug te kry
1 'n nommer.

269
00:13:22,610 --> 00:13:24,610
So hopelik hierdie voorbeeld
het jy 'n bietjie

270
00:13:24,610 --> 00:13:26,620
van 'n voorsmakie van rekursiewe prosedures.

271
00:13:26,620 --> 00:13:30,220
Hopelik jy dink kode is 'n
bietjie mooier indien geïmplementeer

272
00:13:30,220 --> 00:13:32,760
in 'n elegante, rekursiewe manier.

273
00:13:32,760 --> 00:13:35,955
Maar selfs indien nie, is 'n rekursie
regtig kragtige instrument nietemin.

274
00:13:35,955 --> 00:13:38,330
En so is dit beslis iets
om jou kop om te kry,

275
00:13:38,330 --> 00:13:41,360
omdat jy sal in staat wees om te skep
pretty cool programme met behulp van rekursie

276
00:13:41,360 --> 00:13:45,930
wat anders kan komplekse te skryf wees
As jy met behulp van lusse en iterasie.

277
00:13:45,930 --> 00:13:46,980
Ek is Doug Lloyd.

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

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