1
00:00:00,000 --> 00:00:05,860
>> [Muusika mängib]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Sa ilmselt arvad, et
koodi kasutatakse vaid täita ülesanne.

3
00:00:09,530 --> 00:00:10,450
Sa kirjutad selle välja.

4
00:00:10,450 --> 00:00:11,664
Ta teeb midagi.

5
00:00:11,664 --> 00:00:12,580
See on päris palju see.

6
00:00:12,580 --> 00:00:13,160
>> Sa kompileerida.

7
00:00:13,160 --> 00:00:13,993
Sa käivitada programmi.

8
00:00:13,993 --> 00:00:15,370
Sa oled hea minna.

9
00:00:15,370 --> 00:00:17,520
>> Aga uskuge või mitte, kui
te kodeerida kaua,

10
00:00:17,520 --> 00:00:20,550
sa tegelikult võiks tulla, et näha,
kood midagi, mis on ilus.

11
00:00:20,550 --> 00:00:23,275
See lahendab probleemi
väga huvitav viis,

12
00:00:23,275 --> 00:00:26,510
või seal on lihtsalt midagi väga
puhas kohta, kuidas ta välja näeb.

13
00:00:26,510 --> 00:00:28,750
Sa võid olla naeravad
mind, aga see on tõsi.

14
00:00:28,750 --> 00:00:31,530
Ja recursion on üks viis
et omamoodi saada see idee

15
00:00:31,530 --> 00:00:34,090
ilus, elegantne välimusega koodi.

16
00:00:34,090 --> 00:00:37,740
See lahendab probleemid viisil, mis
on huvitav, lihtne visualiseerida,

17
00:00:37,740 --> 00:00:39,810
ja üllatavalt lühike.

18
00:00:39,810 --> 00:00:43,190
>> Tee recursion tööd
on rekursiivse funktsiooni

19
00:00:43,190 --> 00:00:49,291
defineeritakse funktsioon, mis nõuab
ise osa selle täitmist.

20
00:00:49,291 --> 00:00:51,790
See võib tunduda natuke imelik,
ja me näeme natuke

21
00:00:51,790 --> 00:00:53,750
kuidas see töötab hetkel.

22
00:00:53,750 --> 00:00:55,560
Aga jälle need
rekursiivne protseduurid

23
00:00:55,560 --> 00:00:57,730
saab olema nii elegantne
sest nad ei kavatse

24
00:00:57,730 --> 00:01:00,410
Selle probleemi lahendamiseks ilma
kõik need teised funktsioonid

25
00:01:00,410 --> 00:01:02,710
või need pikad silmad.

26
00:01:02,710 --> 00:01:06,310
Sa näed, et need rekursiivne
protseduurid hakkavad otsima nii lühike.

27
00:01:06,310 --> 00:01:10,610
Ja nad tõesti ei kavatse teha
oma koodi vaatama palju ilusam.

28
00:01:10,610 --> 00:01:12,560
>> Ma toon ühe näite
Selle näha, kuidas

29
00:01:12,560 --> 00:01:14,880
rekursiivne korras võib kindlaks määrata.

30
00:01:14,880 --> 00:01:18,202
Nii et kui sa oled tuttav
alates matemaatika klassi aastaid tagasi,

31
00:01:18,202 --> 00:01:20,910
seal on midagi, mida nimetatakse
faktoriaaliga funktsiooni, mis on tavaliselt

32
00:01:20,910 --> 00:01:25,340
tähistatakse hüüumärk, mis
defineeritakse üle kõik positiivsed täisarvud.

33
00:01:25,340 --> 00:01:28,850
Ja nii, et n
faktoriaali arvutamiseks

34
00:01:28,850 --> 00:01:31,050
on sul korrutada kõik
numbrid alla

35
00:01:31,050 --> 00:01:33,750
või võrdne n together--
kõik täisarvud alla

36
00:01:33,750 --> 00:01:34,880
või võrdne n koos.

37
00:01:34,880 --> 00:01:39,850
>> Nii 5 faktoriaal 5 korda
4 korda 3 korda 2 korda 1.

38
00:01:39,850 --> 00:01:43,020
Ja 4 faktoriaal 4 korda
3 korda 2 korda 1 ja nii edasi.

39
00:01:43,020 --> 00:01:44,800
Sa saad idee.

40
00:01:44,800 --> 00:01:47,060
>> Kuna programmeerijad, me ei
kasutada n, hüüumärk.

41
00:01:47,060 --> 00:01:51,840
Nii me määratleda faktoriaali
funktsiooni fakt n.

42
00:01:51,840 --> 00:01:56,897
Ja me kasutame faktoriaali luua
rekursiivne lahendus probleemile.

43
00:01:56,897 --> 00:01:59,230
Ja ma arvan, et te võite leida
et see on palju rohkem visuaalselt

44
00:01:59,230 --> 00:02:02,380
Palve kui iteratiivne
versioon sellest, mida

45
00:02:02,380 --> 00:02:05,010
me ka heita pilk ühe hetkega.

46
00:02:05,010 --> 00:02:08,310
>> Nii et siin on paar
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
umbes factorial--
faktoriaali funktsiooni.

48
00:02:10,169 --> 00:02:13,090
Faktoriaali 1, nagu ma ütlesin, on 1.

49
00:02:13,090 --> 00:02:15,690
Faktoriaali 2 on 2 korda 1.

50
00:02:15,690 --> 00:02:18,470
Faktoriaali 3 on 3
korda 2 korda 1, ja nii edasi.

51
00:02:18,470 --> 00:02:20,810
Rääkisime 4 ja 5 juba.

52
00:02:20,810 --> 00:02:23,940
>> Aga vaadates seda, ei ole see tõsi?

53
00:02:23,940 --> 00:02:28,220
Kas pole faktoriaali 2 lihtsalt
2 korda Faktoriaalse 1?

54
00:02:28,220 --> 00:02:31,130
Ma mõtlen, faktoriaali 1 on 1.

55
00:02:31,130 --> 00:02:34,940
Miks me ei võiks lihtsalt öelda, et
alates faktoriaali 2 on 2 korda 1,

56
00:02:34,940 --> 00:02:38,520
tegelikult on see vaid 2 korda
faktoriaali 1?

57
00:02:38,520 --> 00:02:40,900
>> Ja siis laiendada seda mõtet,
ei ole faktoriaali 3

58
00:02:40,900 --> 00:02:44,080
vaid 3 korda faktoriaali 2?

59
00:02:44,080 --> 00:02:50,350
Ja faktoriaali 4 on 4 korda
faktoriaali 3 ja nii edasi?

60
00:02:50,350 --> 00:02:52,530
Tegelikult Faktoriaalse
mis tahes arvu saab lihtsalt

61
00:02:52,530 --> 00:02:54,660
väljendatakse kas me sellist
ning viia see läbi igavesti.

62
00:02:54,660 --> 00:02:56,870
Me võime liiki üldistada
faktoriaali probleem

63
00:02:56,870 --> 00:02:59,910
kui see on n korda
faktoriaali n miinus 1.

64
00:02:59,910 --> 00:03:04,840
On n korda produktist
kõik numbrid vähem kui mulle.

65
00:03:04,840 --> 00:03:08,890
>> See mõte on see
üldistus probleem,

66
00:03:08,890 --> 00:03:13,410
võimaldab meil rekursiivselt
määratleda faktoriaali funktsiooni.

67
00:03:13,410 --> 00:03:15,440
Kui teil määratleda funktsiooni
rekursiivselt, seal on

68
00:03:15,440 --> 00:03:17,470
kaks asja, mis peavad olema osa sellest.

69
00:03:17,470 --> 00:03:20,990
Sa pead olema midagi, mida nimetatakse
aluspõhimõtted, mis siis, kui vajutad seda,

70
00:03:20,990 --> 00:03:22,480
peatub rekursiivne protsessi.

71
00:03:22,480 --> 00:03:25,300
>> Muidu funktsioon, mis nõuab
itself-- nagu võite imagine--

72
00:03:25,300 --> 00:03:26,870
võiks kesta igavesti.

73
00:03:26,870 --> 00:03:29,047
Funktsioon nõuab funktsiooni
nõuab funktsiooni kõned

74
00:03:29,047 --> 00:03:30,380
funktsioon nõuab funktsiooni.

75
00:03:30,380 --> 00:03:32,380
Kui sul ei ole nii
peatada, oma programmi

76
00:03:32,380 --> 00:03:34,760
saab tõhusalt kinni
kell lõputu silmuse.

77
00:03:34,760 --> 00:03:37,176
See krahhi lõpuks,
sest see saab otsa mälu.

78
00:03:37,176 --> 00:03:38,990
Aga see on kõrval punkti.

79
00:03:38,990 --> 00:03:42,210
>> Meil peab olema muul viisil peatada
asju peale meie programmi krahh,

80
00:03:42,210 --> 00:03:46,010
sest programm, mis jookseb on
Tõenäoliselt ei ilus ega elegantne.

81
00:03:46,010 --> 00:03:47,690
Ja nii me nimetame seda aluspõhimõtted.

82
00:03:47,690 --> 00:03:50,610
See on lihtne lahendus
probleemile, mis peatab

83
00:03:50,610 --> 00:03:52,770
rekursiivne protsessi tekkimist.

84
00:03:52,770 --> 00:03:55,220
Nii et üks osa
rekursiivne funktsioon.

85
00:03:55,220 --> 00:03:56,820
>> Teine osa on rekursiivne puhul.

86
00:03:56,820 --> 00:03:59,195
Ja see on koht, kus recursion
tegelikult toimub.

87
00:03:59,195 --> 00:04:02,200
See on koht, kus
funktsiooni helistab ise.

88
00:04:02,200 --> 00:04:05,940
>> See ei helista ise täpselt
Samamoodi oli kutsutud.

89
00:04:05,940 --> 00:04:08,880
See oleks väike erinevus
mis muudab probleemi see

90
00:04:08,880 --> 00:04:11,497
püüab lahendada Teeny natuke väiksem.

91
00:04:11,497 --> 00:04:14,330
Aga see üldiselt paneb selle
lahendada põhiosa lahendus

92
00:04:14,330 --> 00:04:17,450
teise kõne sätestatakse rida.

93
00:04:17,450 --> 00:04:20,290
>> Milline neist paistab
nagu aluspõhimõtted siin?

94
00:04:20,290 --> 00:04:25,384
Kumb neist näeb välja nagu
Lihtsaim lahendus probleemile?

95
00:04:25,384 --> 00:04:27,550
Meil on hunnik faktoriaalid,
ja me võiks jätkata

96
00:04:27,550 --> 00:04:30,470
läheb nüüd-- 6, 7, 8, 9, 10, ja nii edasi.

97
00:04:30,470 --> 00:04:34,130
>> Aga üks neist näeb välja nagu
heal juhul olla aluspõhimõtted.

98
00:04:34,130 --> 00:04:35,310
See on väga lihtne lahendus.

99
00:04:35,310 --> 00:04:37,810
Me ei pea midagi erilist.

100
00:04:37,810 --> 00:04:40,560
>> Faktoriaali 1 on lihtsalt 1.

101
00:04:40,560 --> 00:04:42,790
Me ei pea tegema muud
korrutamine üldse.

102
00:04:42,790 --> 00:04:45,248
Tundub, kui me läheme
proovida ja seda probleemi lahendada,

103
00:04:45,248 --> 00:04:47,600
ja me peame lõpetama
recursion kuskil,

104
00:04:47,600 --> 00:04:50,610
me ilmselt ei taha enam
see, kui saame 1.

105
00:04:50,610 --> 00:04:54,580
Me ei taha enam enne seda.

106
00:04:54,580 --> 00:04:56,660
>> Nii et kui me määratleda
Meie faktoriaali funktsiooni,

107
00:04:56,660 --> 00:04:58,690
siin on luukere
kuidas me võiksime seda teha.

108
00:04:58,690 --> 00:05:03,110
Meil on vaja ühendada need kaks things--
aluspõhimõtted ja rekursiivne puhul.

109
00:05:03,110 --> 00:05:04,990
Mis aluspõhimõtted?

110
00:05:04,990 --> 00:05:10,150
Kui n on võrdne 1, tagastab 1-- see on
väga lihtne probleem lahendada.

111
00:05:10,150 --> 00:05:11,890
>> Faktoriaali 1 on 1.

112
00:05:11,890 --> 00:05:13,860
See ei ole 1 korda midagi.

113
00:05:13,860 --> 00:05:15,020
See on lihtsalt 1.

114
00:05:15,020 --> 00:05:17,170
See on väga lihtne tõsiasi.

115
00:05:17,170 --> 00:05:19,620
Ja nii, et võib olla meie tugipunkt.

116
00:05:19,620 --> 00:05:24,730
Kui me saada edasi 1 sellesse
funktsiooni, me lihtsalt tagasi 1.

117
00:05:24,730 --> 00:05:27,320
>> Mis on rekursiivne
juhul tõenäoliselt välja nägema?

118
00:05:27,320 --> 00:05:32,445
Sest iga teine ​​number
peale 1, mis on muster?

119
00:05:32,445 --> 00:05:35,780
Noh, kui me võtmist
faktoriaali n,

120
00:05:35,780 --> 00:05:38,160
see on n korda faktoriaali n miinus 1.

121
00:05:38,160 --> 00:05:42,130
>> Kui me võtta faktoriaali 3,
see on 3 korda faktoriaali 3 miinus 1,

122
00:05:42,130 --> 00:05:43,070
või 2.

123
00:05:43,070 --> 00:05:47,330
Ja kui me ei ole
Vaadates 1, vastasel

124
00:05:47,330 --> 00:05:51,710
tagastamise n korda
faktoriaali n miinus 1.

125
00:05:51,710 --> 00:05:53,210
See on üsna lihtne.

126
00:05:53,210 --> 00:05:57,360
>> Ja huvides võttes kergelt
puhtam ja elegantne koodi

127
00:05:57,360 --> 00:06:01,440
tean, et kui meil on ühe-line silmad
või ühekordse joonega tingimisi oksad,

128
00:06:01,440 --> 00:06:04,490
saame vabaneda kõik
looksulg ümber.

129
00:06:04,490 --> 00:06:06,850
Nii saame tugevdada seda sellele.

130
00:06:06,850 --> 00:06:09,640
See on täpselt sama
funktsionaalsus, sest see.

131
00:06:09,640 --> 00:06:13,850
>> Ma lihtsalt tunnen ära lokkis
traksid, sest seal on ainult üks rida

132
00:06:13,850 --> 00:06:18,500
sees neid tingimisi oksad.

133
00:06:18,500 --> 00:06:21,160
Nii et need toimivad sarnaselt.

134
00:06:21,160 --> 00:06:23,800
Kui n on võrdne 1, tagastab 1.

135
00:06:23,800 --> 00:06:28,351
Vastasel tagasi n korda
faktoriaali n miinus 1.

136
00:06:28,351 --> 00:06:29,850
Nii et me teeme probleem väiksem.

137
00:06:29,850 --> 00:06:33,850
Kui n hakkab läbi 5, me ei kavatse
tagasi 5 korda faktoriaali 4.

138
00:06:33,850 --> 00:06:37,100
Ja me näeme mõne hetke, kui me räägime
umbes kõne stack-- teise video

139
00:06:37,100 --> 00:06:39,390
kus me räägime
helistada stack-- õpime

140
00:06:39,390 --> 00:06:41,630
miks just see protsess toimib.

141
00:06:41,630 --> 00:06:46,970
>> Aga samas faktoriaali 5 ütleb
naasta üle 5 korra faktoriaali 4 ja 4

142
00:06:46,970 --> 00:06:49,710
läheb öelda, OK, noh, tagastamise
4 korda faktoriaali 3.

143
00:06:49,710 --> 00:06:51,737
Ja nagu näete, me oleme
omamoodi läheneb 1.

144
00:06:51,737 --> 00:06:53,820
Me lähemale ja
lähemale, et aluspõhimõtted.

145
00:06:53,820 --> 00:06:58,180
>> Ja kui me tabanud base juhul,
kõik eelmise funktsioonid

146
00:06:58,180 --> 00:07:00,540
on vastus nad otsivad.

147
00:07:00,540 --> 00:07:03,900
Factorial 2 ütles vastutasuks
2 korda faktoriaali 1.

148
00:07:03,900 --> 00:07:06,760
Noh, faktoriaali 1 tagastab 1.

149
00:07:06,760 --> 00:07:10,090
Nii et üleskutse faktoriaali
2 võib naasta 2 korda 1,

150
00:07:10,090 --> 00:07:13,980
ja anda see tagasi faktoriaali
3, mis ootab, et tulemus.

151
00:07:13,980 --> 00:07:17,110
>> Ja siis ta saab arvutada
selle tulemusena 3 korda 2 on 6,

152
00:07:17,110 --> 00:07:18,907
ja anda see tagasi faktoriaali 4.

153
00:07:18,907 --> 00:07:20,740
Ja jälle oleme
video pinu

154
00:07:20,740 --> 00:07:23,810
kus see on illustreeritud natuke
rohkem kui see, mida ma räägin praegu.

155
00:07:23,810 --> 00:07:25,300
Aga see on see.

156
00:07:25,300 --> 00:07:29,300
Ainuüksi see on lahendus
arvutamisel faktoriaali number.

157
00:07:29,300 --> 00:07:31,527
>> See on ainult neli rida koodi.

158
00:07:31,527 --> 00:07:32,610
See on päris lahe, eks?

159
00:07:32,610 --> 00:07:35,480
See on selline seksikas.

160
00:07:35,480 --> 00:07:38,580
>> Nii üldiselt, kuid mitte
alati, rekursiivne funktsioon

161
00:07:38,580 --> 00:07:41,190
võib asendada Silmusjuhtme
mitte rekursiivne funktsioon.

162
00:07:41,190 --> 00:07:46,100
Nii et siin kõrvuti, on iteratiivne
versioon Faktoriaalse funktsiooni.

163
00:07:46,100 --> 00:07:49,650
Mõlemad Arvuta
täpselt sama asi.

164
00:07:49,650 --> 00:07:52,170
>> Nad mõlemad arvutada faktoriaali n.

165
00:07:52,170 --> 00:07:54,990
Versioon vasakul
kasutab recursion seda teha.

166
00:07:54,990 --> 00:07:58,320
Versioon paremal
kasutab iteratsiooni seda teha.

167
00:07:58,320 --> 00:08:02,050
>> Ja teate, meil on kuulutada
Muutuva täisarv toodet.

168
00:08:02,050 --> 00:08:02,940
Ja siis me loop.

169
00:08:02,940 --> 00:08:06,790
Nii kaua, kui n on suurem kui 0, me
hoida korrutades selle toote n

170
00:08:06,790 --> 00:08:09,890
ja decrementing n kuni
me arvutada ka.

171
00:08:09,890 --> 00:08:14,600
Nii need kaks ülesannet jällegi
teha täpselt sama asja.

172
00:08:14,600 --> 00:08:19,980
Aga nad ei tee seda
täpselt samamoodi.

173
00:08:19,980 --> 00:08:22,430
>> Nüüd on võimalik
on rohkem kui üht alust

174
00:08:22,430 --> 00:08:25,770
juhtumi või rohkem kui üks
rekursiivne juhul, sõltuvalt

175
00:08:25,770 --> 00:08:27,670
mida teie ülesanne on püüdnud teha.

176
00:08:27,670 --> 00:08:31,650
Sa ei pruugi piirdu ainult
ühe aluse puhul või ühe rekursiivse

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

178
00:08:32,370 --> 00:08:35,320
Nii näiteks midagi
mitu baasi juhtudel

179
00:08:35,320 --> 00:08:37,830
Võib olla see--
Fibonacci jada jada.

180
00:08:37,830 --> 00:08:41,549
>> Nette alates
algkool päeva

181
00:08:41,549 --> 00:08:45,740
et Fibonacci jada määratletud
nagu see-- esimene element on 0.

182
00:08:45,740 --> 00:08:46,890
Teine element on 1.

183
00:08:46,890 --> 00:08:49,230
Mõlemad neist on lihtsalt definitsiooni.

184
00:08:49,230 --> 00:08:55,920
>> Siis iga teine ​​element on määratletud
summana n miinus 1 ja n miinus 2.

185
00:08:55,920 --> 00:09:00,330
Nii kolmas element
oleks 0 pluss 1 on 1.

186
00:09:00,330 --> 00:09:03,280
Ja siis neljas element
Oleks teine ​​element, 1,

187
00:09:03,280 --> 00:09:06,550
pluss kolmas element, 1.

188
00:09:06,550 --> 00:09:08,507
Ja et oleks 2.

189
00:09:08,507 --> 00:09:09,340
Ja nii edasi ja nii edasi.

190
00:09:09,340 --> 00:09:11,680
>> Nii et kui meil on kaks alust juhtudel.

191
00:09:11,680 --> 00:09:14,850
Kui n on võrdne 1, tagastab 0.

192
00:09:14,850 --> 00:09:18,560
Kui n on võrdne 2, tagasi 1.

193
00:09:18,560 --> 00:09:25,930
Vastasel juhul tagastab Fibonacci n
miinus 1 pluss Fibonacci n miinus 2.

194
00:09:25,930 --> 00:09:27,180
>> Nii et mitu baasi juhtudel.

195
00:09:27,180 --> 00:09:29,271
Aga mitu rekursiivne juhtudel?

196
00:09:29,271 --> 00:09:31,520
Noh, seal on midagi
nimetatakse Collatz oletustele.

197
00:09:31,520 --> 00:09:34,630
Ma ei hakka ütlema,
sa tead, mis see on,

198
00:09:34,630 --> 00:09:38,170
sest see on tegelikult meie lõplik
Probleem selle konkreetse video.

199
00:09:38,170 --> 00:09:43,220
Ja see on meie harjutus
töötada koos.

200
00:09:43,220 --> 00:09:46,760
>> Nii et siin on, mida
Collatz oletustele on--

201
00:09:46,760 --> 00:09:48,820
see kehtib iga positiivne täisarv.

202
00:09:48,820 --> 00:09:51,500
Ja see spekuleerib, et see on
alati võimalik tagasi saada

203
00:09:51,500 --> 00:09:55,060
1, kui te järgite neid samme.

204
00:09:55,060 --> 00:09:57,560
Kui n on 1, peatus.

205
00:09:57,560 --> 00:10:00,070
Meil tagasi 1 kui n on 1.

206
00:10:00,070 --> 00:10:05,670
>> Muidu läheb läbi selle
Meetod uuesti n jagatuna 2.

207
00:10:05,670 --> 00:10:08,200
Ja vaata, kas saad tagasi 1.

208
00:10:08,200 --> 00:10:13,260
Vastasel juhul, kui n on paaritu, läbida
Selle protsessi uuesti 3n + 1,

209
00:10:13,260 --> 00:10:15,552
või 3 korda n pluss 1.

210
00:10:15,552 --> 00:10:17,010
Nii et siin on meil ühe aluse puhul.

211
00:10:17,010 --> 00:10:18,430
Kui n on võrdne 1, peatus.

212
00:10:18,430 --> 00:10:20,230
Me ei tee enam recursion.

213
00:10:20,230 --> 00:10:23,730
>> Aga meil on kaks rekursiivne juhtudel.

214
00:10:23,730 --> 00:10:28,750
Kui n on paarisarv, teeme ühe rekursiivse
Juhul, kutsudes n jagatud 2.

215
00:10:28,750 --> 00:10:33,950
Kui n on paaritu, teeme erinev
rekursiivne juhul 3 korda n + 1.

216
00:10:33,950 --> 00:10:39,120
>> Ja nii eesmärk see video on
võtma teise, Video peatamiseks

217
00:10:39,120 --> 00:10:42,440
ja püüa kirjutada seda
rekursiivne funktsioon Collatz

218
00:10:42,440 --> 00:10:47,640
kus te kaotate oma väärtuse n, ja
arvutab, kui palju samme selle

219
00:10:47,640 --> 00:10:52,430
võtab, et saada 1, kui te alustate n
ja te järgite neid samme kuni eespool.

220
00:10:52,430 --> 00:10:56,660
Kui n on 1, kulub 0 samme.

221
00:10:56,660 --> 00:11:00,190
Vastasel juhul läheb
võta üks samm pluss aga

222
00:11:00,190 --> 00:11:06,200
palju samme, mis kulub kas n
jagatuna 2, kui n on paaris või 3n pluss 1

223
00:11:06,200 --> 00:11:08,100
kui n on paaritu.

224
00:11:08,100 --> 00:11:11,190
>> Nüüd ma panin ekraanil siin
paar testi jaoks midagi

225
00:11:11,190 --> 00:11:15,690
paar testid juhtudel sulle, et näha
mida need erinevad Collatz numbrid,

226
00:11:15,690 --> 00:11:17,440
ning samuti illustratsioon
samme, mis

227
00:11:17,440 --> 00:11:20,390
tuleb läbi käinud, nii et saate
omamoodi näha selle protsessi tegevuse.

228
00:11:20,390 --> 00:11:24,222
Seega, kui n on võrdne
1, Collatz n on 0.

229
00:11:24,222 --> 00:11:26,180
Sa ei pea tegema
midagi tagasi saada 1.

230
00:11:26,180 --> 00:11:27,600
Sa oled juba seal.

231
00:11:27,600 --> 00:11:30,550
>> Kui n on 2, kulub
üks samm, et saada 1.

232
00:11:30,550 --> 00:11:31,810
Sa alustad 2.

233
00:11:31,810 --> 00:11:33,100
Well, 2 ei võrdu 1.

234
00:11:33,100 --> 00:11:36,580
Nii et see saab olema üks samm
pluss aga palju samme selle

235
00:11:36,580 --> 00:11:38,015
võtab n jagatuna 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 jagatuna 2 on 1.

238
00:11:42,910 --> 00:11:47,200
Nii kulub ühe sammu pluss aga
palju samme, mis kulub 1.

239
00:11:47,200 --> 00:11:49,720
1 võtab null samme.

240
00:11:49,720 --> 00:11:52,370
>> 3, kui näed, seal on
päris mitmeid etappe.

241
00:11:52,370 --> 00:11:53,590
Lähed 3.

242
00:11:53,590 --> 00:11:56,710
Ja siis lähete
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
See võtab seitse sammu, et saada tagasi 1.

244
00:11:58,804 --> 00:12:01,220
Ja nagu näete, seal on
Paar teiste test juhtudel siin

245
00:12:01,220 --> 00:12:02,470
katsetada oma programmi.

246
00:12:02,470 --> 00:12:03,970
Nii jälle pausi video.

247
00:12:03,970 --> 00:12:09,210
Ja ma lähen tagasi hüpata nüüd
mida tegelik protsess on siin,

248
00:12:09,210 --> 00:12:11,390
mida see hüpotees on.

249
00:12:11,390 --> 00:12:14,140
>> Vaadake, kas saate aru saada
kuidas määratleda Collatz n

250
00:12:14,140 --> 00:12:19,967
nii, et see arvutab mitu
astub ta võtab, et saada 1.

251
00:12:19,967 --> 00:12:23,050
Loodetavasti olete peatatud video
ja sa ei ole lihtsalt ootab mind

252
00:12:23,050 --> 00:12:25,820
teile vastuse siin.

253
00:12:25,820 --> 00:12:29,120
Aga kui sa oled, noh,
siin on vastus nagunii.

254
00:12:29,120 --> 00:12:33,070
>> Nii et siin on võimalik määratlus
on Collatz funktsiooni.

255
00:12:33,070 --> 00:12:35,610
Meie baasi case-- kui n on
võrdub 1, naaseme 0.

256
00:12:35,610 --> 00:12:38,250
See ei võta
samme, et saada tagasi 1.

257
00:12:38,250 --> 00:12:42,710
>> Muidu on meil kaks rekursiivne cases--
üks isegi numbreid ja üks veider.

258
00:12:42,710 --> 00:12:47,164
Kuidas ma test isegi numbrid
on vaadata, kui n mod 2 võrdub 0.

259
00:12:47,164 --> 00:12:49,080
See on põhiliselt jällegi
küsib küsimuse,

260
00:12:49,080 --> 00:12:54,050
Kui te mäletate, milline mod on-- kui ma
lõhe n 2 ei puudu jäänud?

261
00:12:54,050 --> 00:12:55,470
See oleks paarisarv.

262
00:12:55,470 --> 00:13:01,370
>> Ja nii, kui n mod 2 võrdub 0 on
testimine on see paarisarv.

263
00:13:01,370 --> 00:13:04,250
Kui jah, ma tahan tagasi 1
sest see on kindlasti

264
00:13:04,250 --> 00:13:09,270
võttes üks samm pluss Collatz kohta
mis iganes number on pool mind.

265
00:13:09,270 --> 00:13:13,910
Muidu ma tahan tagasi 1
pluss Collatz 3 korda n + 1.

266
00:13:13,910 --> 00:13:16,060
See oli teine
rekursiivne samm, et me

267
00:13:16,060 --> 00:13:19,470
võiks võtta, et arvutada
Collatz-- sammude arv

268
00:13:19,470 --> 00:13:22,610
kulub, et saada tagasi
1 antud number.

269
00:13:22,610 --> 00:13:24,610
Loodetavasti on see näiteks
saatis sulle natuke

270
00:13:24,610 --> 00:13:26,620
ja maitse rekursiivne korra.

271
00:13:26,620 --> 00:13:30,220
Loodetavasti te arvate, kood on
vähe ilusamaks, kui rakendatakse

272
00:13:30,220 --> 00:13:32,760
elegantne, rekursiivne viis.

273
00:13:32,760 --> 00:13:35,955
Aga isegi kui ei ole, recursion on
tõesti võimas vahend sellegipoolest.

274
00:13:35,955 --> 00:13:38,330
Ja nii see on kindlasti midagi
saada oma peas ümber,

275
00:13:38,330 --> 00:13:41,360
sest sa pead olema võimeline looma
päris lahe programme kasutades recursion

276
00:13:41,360 --> 00:13:45,930
mis muidu oleks keeruline kirjutada
kui te kasutate silmad ja korduse.

277
00:13:45,930 --> 00:13:46,980
Ma olen Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
See on CS50.

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