1
00:00:00,000 --> 00:00:05,860
>> [Přehrávání hudby]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Pravděpodobně si myslí, že
kód slouží jen ke splnění úkolu.

3
00:00:09,530 --> 00:00:10,450
Píšete si to.

4
00:00:10,450 --> 00:00:11,664
Je to něco dělá.

5
00:00:11,664 --> 00:00:12,580
To je docela hodně to.

6
00:00:12,580 --> 00:00:13,160
>> Ty zkompilovat.

7
00:00:13,160 --> 00:00:13,993
Spusťte program.

8
00:00:13,993 --> 00:00:15,370
Jsi dobré jít.

9
00:00:15,370 --> 00:00:17,520
>> Ale věřte tomu nebo ne, je-li
si kód na dlouhou dobu,

10
00:00:17,520 --> 00:00:20,550
jste vlastně může přijít vidět
kód jako něco, co je krásné.

11
00:00:20,550 --> 00:00:23,275
To řeší problém v
Velmi zajímavý způsob,

12
00:00:23,275 --> 00:00:26,510
nebo tam je prostě něco, co opravdu
čistý o tom, jak to vypadá.

13
00:00:26,510 --> 00:00:28,750
Ty by mohly být smát
se na mě, ale je to pravda.

14
00:00:28,750 --> 00:00:31,530
A rekurze je jedním ze způsobů,
se nějak dostat tuto myšlenku

15
00:00:31,530 --> 00:00:34,090
krásné, elegantní vypadající kód.

16
00:00:34,090 --> 00:00:37,740
To řeší problémy, způsoby, které
jsou zajímavé, snadno představit,

17
00:00:37,740 --> 00:00:39,810
a překvapivě krátké.

18
00:00:39,810 --> 00:00:43,190
>> Způsob, jakým funguje rekurze
je, rekurzivní funkce

19
00:00:43,190 --> 00:00:49,291
je definován jako funkce, která volá
sám jako součást jeho provedení.

20
00:00:49,291 --> 00:00:51,790
To se může zdát trochu divné,
a uvidíme trochu

21
00:00:51,790 --> 00:00:53,750
o tom, jak to funguje v okamžiku.

22
00:00:53,750 --> 00:00:55,560
Ale opět, tyto
rekurzivní postupy jsou

23
00:00:55,560 --> 00:00:57,730
Bude tak elegantní
protože jdou

24
00:00:57,730 --> 00:01:00,410
k řešení tohoto problému, aniž by
které mají všechny tyto ostatní funkce

25
00:01:00,410 --> 00:01:02,710
nebo tyto dlouhé smyčky.

26
00:01:02,710 --> 00:01:06,310
Uvidíte, že tyto rekurzivní
postupy jsou bude vypadat tak krátký.

27
00:01:06,310 --> 00:01:10,610
A opravdu se chystáte dělat
váš kód vypadat mnohem krásnější.

28
00:01:10,610 --> 00:01:12,560
>> Dám vám příklad
z toho vidět, jak

29
00:01:12,560 --> 00:01:14,880
rekurzivní postup by mohl být definován.

30
00:01:14,880 --> 00:01:18,202
Takže pokud jste obeznámeni s tím
od třídě math před mnoha lety,

31
00:01:18,202 --> 00:01:20,910
Je tu něco, co nazývá
Funkce faktoriál, který je obvykle

32
00:01:20,910 --> 00:01:25,340
označený jako vykřičník, který
je definován přes všechny pozitivní celá čísla.

33
00:01:25,340 --> 00:01:28,850
A tak, že n
faktoriál se vypočítá

34
00:01:28,850 --> 00:01:31,050
je násobit všechny
čísla menší než

35
00:01:31,050 --> 00:01:33,750
nebo se rovná n together--
všechna celá čísla menší než

36
00:01:33,750 --> 00:01:34,880
nebo rovna n dohromady.

37
00:01:34,880 --> 00:01:39,850
>> Takže 5 faktoriál je 5 krát
4 krát 3 krát 2 krát 1.

38
00:01:39,850 --> 00:01:43,020
A 4 faktoriál je 4 krát
3 krát 2 krát 1 a tak dále.

39
00:01:43,020 --> 00:01:44,800
Dostanete nápad.

40
00:01:44,800 --> 00:01:47,060
>> Jako programátoři, my ne
použijte N vykřičník.

41
00:01:47,060 --> 00:01:51,840
Takže budeme definovat faktoriál
Funkce jako fakt n.

42
00:01:51,840 --> 00:01:56,897
A budeme používat faktoriál k vytvoření
rekurzivní řešení problému.

43
00:01:56,897 --> 00:01:59,230
A myslím, že byste mohli najít
že je to mnohem víc vizuálně

44
00:01:59,230 --> 00:02:02,380
přitažlivý než iterativní
verze tohoto, což

45
00:02:02,380 --> 00:02:05,010
budeme také se podívat na za chvíli.

46
00:02:05,010 --> 00:02:08,310
>> Tak tady je pár
facts-- hříčka intended--

47
00:02:08,310 --> 00:02:10,169
o factorial--
faktoriál funkce.

48
00:02:10,169 --> 00:02:13,090
Faktoriál 1, jak jsem řekl, je 1.

49
00:02:13,090 --> 00:02:15,690
Faktoriál 2 je 2 krát 1.

50
00:02:15,690 --> 00:02:18,470
Faktoriál 3 je 3
krát 2 krát 1, a tak dále.

51
00:02:18,470 --> 00:02:20,810
Mluvili jsme o 4 a 5 již.

52
00:02:20,810 --> 00:02:23,940
>> Ale při pohledu na to, není to pravda?

53
00:02:23,940 --> 00:02:28,220
Není faktoriál 2 jen
2 krát faktoriál 1?

54
00:02:28,220 --> 00:02:31,130
Myslím, že faktoriál 1 je 1.

55
00:02:31,130 --> 00:02:34,940
Tak proč prostě nemůžeme říct, že,
protože faktoriál 2 je 2 krát 1,

56
00:02:34,940 --> 00:02:38,520
je to opravdu jen 2 krát
faktoriál 1?

57
00:02:38,520 --> 00:02:40,900
>> A pak rozšířila tuto myšlenku,
není faktoriál 3

58
00:02:40,900 --> 00:02:44,080
jen 3 krát faktoriál 2?

59
00:02:44,080 --> 00:02:50,350
A faktoriál 4 je 4 krát
faktoriál 3, a tak dále?

60
00:02:50,350 --> 00:02:52,530
Ve skutečnosti, faktoriální
jakékoliv množství může jen

61
00:02:52,530 --> 00:02:54,660
se vyjádří, pokud jsme trochu
o provádění tohoto navždy.

62
00:02:54,660 --> 00:02:56,870
Můžeme trochu zobecnit
faktoriál problém

63
00:02:56,870 --> 00:02:59,910
jak je to časy n
faktoriál n minus 1.

64
00:02:59,910 --> 00:03:04,840
Je to n krát produkt
všechna čísla menší než já.

65
00:03:04,840 --> 00:03:08,890
>> Tato myšlenka, to
zobecnění problému,

66
00:03:08,890 --> 00:03:13,410
nám umožňuje rekurzivně
definovat faktoriálu funkce.

67
00:03:13,410 --> 00:03:15,440
Při definování funkce
rekurzivně, je tu

68
00:03:15,440 --> 00:03:17,470
dvě věci, které musí být součástí toho všeho.

69
00:03:17,470 --> 00:03:20,990
Musíte mít něco, co nazývá
referenční případ, který, když jej spustit,

70
00:03:20,990 --> 00:03:22,480
zastaví rekurzivní proces.

71
00:03:22,480 --> 00:03:25,300
>> V opačném případě funkce, která volá
itself-- jak by se mohlo imagine--

72
00:03:25,300 --> 00:03:26,870
by mohl pokračovat donekonečna.

73
00:03:26,870 --> 00:03:29,047
Funkce volá funkci
volání funkce volání

74
00:03:29,047 --> 00:03:30,380
Funkce volá funkci.

75
00:03:30,380 --> 00:03:32,380
Pokud nemáte cestu
jej zastavit, program

76
00:03:32,380 --> 00:03:34,760
bude účinně přilepená
v nekonečné smyčce.

77
00:03:34,760 --> 00:03:37,176
To se zhroutí nakonec,
protože to bude spustit z paměti.

78
00:03:37,176 --> 00:03:38,990
Ale to je vedlejší.

79
00:03:38,990 --> 00:03:42,210
>> Potřebujeme mít nějaký jiný způsob, jak zastavit
věci, kromě našeho programu shazovat,

80
00:03:42,210 --> 00:03:46,010
protože program, který havaruje je
Pravděpodobně ne krásná a elegantní.

81
00:03:46,010 --> 00:03:47,690
A tak říkáme to referenční případ.

82
00:03:47,690 --> 00:03:50,610
Jedná se o jednoduché řešení
na problém, který zastavuje

83
00:03:50,610 --> 00:03:52,770
proces rekurzivního výskytu.

84
00:03:52,770 --> 00:03:55,220
Takže to je jedna část
rekurzivní funkce.

85
00:03:55,220 --> 00:03:56,820
>> Druhá část je rekurzivní případ.

86
00:03:56,820 --> 00:03:59,195
A to je místo, kde rekurze
bude skutečně konat.

87
00:03:59,195 --> 00:04:02,200
To je místo, kde
Funkce zavolá sama.

88
00:04:02,200 --> 00:04:05,940
>> Nebude volat sebe v přesně
stejně tak, jak to bylo voláno.

89
00:04:05,940 --> 00:04:08,880
Bude to nepatrná změna
která dělá problém je to

90
00:04:08,880 --> 00:04:11,497
snaží vyřešit malinký něco menší.

91
00:04:11,497 --> 00:04:14,330
Ale obecně prochází babku
vyřešit převážnou část roztoku

92
00:04:14,330 --> 00:04:17,450
na jinou výzvu v řadě.

93
00:04:17,450 --> 00:04:20,290
>> Který z těchto pohledů
jako základní věci tady?

94
00:04:20,290 --> 00:04:25,384
Který z těchto vypadá
Nejjednodušším řešením problému?

95
00:04:25,384 --> 00:04:27,550
Máme spoustu faktoriály,
a tak bychom mohli pokračovat

96
00:04:27,550 --> 00:04:30,470
se on-- 6, 7, 8, 9, 10, a tak dále.

97
00:04:30,470 --> 00:04:34,130
>> Ale jeden z nich vypadá jako
dobrým příkladem, že je referenční případ.

98
00:04:34,130 --> 00:04:35,310
Je to velmi jednoduché řešení.

99
00:04:35,310 --> 00:04:37,810
Nemusíme dělat nic zvláštního.

100
00:04:37,810 --> 00:04:40,560
>> Faktoriál 1 je jen 1.

101
00:04:40,560 --> 00:04:42,790
Nemusíme dělat jakýkoli
násobení vůbec.

102
00:04:42,790 --> 00:04:45,248
Vypadá to, že v případě, že budeme
aby se pokusila vyřešit tento problém,

103
00:04:45,248 --> 00:04:47,600
a musíme zastavit
rekurzi někde,

104
00:04:47,600 --> 00:04:50,610
Pravděpodobně chceme zastavit
za to, když se dostaneme do 1.

105
00:04:50,610 --> 00:04:54,580
Nechceme zastavit před tím.

106
00:04:54,580 --> 00:04:56,660
>> Takže pokud budeme definovat
náš faktoriál funkce,

107
00:04:56,660 --> 00:04:58,690
tady je kostra pro
jak bychom mohli udělat.

108
00:04:58,690 --> 00:05:03,110
Musíme zapojit v těchto dvou things--
referenční případ, a rekurzivní případ.

109
00:05:03,110 --> 00:05:04,990
Co je to referenční případ?

110
00:05:04,990 --> 00:05:10,150
Je-li n rovno 1, vrátit 1-- to je
opravdu jednoduchý problém k řešení.

111
00:05:10,150 --> 00:05:11,890
>> Faktoriál 1 je 1.

112
00:05:11,890 --> 00:05:13,860
Nejsou to 1 krát cokoliv.

113
00:05:13,860 --> 00:05:15,020
Je to jen 1.

114
00:05:15,020 --> 00:05:17,170
Je to velmi jednoduchý fakt.

115
00:05:17,170 --> 00:05:19,620
A tak to může být naše základna případ.

116
00:05:19,620 --> 00:05:24,730
Pokud bychom si prošel 1 do tohoto
funkce, prostě budeme vracet 1.

117
00:05:24,730 --> 00:05:27,320
>> Co je rekurzivní
Případ pravděpodobně vypadat?

118
00:05:27,320 --> 00:05:32,445
Pro každý jiné číslo
kromě 1, co je vzor?

119
00:05:32,445 --> 00:05:35,780
No, pokud bereme
faktoriál n,

120
00:05:35,780 --> 00:05:38,160
Je to doba n faktoriál n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Pokud vezmeme faktoriál 3,
je to 3 krát faktoriál 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
A tak, když nejsme
při pohledu na 1, jinak

124
00:05:47,330 --> 00:05:51,710
return n násobek
faktoriál n minus 1.

125
00:05:51,710 --> 00:05:53,210
Je to docela jednoduché.

126
00:05:53,210 --> 00:05:57,360
>> A v zájmu mít mírně
čistší a elegantnější kód,

127
00:05:57,360 --> 00:06:01,440
vědí, že pokud máme jednořádkové smyčky
nebo jednořádkový podmíněné větve,

128
00:06:01,440 --> 00:06:04,490
se můžeme zbavit všechny
složené závorky kolem nich.

129
00:06:04,490 --> 00:06:06,850
Takže můžeme upevnit to k tomu.

130
00:06:06,850 --> 00:06:09,640
To má přesně stejné
funkce je tento.

131
00:06:09,640 --> 00:06:13,850
>> Já jsem jen odnášet kudrnaté
šle, protože tam je jen jeden řádek

132
00:06:13,850 --> 00:06:18,500
uvnitř těchto podmíněných větví.

133
00:06:18,500 --> 00:06:21,160
Tak to se chovají stejně.

134
00:06:21,160 --> 00:06:23,800
Je-li n rovno 1, 1 vrátit.

135
00:06:23,800 --> 00:06:28,351
V opačném případě vrací n-krát
faktoriál n minus 1.

136
00:06:28,351 --> 00:06:29,850
Takže děláme problém menší.

137
00:06:29,850 --> 00:06:33,850
Pokud n začíná jako 5, jdeme
vrátit 5 krát faktoriál 4.

138
00:06:33,850 --> 00:06:37,100
A uvidíme za chvíli, když mluvíme
o volání stack-- v jiném videu

139
00:06:37,100 --> 00:06:39,390
kde mluvíme o
zavolejte stack-- dozvíme

140
00:06:39,390 --> 00:06:41,630
o tom, proč právě tento proces funguje.

141
00:06:41,630 --> 00:06:46,970
>> Ale zatímco faktoriál 5 říká:
vrátit 5 krát faktoriál 4, a 4

142
00:06:46,970 --> 00:06:49,710
se chystá říct, OK, dobře, návrat
4 krát faktoriál 3.

143
00:06:49,710 --> 00:06:51,737
A jak můžete vidět, že jsme
druh blíží 1.

144
00:06:51,737 --> 00:06:53,820
Jsme stále blíž a
blíže k tomuto základnímu případu.

145
00:06:53,820 --> 00:06:58,180
>> A jakmile jsme narazili základní věci,
všechny předchozí funkce

146
00:06:58,180 --> 00:07:00,540
znát odpověď, které hledali.

147
00:07:00,540 --> 00:07:03,900
Faktoriál 2 říkal návrat
2 krát faktoriál 1.

148
00:07:03,900 --> 00:07:06,760
No, faktoriál 1 vrátí 1.

149
00:07:06,760 --> 00:07:10,090
Takže výzva k faktoriálu
2 může vrátit 2 krát 1,

150
00:07:10,090 --> 00:07:13,980
a dát to zpátky do faktoriálem
3, který čeká na tento výsledek.

151
00:07:13,980 --> 00:07:17,110
>> A pak to může vypočítat
Její výsledek, 3x 2 je 6,

152
00:07:17,110 --> 00:07:18,907
a vrátí jej faktoriálem 4.

153
00:07:18,907 --> 00:07:20,740
A zase, máme
video na zásobníku volání

154
00:07:20,740 --> 00:07:23,810
kde je to znázorněno poněkud
víc než to, co říkám teď.

155
00:07:23,810 --> 00:07:25,300
Ale to je to.

156
00:07:25,300 --> 00:07:29,300
To samo o sobě je řešením
výpočet faktoriál čísla.

157
00:07:29,300 --> 00:07:31,527
>> Je to jen čtyři řádky kódu.

158
00:07:31,527 --> 00:07:32,610
To je docela v pohodě, ne?

159
00:07:32,610 --> 00:07:35,480
Je to trochu sexy.

160
00:07:35,480 --> 00:07:38,580
>> Takže obecně, ale nikoli
vždy, rekurzivní funkce

161
00:07:38,580 --> 00:07:41,190
může nahradit smyčkou v
non-rekurzivní funkce.

162
00:07:41,190 --> 00:07:46,100
Tak tady, vedle sebe, je iterativní
verze faktoriálové funkce.

163
00:07:46,100 --> 00:07:49,650
Obě tyto vypočítat
přesně totéž.

164
00:07:49,650 --> 00:07:52,170
>> Oba vypočítat faktoriál n.

165
00:07:52,170 --> 00:07:54,990
Verze na levé straně
používá rekurzi, jak to udělat.

166
00:07:54,990 --> 00:07:58,320
Verze na pravé straně
využívá opakování, jak to udělat.

167
00:07:58,320 --> 00:08:02,050
>> A upozornění, musíme prohlásit,
proměnná celé číslo produktu.

168
00:08:02,050 --> 00:08:02,940
A pak jsme smyčka.

169
00:08:02,940 --> 00:08:06,790
Tak dlouho, jak n je větší než 0, jsme
udržovat vynásobením tohoto výrobku N

170
00:08:06,790 --> 00:08:09,890
a dekrementování n, dokud
spočítáme produktu.

171
00:08:09,890 --> 00:08:14,600
Takže tyto dvě funkce, opět,
dělat přesně totéž.

172
00:08:14,600 --> 00:08:19,980
Ale nedělají to v
přesně stejným způsobem.

173
00:08:19,980 --> 00:08:22,430
>> Nyní je možné
mají více než jednu základnu

174
00:08:22,430 --> 00:08:25,770
pouzdro nebo více než jedno
rekurzivní případ, v závislosti

175
00:08:25,770 --> 00:08:27,670
o Jaká je vaše funkce snaží dělat.

176
00:08:27,670 --> 00:08:31,650
Ty nejsou nutně jen na
jediný referenční případ nebo jeden rekurzivní

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

178
00:08:32,370 --> 00:08:35,320
Takže příklad něčeho
s více základnovými případech

179
00:08:35,320 --> 00:08:37,830
by mohl být tohle--
Fibonacci pořadové číslo.

180
00:08:37,830 --> 00:08:41,549
>> Možná si vzpomenete, od
základní školy dní

181
00:08:41,549 --> 00:08:45,740
že sekvence Fibonacci je definována
jako tohle-- první prvek je 0.

182
00:08:45,740 --> 00:08:46,890
Druhým prvkem je 1.

183
00:08:46,890 --> 00:08:49,230
Oba to jsou jen ze své podstaty.

184
00:08:49,230 --> 00:08:55,920
>> Pak je definován každý jiný prvek
jako součet n minus 1 a n minus 2.

185
00:08:55,920 --> 00:09:00,330
Takže třetí prvek
by být 0 plus 1 je 1.

186
00:09:00,330 --> 00:09:03,280
A pak čtvrtý element
by byl druhý prvek, 1,

187
00:09:03,280 --> 00:09:06,550
a třetí prvek, 1.

188
00:09:06,550 --> 00:09:08,507
A to by bylo 2.

189
00:09:08,507 --> 00:09:09,340
A tak dále a tak dále.

190
00:09:09,340 --> 00:09:11,680
>> Takže v tomto případě, máme dvě základní případy.

191
00:09:11,680 --> 00:09:14,850
Je-li n rovno 1, vrátit 0.

192
00:09:14,850 --> 00:09:18,560
Je-li n rovno 2, 1 vrátit.

193
00:09:18,560 --> 00:09:25,930
V opačném případě vrátí Fibonacci n
1 plus minus Fibonacci n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Tak to je více základní případy.

195
00:09:27,180 --> 00:09:29,271
A co více rekurzivních případech?

196
00:09:29,271 --> 00:09:31,520
No, je tu něco,
volal Collatz dohad.

197
00:09:31,520 --> 00:09:34,630
Nebudu říkat,
Víte, co to je,

198
00:09:34,630 --> 00:09:38,170
protože je to vlastně naše poslední
Problémem pro tuto konkrétní video.

199
00:09:38,170 --> 00:09:43,220
A to je naše cvičení
pracovat společně.

200
00:09:43,220 --> 00:09:46,760
>> Tak tady je to, co
Collatz dohad je--

201
00:09:46,760 --> 00:09:48,820
to platí pro každé kladné celé číslo.

202
00:09:48,820 --> 00:09:51,500
A to spekuluje, že je to
vždy možné se dostat zpátky

203
00:09:51,500 --> 00:09:55,060
1, pokud budete postupovat podle těchto kroků.

204
00:09:55,060 --> 00:09:57,560
Jestliže n je 1, zastavit.

205
00:09:57,560 --> 00:10:00,070
Musíme zpátky na 1, pokud n je 1.

206
00:10:00,070 --> 00:10:05,670
>> V opačném případě, projít tento
proces opět na n děleno 2.

207
00:10:05,670 --> 00:10:08,200
A uvidíme, jestli se můžete vrátit do 1.

208
00:10:08,200 --> 00:10:13,260
V opačném případě, je-li n liché, projít
tento proces znovu 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
nebo 3 krát n a 1.

210
00:10:15,552 --> 00:10:17,010
Takže tady máme jednotný referenční případ.

211
00:10:17,010 --> 00:10:18,430
Je-li n rovno 1, zastavit.

212
00:10:18,430 --> 00:10:20,230
Neděláme žádné další rekurzi.

213
00:10:20,230 --> 00:10:23,730
>> Ale my máme dvě rekurzivní případy.

214
00:10:23,730 --> 00:10:28,750
Pokud n je dokonce, děláme jednu rekurzivní
Případ, volání n děleno 2.

215
00:10:28,750 --> 00:10:33,950
Pokud je n liché, děláme jiný
rekurzivní případ na 3 krát N plus 1.

216
00:10:33,950 --> 00:10:39,120
>> A tak cíl pro toto video je
vzít druhý, video pozastavit,

217
00:10:39,120 --> 00:10:42,440
a pokusit se napsat tento
rekurzivní funkce Collatz

218
00:10:42,440 --> 00:10:47,640
kde předáte v hodnotě n, a
to spočítá, kolik kroků to

219
00:10:47,640 --> 00:10:52,430
znamená dostat na hodnotu 1, pokud spustíte z n
a budete postupovat tyto kroky nahoře.

220
00:10:52,430 --> 00:10:56,660
Pokud n je 1, to trvá 0 kroků.

221
00:10:56,660 --> 00:11:00,190
V opačném případě, bude to
jeden krok navíc nicméně

222
00:11:00,190 --> 00:11:06,200
řada kroků to trvá na obou n
děleno 2, pokud n je dokonce, nebo 3n plus 1

223
00:11:06,200 --> 00:11:08,100
pokud n je liché.

224
00:11:08,100 --> 00:11:11,190
>> Teď jsem dal na obrazovce zde
pár zkušebních věcí pro vás,

225
00:11:11,190 --> 00:11:15,690
pár testů případů pro vás, vidět
co tyto různé počty Collatz jsou,

226
00:11:15,690 --> 00:11:17,440
a také ilustrace
z kroků, které

227
00:11:17,440 --> 00:11:20,390
Je třeba prošel, takže můžete
druh vidět tento proces v akci.

228
00:11:20,390 --> 00:11:24,222
Takže pokud n je rovno
1, Collatz n je 0.

229
00:11:24,222 --> 00:11:26,180
Nemusíte dělat
něco dostat se zpátky do 1.

230
00:11:26,180 --> 00:11:27,600
Už jsi už tam.

231
00:11:27,600 --> 00:11:30,550
>> Pokud n je 2, trvá
jeden krok se dostat do 1.

232
00:11:30,550 --> 00:11:31,810
Začnete s 2.

233
00:11:31,810 --> 00:11:33,100
Tak, 2 není rovno 1.

234
00:11:33,100 --> 00:11:36,580
Takže to bude jeden krok
plus nicméně mnoho krocích,

235
00:11:36,580 --> 00:11:38,015
bere na n děleno 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 děleno 2 je 1.

238
00:11:42,910 --> 00:11:47,200
Takže to trvá jeden krok navíc nicméně
řada kroků trvá 1.

239
00:11:47,200 --> 00:11:49,720
1. bere nula kroky.

240
00:11:49,720 --> 00:11:52,370
>> Pro 3, jak můžete vidět, je tu
poměrně málo kroků zapojit.

241
00:11:52,370 --> 00:11:53,590
Můžete jít od 3.

242
00:11:53,590 --> 00:11:56,710
A pak jdete
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
To trvá sedm kroků dostat se zpátky do 1.

244
00:11:58,804 --> 00:12:01,220
A jak můžete vidět, je tu
pár dalších testovacích případů zde

245
00:12:01,220 --> 00:12:02,470
vyzkoušet program.

246
00:12:02,470 --> 00:12:03,970
Takže znovu, video pozastavit.

247
00:12:03,970 --> 00:12:09,210
A já půjdu skočit zpět teď
co je skutečný proces je tady,

248
00:12:09,210 --> 00:12:11,390
co to je dohad.

249
00:12:11,390 --> 00:12:14,140
>> Uvidíme, jestli můžete přijít na to,
jak definovat Collatz n

250
00:12:14,140 --> 00:12:19,967
tak, aby se vypočítá, kolik
kroky trvá dostat na 1.

251
00:12:19,967 --> 00:12:23,050
Takže doufejme, že jste se zastavil video
a nejste zrovna na mě čekají

252
00:12:23,050 --> 00:12:25,820
aby vám odpověď zde.

253
00:12:25,820 --> 00:12:29,120
Ale pokud jste dobře,
tady je odpověď stejně.

254
00:12:29,120 --> 00:12:33,070
>> Tak tady je možná definice
funkce Collatz.

255
00:12:33,070 --> 00:12:35,610
Naše základna case-- pokud n je
rovné 1, vrátíme 0.

256
00:12:35,610 --> 00:12:38,250
Neznamená to však trvat jakýkoli
Kroky se dostat zpět do 1.

257
00:12:38,250 --> 00:12:42,710
>> Jinak máme dvě rekurzivní cases--
jeden pro sudá čísla a jeden pro liché.

258
00:12:42,710 --> 00:12:47,164
Způsob, jakým jsem test na sudých čísel
je zkontrolovat, zda n mod 2 = 0.

259
00:12:47,164 --> 00:12:49,080
To je v podstatě, opět,
ptát na otázku,

260
00:12:49,080 --> 00:12:54,050
Pokud si vzpomínáte, co mod je-- kdybych
rozdělit n o 2 neexistuje žádný zbytek?

261
00:12:54,050 --> 00:12:55,470
To by být sudé číslo.

262
00:12:55,470 --> 00:13:01,370
>> A tak, když n mod 2 = 0 je
testování je to sudé číslo.

263
00:13:01,370 --> 00:13:04,250
Pokud ano, chci se vrátit 1,
proto, že to je určitě

264
00:13:04,250 --> 00:13:09,270
přičemž jeden krok navíc Collatz z
bez ohledu na počet je polovina ze mě.

265
00:13:09,270 --> 00:13:13,910
Jinak bych se chtěl vrátit 1
plus Collatz 3 krát n a 1.

266
00:13:13,910 --> 00:13:16,060
To byl druhý
rekurzivní krok, který jsme

267
00:13:16,060 --> 00:13:19,470
mohl vzít pro výpočet
Collatz-- počet kroků

268
00:13:19,470 --> 00:13:22,610
to znamená dostat zpět
na 1 přiděleno číslo.

269
00:13:22,610 --> 00:13:24,610
Tak doufejme, že tento příklad
ti dal trochu

270
00:13:24,610 --> 00:13:26,620
z chuti rekurzivních postupů.

271
00:13:26,620 --> 00:13:30,220
Doufejme, že si myslíte, že kód je
něco krásnější, jestliže budou provedeny

272
00:13:30,220 --> 00:13:32,760
v elegantním, rekurzivní způsobem.

273
00:13:32,760 --> 00:13:35,955
Ale i když ne, rekurze je
opravdu mocný nástroj nicméně.

274
00:13:35,955 --> 00:13:38,330
A tak je to určitě něco,
dostat hlavu kolem,

275
00:13:38,330 --> 00:13:41,360
protože budete moci vytvořit
docela v pohodě programy pomocí rekurze

276
00:13:41,360 --> 00:13:45,930
které by jinak mohly být složité psát
pokud používáte smyčky a iterace.

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

278
00:13:46,980 --> 00:13:48,780
To je CS50.

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