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

2
00:00:05,860 --> 00:00:09,530
>> DOUG Lloyd: Olet luultavasti ajattelevat, että
koodi on vain käytetään tehtävän suorittamiseksi.

3
00:00:09,530 --> 00:00:10,450
Voit kirjoittaa sen ulos.

4
00:00:10,450 --> 00:00:11,664
Se tekee jotain.

5
00:00:11,664 --> 00:00:12,580
Se on aika paljon se.

6
00:00:12,580 --> 00:00:13,160
>> Käännät sitä.

7
00:00:13,160 --> 00:00:13,993
Käynnistät ohjelman.

8
00:00:13,993 --> 00:00:15,370
Olet hyvä mennä.

9
00:00:15,370 --> 00:00:17,520
>> Mutta uskokaa tai älkää, jos
koodataan pitkään,

10
00:00:17,520 --> 00:00:20,550
te todella voi tulla nähdä
koodi jotain, joka on kaunis.

11
00:00:20,550 --> 00:00:23,275
Se ratkaisee ongelman
erittäin mielenkiintoinen tapa,

12
00:00:23,275 --> 00:00:26,510
tai siellä on vain jotain todella
siisti siitä, miten se näyttää.

13
00:00:26,510 --> 00:00:28,750
Saatat nauraa
minua, mutta se on totta.

14
00:00:28,750 --> 00:00:31,530
Ja rekursio on yksi tapa
tavallaan saat tämän idean

15
00:00:31,530 --> 00:00:34,090
kaunis, tyylikäs näköisiä koodi.

16
00:00:34,090 --> 00:00:37,740
Se ratkaisee ongelmia tavoilla,
ovat mielenkiintoisia, helppo visualisoida,

17
00:00:37,740 --> 00:00:39,810
ja yllättävän lyhyt.

18
00:00:39,810 --> 00:00:43,190
>> Tapa rekursio teokset
on, rekursiivinen funktio

19
00:00:43,190 --> 00:00:49,291
määritellään funktio, joka kutsuu
itselleen osana sen täytäntöönpanoa.

20
00:00:49,291 --> 00:00:51,790
Tämä saattaa tuntua hieman oudolta,
ja näemme hieman

21
00:00:51,790 --> 00:00:53,750
siitä, miten tämä toimii hetki.

22
00:00:53,750 --> 00:00:55,560
Mutta jälleen kerran, nämä
rekursiiviset menettelyt ovat

23
00:00:55,560 --> 00:00:57,730
tulee olemaan niin tyylikäs
koska he ovat menossa

24
00:00:57,730 --> 00:01:00,410
tämän ongelman ratkaisemiseksi ilman
joilla on kaikki nämä muut toiminnot

25
00:01:00,410 --> 00:01:02,710
tai nämä pitkät silmukoita.

26
00:01:02,710 --> 00:01:06,310
Näet että nämä rekursiiviset
menettelyt ovat menossa katsomaan niin lyhyt.

27
00:01:06,310 --> 00:01:10,610
Ja he todella aikovat tehdä
koodi näyttää paljon kauniimpi.

28
00:01:10,610 --> 00:01:12,560
>> Annan teille esimerkin
Tämän miten

29
00:01:12,560 --> 00:01:14,880
rekursiivinen menettely voitaisiin määritellä.

30
00:01:14,880 --> 00:01:18,202
Joten jos olet perehtynyt tähän
alkaen matematiikka luokka monta vuotta sitten,

31
00:01:18,202 --> 00:01:20,910
Siinä on jotain kutsutaan
kertoma-toiminto, joka on yleensä

32
00:01:20,910 --> 00:01:25,340
merkitty huutomerkki, joka
määritellään yli kaikki positiiviset kokonaisluvut.

33
00:01:25,340 --> 00:01:28,850
Ja siten, että n
kertoma lasketaan

34
00:01:28,850 --> 00:01:31,050
on kerrot kaikki
numerot vähemmän kuin

35
00:01:31,050 --> 00:01:33,750
tai yhtä suuri kuin n-together--
kaikki kokonaisluvut alle

36
00:01:33,750 --> 00:01:34,880
tai yhtä suuri kuin n yhdessä.

37
00:01:34,880 --> 00:01:39,850
>> Joten 5 kertoma on 5 kertaa
4 kertaa 3 kertaa 2 kertaa 1.

38
00:01:39,850 --> 00:01:43,020
Ja 4 kertoma on 4 kertaa
3 kertaa 2 kertaa 1 ja niin edelleen.

39
00:01:43,020 --> 00:01:44,800
Saat ajatus.

40
00:01:44,800 --> 00:01:47,060
>> Kuten ohjelmoijat, emme
käyttää n, huutomerkki.

41
00:01:47,060 --> 00:01:51,840
Niin me määritellä factorial
toimivat tosiasia n.

42
00:01:51,840 --> 00:01:56,897
Ja käytämme kertoma luoda
rekursiivinen ratkaisu ongelmaan.

43
00:01:56,897 --> 00:01:59,230
Ja luulen, että saatat löytää
että se on paljon enemmän visuaalisesti

44
00:01:59,230 --> 00:02:02,380
houkutteleva kuin iteratiivinen
versio, joka

45
00:02:02,380 --> 00:02:05,010
me myös katsomaan hetkessä.

46
00:02:05,010 --> 00:02:08,310
>> Joten tässä on pari
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
noin factorial--
kertoma toiminto.

48
00:02:10,169 --> 00:02:13,090
Kertoma 1, kuten sanoin, on 1.

49
00:02:13,090 --> 00:02:15,690
Kertoma 2 on 2 kertaa 1.

50
00:02:15,690 --> 00:02:18,470
Kertoma 3 on 3
kertaa 2 kertaa 1, ja niin edelleen.

51
00:02:18,470 --> 00:02:20,810
Puhuimme 4 ja 5 jo.

52
00:02:20,810 --> 00:02:23,940
>> Mutta katsot tätä, ei ole tämä totta?

53
00:02:23,940 --> 00:02:28,220
Eikö kertoma 2 vain
2 kertaa kertoma 1?

54
00:02:28,220 --> 00:02:31,130
Tarkoitan, kertoma 1 on 1.

55
00:02:31,130 --> 00:02:34,940
Joten miksi emme voi vain sanoa, että,
koska kertoma 2 on 2 kertaa 1,

56
00:02:34,940 --> 00:02:38,520
se on oikeastaan ​​vain 2 kertaa
kertoma 1?

57
00:02:38,520 --> 00:02:40,900
>> Ja sitten ulottuu että ajatus,
ei kertoman 3

58
00:02:40,900 --> 00:02:44,080
vain 3 kertaa kertoma 2?

59
00:02:44,080 --> 00:02:50,350
Ja kertoma 4 on 4 kertaa
kertoma 3, ja niin edelleen?

60
00:02:50,350 --> 00:02:52,530
Itse asiassa, kertoma
tahansa numero voi vain

61
00:02:52,530 --> 00:02:54,660
ilmaistaan ​​jos sellainen
on viedä tätä ulos ikuisesti.

62
00:02:54,660 --> 00:02:56,870
Voimme sellaista yleistää
kertoma ongelma

63
00:02:56,870 --> 00:02:59,910
koska se on n kertaa
kertoma n miinus 1.

64
00:02:59,910 --> 00:03:04,840
Se on n kertaa tuote
kaikki numerot vähemmän kuin minä.

65
00:03:04,840 --> 00:03:08,890
>> Tämä ajatus, tämä
yleistys ongelma,

66
00:03:08,890 --> 00:03:13,410
antaa meille mahdollisuuden rekursiivisesti
määritellä kertoma toiminnon.

67
00:03:13,410 --> 00:03:15,440
Kun määrittää funktion
rekursiivisesti, siellä

68
00:03:15,440 --> 00:03:17,470
kaksi asiaa, jotka täytyy olla osa sitä.

69
00:03:17,470 --> 00:03:20,990
Sinun täytyy olla jotain kutsutaan
perustapaus, joka, kun laukaista se,

70
00:03:20,990 --> 00:03:22,480
pysäyttää rekursiivinen prosessi.

71
00:03:22,480 --> 00:03:25,300
>> Muutoin toiminto, joka kutsuu
itself-- kuten ehkä imagine--

72
00:03:25,300 --> 00:03:26,870
voisi jatkua ikuisesti.

73
00:03:26,870 --> 00:03:29,047
Funktiokutsut toiminto
kehottaa funktiokutsut

74
00:03:29,047 --> 00:03:30,380
funktiokutsuja toiminto.

75
00:03:30,380 --> 00:03:32,380
Jos sinulla ei ole tapa
pysäyttää sen, ohjelma

76
00:03:32,380 --> 00:03:34,760
on tehokkaasti jumissa
klo päättymättömään silmukkaan.

77
00:03:34,760 --> 00:03:37,176
Se kaatuu lopulta,
koska se tulee loppuu muisti.

78
00:03:37,176 --> 00:03:38,990
Mutta se sivuseikka.

79
00:03:38,990 --> 00:03:42,210
>> Meillä on oltava jokin muu tapa lopettaa
asioita lisäksi meidän ohjelma kaatuu,

80
00:03:42,210 --> 00:03:46,010
koska ohjelma joka kaatuu on
luultavasti ole kaunis tai tyylikäs.

81
00:03:46,010 --> 00:03:47,690
Ja niin me kutsumme tätä perustapaus.

82
00:03:47,690 --> 00:03:50,610
Tämä on yksinkertainen ratkaisu
ongelmaan, joka lopettaa

83
00:03:50,610 --> 00:03:52,770
rekursiivinen prosessi syntymisen.

84
00:03:52,770 --> 00:03:55,220
Joten se on yksi osa
rekursiivinen funktio.

85
00:03:55,220 --> 00:03:56,820
>> Toinen osa on rekursiivinen tapauksessa.

86
00:03:56,820 --> 00:03:59,195
Ja tämä on silloin rekursio
todella tapahtuu.

87
00:03:59,195 --> 00:04:02,200
Tämä on, jos
toiminto kutsua itseään.

88
00:04:02,200 --> 00:04:05,940
>> Se ei kutsua itseään täsmälleen
samalla tavalla kuin se oli nimeltään.

89
00:04:05,940 --> 00:04:08,880
Se tulee olemaan hieman vaihtelua
joka tekee ongelma on

90
00:04:08,880 --> 00:04:11,497
yrittää ratkaista pikkuinen vähän pienempi.

91
00:04:11,497 --> 00:04:14,330
Mutta se yleensä kulkee pukki
ratkaista suurin liuoksen

92
00:04:14,330 --> 00:04:17,450
eri puhelun ruodussa.

93
00:04:17,450 --> 00:04:20,290
>> Mikä näistä näyttää
kuten pohja tässä tapauksessa?

94
00:04:20,290 --> 00:04:25,384
Kumpi näistä näyttää
Yksinkertaisin ratkaisu ongelmaan?

95
00:04:25,384 --> 00:04:27,550
Meillä on nippu factorials,
ja voisimme jatkaa

96
00:04:27,550 --> 00:04:30,470
menossa on-- 6, 7, 8, 9, 10, ja niin edelleen.

97
00:04:30,470 --> 00:04:34,130
>> Mutta yksi näistä näyttää
hyvä asia olla perustapaus.

98
00:04:34,130 --> 00:04:35,310
Se on hyvin yksinkertainen ratkaisu.

99
00:04:35,310 --> 00:04:37,810
Meidän ei tarvitse tehdä mitään erityistä.

100
00:04:37,810 --> 00:04:40,560
>> Kertoma 1 on vain 1.

101
00:04:40,560 --> 00:04:42,790
Meidän ei tarvitse tehdä mitään
kertominen lainkaan.

102
00:04:42,790 --> 00:04:45,248
Tuntuu siltä, ​​jos aiomme
yrittää ratkaista tämä ongelma,

103
00:04:45,248 --> 00:04:47,600
ja meidän täytyy pysähtyä
rekursio jonnekin,

104
00:04:47,600 --> 00:04:50,610
me luultavasti halua lopettaa
se kun pääsemme 1.

105
00:04:50,610 --> 00:04:54,580
Emme halua lopettaa ennen sitä.

106
00:04:54,580 --> 00:04:56,660
>> Joten jos me määritellään
meidän kertoma toiminto,

107
00:04:56,660 --> 00:04:58,690
tässä on luuranko varten
miten voisimme tehdä.

108
00:04:58,690 --> 00:05:03,110
Meidän on plug näissä kahdessa things--
perusskenaariossa ja rekursiivinen tapaus.

109
00:05:03,110 --> 00:05:04,990
Mikä perustapaus?

110
00:05:04,990 --> 00:05:10,150
Jos n on yhtä kuin 1, palauttaa 1-- se on
todella yksinkertainen ongelma ratkaista.

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

112
00:05:11,890 --> 00:05:13,860
Se ei ole 1 kertaa mitään.

113
00:05:13,860 --> 00:05:15,020
Se on vain 1.

114
00:05:15,020 --> 00:05:17,170
Se on erittäin helppo tosiasia.

115
00:05:17,170 --> 00:05:19,620
Ja jotta voi olla meidän perustapaus.

116
00:05:19,620 --> 00:05:24,730
Jos saamme kulunut 1 tähän
toiminto, me vain palata 1.

117
00:05:24,730 --> 00:05:27,320
>> Mikä rekursiivinen
tapauksessa luultavasti näyttää?

118
00:05:27,320 --> 00:05:32,445
Jokaista muu numero
lisäksi 1, mikä malli?

119
00:05:32,445 --> 00:05:35,780
No, jos viemme
kertoma n,

120
00:05:35,780 --> 00:05:38,160
se on n kertaa kertoma n miinus 1.

121
00:05:38,160 --> 00:05:42,130
>> Jos viemme kertoma 3,
se on 3 kertaa kertoma 3 miinus 1,

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

123
00:05:43,070 --> 00:05:47,330
Joten jos emme ole
katsomalla 1, muuten

124
00:05:47,330 --> 00:05:51,710
palata n kertaa
kertoma n miinus 1.

125
00:05:51,710 --> 00:05:53,210
Se on melko yksinkertainen.

126
00:05:53,210 --> 00:05:57,360
>> Ja vuoksi, joilla on hieman
puhtaampi ja tyylikäs koodi,

127
00:05:57,360 --> 00:06:01,440
tietävät, että jos meillä on yksilinjainen silmukoita
tai yksilinjainen ehdollisen oksat,

128
00:06:01,440 --> 00:06:04,490
voimme päästä eroon kaikista
aaltosulkumerkkien heidän ympärillään.

129
00:06:04,490 --> 00:06:06,850
Joten voimme vahvistaa tätä tähän.

130
00:06:06,850 --> 00:06:09,640
Tämä on täsmälleen sama
toiminnot kuin tämä.

131
00:06:09,640 --> 00:06:13,850
>> Olen vain ottamalla pois kihara
henkselit, koska siellä on vain yksi rivi

132
00:06:13,850 --> 00:06:18,500
sisäpuolella näiden ehdollisen oksat.

133
00:06:18,500 --> 00:06:21,160
Joten nämä käyttäytyvät identtisesti.

134
00:06:21,160 --> 00:06:23,800
Jos n on yhtä kuin 1, palauttaa 1.

135
00:06:23,800 --> 00:06:28,351
Muutoin palaa n kertaa
kertoma n miinus 1.

136
00:06:28,351 --> 00:06:29,850
Joten Teemme ongelma pienempiä.

137
00:06:29,850 --> 00:06:33,850
Jos n alkaa out 5, aiomme
palata 5 kertaa kertoma 4.

138
00:06:33,850 --> 00:06:37,100
Ja näemme hetken kun puhumme
noin puhelun stack-- toisessa video

139
00:06:37,100 --> 00:06:39,390
jossa puhumme
soittaa stack-- me oppia

140
00:06:39,390 --> 00:06:41,630
miksi juuri tämä prosessi toimii.

141
00:06:41,630 --> 00:06:46,970
>> Mutta kun kertoma 5 sanoo
palata 5 kertaa kertoma 4, ja 4

142
00:06:46,970 --> 00:06:49,710
aikoo sanoa, OK, hyvin, paluu
4 kertaa kertoma 3.

143
00:06:49,710 --> 00:06:51,737
Ja kuten näette, olemme
eräänlainen lähestyy 1.

144
00:06:51,737 --> 00:06:53,820
Saamme lähemmäksi ja
lähemmäksi että perustapaus.

145
00:06:53,820 --> 00:06:58,180
>> Ja kun me osuma perustapaus,
kaikki aiemmat toiminnot

146
00:06:58,180 --> 00:07:00,540
on vastaus he etsivät.

147
00:07:00,540 --> 00:07:03,900
Kertoma 2 sanoi paluu
2 kertaa kertoma 1.

148
00:07:03,900 --> 00:07:06,760
No, kertoma 1 palauttaa 1.

149
00:07:06,760 --> 00:07:10,090
Joten vaatimus factorial
2 voi palata 2 kertaa 1,

150
00:07:10,090 --> 00:07:13,980
ja antaa ne takaisin faktoria
3, joka odottaa, että tulos.

151
00:07:13,980 --> 00:07:17,110
>> Ja sitten se voi laskea
sen seurauksena, 3 kertaa 2 on 6,

152
00:07:17,110 --> 00:07:18,907
ja antaa sen takaisin kertoma 4.

153
00:07:18,907 --> 00:07:20,740
Ja vielä, meillä on
video kutsupino

154
00:07:20,740 --> 00:07:23,810
jos tämä on kuvattu hieman
enemmän kuin mitä minä sanon nyt.

155
00:07:23,810 --> 00:07:25,300
Mutta tämä on se.

156
00:07:25,300 --> 00:07:29,300
Tämä yksin on ratkaisu
laskettaessa kertoman numeron.

157
00:07:29,300 --> 00:07:31,527
>> Se on vain neljä riviä koodia.

158
00:07:31,527 --> 00:07:32,610
Se on aika siistiä, eikö?

159
00:07:32,610 --> 00:07:35,480
Se on tavallaan seksikäs.

160
00:07:35,480 --> 00:07:38,580
>> Niin yleensä, mutta ei
aina, rekursiivinen funktio

161
00:07:38,580 --> 00:07:41,190
voi korvata silmukan
ei-rekursiivinen funktio.

162
00:07:41,190 --> 00:07:46,100
Joten tässä, vierekkäin, on iteratiivinen
versio kertoma toiminnon.

163
00:07:46,100 --> 00:07:49,650
Nämä molemmat laske
täsmälleen sama asia.

164
00:07:49,650 --> 00:07:52,170
>> Molemmat laskea kertoma n.

165
00:07:52,170 --> 00:07:54,990
Versio vasemmalla
käyttää rekursio tehdä se.

166
00:07:54,990 --> 00:07:58,320
Versio oikealla
käyttää iteraation tehdä se.

167
00:07:58,320 --> 00:08:02,050
>> Ja ilmoitus, meidän täytyy julistaa
muuttujan kokonaisluku tuotetta.

168
00:08:02,050 --> 00:08:02,940
Ja sitten me silmukka.

169
00:08:02,940 --> 00:08:06,790
Niin kauan kuin n on suurempi kuin 0, me
pitää kertomalla että tuotteen n

170
00:08:06,790 --> 00:08:09,890
ja pienentämällä n saakka
laskemme tuotetta.

171
00:08:09,890 --> 00:08:14,600
Joten nämä kaksi tehtävää, jälleen,
tehdä täsmälleen sama asia.

172
00:08:14,600 --> 00:08:19,980
Mutta he eivät tee sitä
täsmälleen samalla tavalla.

173
00:08:19,980 --> 00:08:22,430
>> Nyt, on mahdollista
on enemmän kuin yksi emäs

174
00:08:22,430 --> 00:08:25,770
tapauksessa tai useamman kuin yhden
rekursiivinen tapauksessa riippuen

175
00:08:25,770 --> 00:08:27,670
siitä, mitä toiminto yrittää tehdä.

176
00:08:27,670 --> 00:08:31,650
Et ole välttämättä rajoitu vain
yhden emäksen tapaus tai yhden rekursiivinen

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

178
00:08:32,370 --> 00:08:35,320
Joten esimerkki jotain
useita pohja tapauksia

179
00:08:35,320 --> 00:08:37,830
voisi olla this--
Fibonaccin numerosarja.

180
00:08:37,830 --> 00:08:41,549
>> Voit muistamme
peruskoulun päivää

181
00:08:41,549 --> 00:08:45,740
että Fibonaccin määritellään
kuten this-- ensimmäinen elementti on 0.

182
00:08:45,740 --> 00:08:46,890
Toinen elementti on 1.

183
00:08:46,890 --> 00:08:49,230
Molemmat näistä ovat vain määritelmän.

184
00:08:49,230 --> 00:08:55,920
>> Sitten joka toinen elementti on määritelty
summana n miinus 1 ja n miinus 2.

185
00:08:55,920 --> 00:09:00,330
Joten kolmas elementti
olisi 0 plus 1 on 1.

186
00:09:00,330 --> 00:09:03,280
Ja sitten neljäs elementti
olisi toinen elementti, 1,

187
00:09:03,280 --> 00:09:06,550
plus kolmas elementti, 1.

188
00:09:06,550 --> 00:09:08,507
Ja että olisi 2.

189
00:09:08,507 --> 00:09:09,340
Ja niin edelleen ja niin edelleen.

190
00:09:09,340 --> 00:09:11,680
>> Joten tässä tapauksessa, meillä on kaksi pohja tapausta.

191
00:09:11,680 --> 00:09:14,850
Jos n on yhtä kuin 1, palauttaa 0.

192
00:09:14,850 --> 00:09:18,560
Jos n on 2, paluu 1.

193
00:09:18,560 --> 00:09:25,930
Muuten palauttaa Fibonaccin n
miinus 1 plus Fibonaccin n miinus 2.

194
00:09:25,930 --> 00:09:27,180
>> Niin, että useita pohja tapauksissa.

195
00:09:27,180 --> 00:09:29,271
Entä useita rekursiivinen tapauksissa?

196
00:09:29,271 --> 00:09:31,520
No, siinä on jotain
nimeltään Collatz Conjecture.

197
00:09:31,520 --> 00:09:34,630
En aio sanoa,
tiedät mitä se on,

198
00:09:34,630 --> 00:09:38,170
koska se on todella meidän lopullinen
ongelma tässä video.

199
00:09:38,170 --> 00:09:43,220
Ja se on meidän liikunta
työskennellä yhdessä.

200
00:09:43,220 --> 00:09:46,760
>> Joten tässä mitä
Collatz Conjecture is--

201
00:09:46,760 --> 00:09:48,820
se koskee kaikkia positiivinen kokonaisluku.

202
00:09:48,820 --> 00:09:51,500
Ja se spekuloi, että se on
aina mahdollista saada takaisin

203
00:09:51,500 --> 00:09:55,060
1, jos teet nämä toimet.

204
00:09:55,060 --> 00:09:57,560
Jos n on 1, lopeta.

205
00:09:57,560 --> 00:10:00,070
Meillä takaisin 1, jos n on 1.

206
00:10:00,070 --> 00:10:05,670
>> Muuten, läpi tämän
prosessin uudelleen n jaettuna 2.

207
00:10:05,670 --> 00:10:08,200
Ja katso jos voit saada takaisin 1.

208
00:10:08,200 --> 00:10:13,260
Muuten, jos n on pariton, läpi
Tämän prosessin uudelleen 3n + 1,

209
00:10:13,260 --> 00:10:15,552
tai 3 kertaa N + 1.

210
00:10:15,552 --> 00:10:17,010
Joten tässä meillä on yhden emäksen tapaus.

211
00:10:17,010 --> 00:10:18,430
Jos n on yhtä kuin 1, lopettaa.

212
00:10:18,430 --> 00:10:20,230
Emme tee enää rekursio.

213
00:10:20,230 --> 00:10:23,730
>> Mutta meillä on kaksi rekursiivista tapausta.

214
00:10:23,730 --> 00:10:28,750
Jos n on parillinen, teemme yhden rekursiivinen
tapauksessa kutsuen n jaettuna 2.

215
00:10:28,750 --> 00:10:33,950
Jos n on pariton, teemme eri
rekursiivinen tapauksessa 3 kertaa n ja 1.

216
00:10:33,950 --> 00:10:39,120
>> Ja niin tavoite tämä video on
ottaa toisen, keskeyttää videon,

217
00:10:39,120 --> 00:10:42,440
ja yrittää kirjoittaa tätä
rekursiivinen funktio Collatz

218
00:10:42,440 --> 00:10:47,640
jossa voit kulkea arvo n, ja
se laskee, kuinka monta askelta se

219
00:10:47,640 --> 00:10:52,430
tekee päästä 1, jos aloitat n
ja noudatat niitä vaiheita yläpuolelle.

220
00:10:52,430 --> 00:10:56,660
Jos n on 1, se vie 0 vaiheita.

221
00:10:56,660 --> 00:11:00,190
Muuten, se tulee
ottaa yksi askel plus kuitenkin

222
00:11:00,190 --> 00:11:06,200
monta askelta kuluu joko n
jaettuna 2, jos n on parillinen tai 3n + 1

223
00:11:06,200 --> 00:11:08,100
jos n on pariton.

224
00:11:08,100 --> 00:11:11,190
>> Nyt, olen laittaa ruudulle täällä
pari testi asioita sinulle,

225
00:11:11,190 --> 00:11:15,690
pari testejä tapauksissa sinulle, nähdä
mitä nämä eri Collatz numerot ovat,

226
00:11:15,690 --> 00:11:17,440
ja myös kuva
vaiheet, jotka

227
00:11:17,440 --> 00:11:20,390
on mennyt läpi niin voit
tavallaan nähdä tämän prosessin toiminnassa.

228
00:11:20,390 --> 00:11:24,222
Joten jos n on yhtä suuri kuin
1, Collatz n on 0.

229
00:11:24,222 --> 00:11:26,180
Sinun ei tarvitse tehdä
tahansa saadakseen takaisin 1.

230
00:11:26,180 --> 00:11:27,600
Olet jo siellä.

231
00:11:27,600 --> 00:11:30,550
>> Jos n on 2, se kestää
yksi askel päästä 1.

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

233
00:11:31,810 --> 00:11:33,100
Hyvin, 2 ei ole yhtä kuin 1.

234
00:11:33,100 --> 00:11:36,580
Joten se tulee olemaan yksi askel
plus kuitenkin monta askelta se

235
00:11:36,580 --> 00:11:38,015
ottaa n jaettuna 2.

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

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

238
00:11:42,910 --> 00:11:47,200
Joten se vie yhden askeleen plus kuitenkin
monta askelta kuluu 1.

239
00:11:47,200 --> 00:11:49,720
1 ottaa nolla vaiheet.

240
00:11:49,720 --> 00:11:52,370
>> 3, kuten näette, siellä
aivan muutaman askeleen mukana.

241
00:11:52,370 --> 00:11:53,590
Menet 3.

242
00:11:53,590 --> 00:11:56,710
Ja sitten menet
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Se kestää seitsemän askelta päästä takaisin 1.

244
00:11:58,804 --> 00:12:01,220
Ja kuten näette, siellä
Pari muuta testitapaukset täällä

245
00:12:01,220 --> 00:12:02,470
testata ohjelman.

246
00:12:02,470 --> 00:12:03,970
Joten jälleen, keskeyttää videon.

247
00:12:03,970 --> 00:12:09,210
Ja Menen hypätä takaisin nyt
mitä todellinen prosessi on täällä,

248
00:12:09,210 --> 00:12:11,390
mitä tämä arveluja on.

249
00:12:11,390 --> 00:12:14,140
>> Katso jos voit selvittää
miten määritellä Collatz n

250
00:12:14,140 --> 00:12:19,967
niin, että se laskee, kuinka monta
toimiin se tekee päästä 1.

251
00:12:19,967 --> 00:12:23,050
Joten toivottavasti olet keskeytetty video
ja et ole vain odottavat minua

252
00:12:23,050 --> 00:12:25,820
antaa sinulle vastauksen täällä.

253
00:12:25,820 --> 00:12:29,120
Mutta jos olet, hyvin,
tässä on vastaus muutenkin.

254
00:12:29,120 --> 00:12:33,070
>> Joten tässä on mahdollinen määritelmä
ja Collatz funktion.

255
00:12:33,070 --> 00:12:35,610
Meidän perustaa case-- jos n on
on 1, palaamme 0.

256
00:12:35,610 --> 00:12:38,250
Se ei ota mitään
askeleen päästä takaisin 1.

257
00:12:38,250 --> 00:12:42,710
>> Muuten, meillä on kaksi rekursiivista cases--
yksi parilliset numerot ja yksi outoa.

258
00:12:42,710 --> 00:12:47,164
Tapa I -testissä parillisia
on tarkistaa, jos n mod 2 tuloksena 0.

259
00:12:47,164 --> 00:12:49,080
Tämä on periaatteessa, jälleen,
kysyvät,

260
00:12:49,080 --> 00:12:54,050
Jos muistatte, mitä mod is-- jos en
jakaa n 2 on olemassa mitään jäljellä?

261
00:12:54,050 --> 00:12:55,470
Se olisi parillinen määrä.

262
00:12:55,470 --> 00:13:01,370
>> Ja niin jos n mod 2 tuloksena 0 on
testaus on tämä parillinen.

263
00:13:01,370 --> 00:13:04,250
Jos näin on, haluan palata 1,
koska tämä on ehdottomasti

264
00:13:04,250 --> 00:13:09,270
ottamalla yksi askel plus Collatz of
mikä määrä on puoli minusta.

265
00:13:09,270 --> 00:13:13,910
Muuten, haluan palata 1
plus Collatz 3 kertaa n ja 1.

266
00:13:13,910 --> 00:13:16,060
Joka oli toinen
rekursiivinen askel, että me

267
00:13:16,060 --> 00:13:19,470
voisi laskea
Collatz-- useita vaiheita

268
00:13:19,470 --> 00:13:22,610
se tekee päästä takaisin
1 annetaan numero.

269
00:13:22,610 --> 00:13:24,610
Joten toivottavasti tämä esimerkki
antoi sinulle hieman

270
00:13:24,610 --> 00:13:26,620
of maku rekursiivinen menettelyjä.

271
00:13:26,620 --> 00:13:30,220
Toivottavasti luulet koodi on
hieman kaunis toteutuessaan

272
00:13:30,220 --> 00:13:32,760
tyylikäs, rekursiivinen tavalla.

273
00:13:32,760 --> 00:13:35,955
Mutta vaikka ei, rekursiota on
todella tehokas työkalu kuitenkin.

274
00:13:35,955 --> 00:13:38,330
Ja niin se on varmasti jotain
saada pään ympäri,

275
00:13:38,330 --> 00:13:41,360
koska voit luoda
melko viileä ohjelmia recursion

276
00:13:41,360 --> 00:13:45,930
jotka muuten saattaisivat olla monimutkainen kirjoittaa
jos käytät silmukoita ja iterointia.

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

278
00:13:46,980 --> 00:13:48,780
Tämä on CS50.

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