1
00:00:00,000 --> 00:00:05,860
>> [Prehrávanie hudby]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Pravdepodobne si myslí, že
kód slúži len na splnenie úlohy.

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

4
00:00:10,450 --> 00:00:11,664
Je to niečo robí.

5
00:00:11,664 --> 00:00:12,580
To je celkom veľa to.

6
00:00:12,580 --> 00:00:13,160
>> Tie skompilovať.

7
00:00:13,160 --> 00:00:13,993
Spustite program.

8
00:00:13,993 --> 00:00:15,370
Si dobré ísť.

9
00:00:15,370 --> 00:00:17,520
>> Ale verte tomu alebo nie, ak je
si kód na dlhú dobu,

10
00:00:17,520 --> 00:00:20,550
ste vlastne môže prísť vidieť
kód ako niečo, čo je krásne.

11
00:00:20,550 --> 00:00:23,275
To rieši problém v
Veľmi zaujímavý spôsob,

12
00:00:23,275 --> 00:00:26,510
alebo tam je proste niečo, čo naozaj
čistý o tom, ako to vyzerá.

13
00:00:26,510 --> 00:00:28,750
Tie by mohli byť smiať
sa na mňa, ale je to pravda.

14
00:00:28,750 --> 00:00:31,530
A rekurzia je jedným zo spôsobov,
sa nejako dostať túto myšlienku

15
00:00:31,530 --> 00:00:34,090
krásne, elegantné vyzerajúce kód.

16
00:00:34,090 --> 00:00:37,740
To rieši problémy, spôsoby, ktoré
sú zaujímavé, ľahko predstaviť,

17
00:00:37,740 --> 00:00:39,810
a prekvapivo krátke.

18
00:00:39,810 --> 00:00:43,190
>> Spôsob, akým funguje rekurzia
je, rekurzívne funkcie

19
00:00:43,190 --> 00:00:49,291
je definovaný ako funkcia, ktorá volá
sám ako súčasť jeho vykonanie.

20
00:00:49,291 --> 00:00:51,790
To sa môže zdať trochu divné,
a uvidíme trochu

21
00:00:51,790 --> 00:00:53,750
o tom, ako to funguje v okamihu.

22
00:00:53,750 --> 00:00:55,560
Ale opäť, tieto
rekurzívne postupy sú

23
00:00:55,560 --> 00:00:57,730
Bude tak elegantné
pretože idú

24
00:00:57,730 --> 00:01:00,410
na riešenie tohto problému, bez toho, aby
ktoré majú všetky tieto ostatné funkcie

25
00:01:00,410 --> 00:01:02,710
alebo tieto dlhé slučky.

26
00:01:02,710 --> 00:01:06,310
Uvidíte, že tieto rekurzívne
postupy sú bude vyzerať tak krátky.

27
00:01:06,310 --> 00:01:10,610
A naozaj sa chystáte robiť
váš kód vyzerať oveľa krajšie.

28
00:01:10,610 --> 00:01:12,560
>> Dám vám príklad
z toho vidieť, ako

29
00:01:12,560 --> 00:01:14,880
rekurzívne postup by mohol byť definovaný.

30
00:01:14,880 --> 00:01:18,202
Takže ak ste oboznámení s tým
od triede math pred mnohými rokmi,

31
00:01:18,202 --> 00:01:20,910
Je tu niečo, čo nazýva
Funkcia faktoriál, ktorý je zvyčajne

32
00:01:20,910 --> 00:01:25,340
označený ako výkričník, ktorý
je definovaný cez všetky pozitívne celé čísla.

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

34
00:01:28,850 --> 00:01:31,050
je násobiť všetky
čísla menšie ako

35
00:01:31,050 --> 00:01:33,750
alebo sa rovná n together--
všetky celé čísla menšie ako

36
00:01:33,750 --> 00:01:34,880
alebo rovná 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 ďalej.

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

40
00:01:44,800 --> 00:01:47,060
>> Ako programátori, my nie
použite N výkričník.

41
00:01:47,060 --> 00:01:51,840
Takže budeme definovať faktoriál
Funkcie ako fakt n.

42
00:01:51,840 --> 00:01:56,897
A budeme používať faktoriál k vytvoreniu
rekurzívne riešenie problému.

43
00:01:56,897 --> 00:01:59,230
A myslím, že by ste mohli nájsť
že je to oveľa viac vizuálne

44
00:01:59,230 --> 00:02:02,380
príťažlivý ako iteratívny
verzia tohto, čo

45
00:02:02,380 --> 00:02:05,010
budeme tiež sa pozrieť na za chvíľu.

46
00:02:05,010 --> 00:02:08,310
>> Tak tu je pár
facts-- hračka intended--

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

48
00:02:10,169 --> 00:02:13,090
Faktoriál 1, ako som povedal, 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 ďalej.

51
00:02:18,470 --> 00:02:20,810
Hovorili sme o 4 a 5 už.

52
00:02:20,810 --> 00:02:23,940
>> Ale pri pohľade na to, nie je to pravda?

53
00:02:23,940 --> 00:02:28,220
Nie je faktoriál 2 len
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 prečo jednoducho nemôžeme povedať, že,
pretože faktoriál 2 je 2 krát 1,

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

57
00:02:38,520 --> 00:02:40,900
>> A potom rozšírila túto myšlienku,
nie je faktoriál 3

58
00:02:40,900 --> 00:02:44,080
len 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 ďalej?

60
00:02:50,350 --> 00:02:52,530
V skutočnosti, faktoriálovej
akékoľvek množstvo môže len

61
00:02:52,530 --> 00:02:54,660
sa vyjadrí, ak sme trochu
o vykonávaní tohto navždy.

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

63
00:02:56,870 --> 00:02:59,910
ako je to časy n
faktoriál n mínus 1.

64
00:02:59,910 --> 00:03:04,840
Je to n krát produkt
všetky čísla menšie ako ja.

65
00:03:04,840 --> 00:03:08,890
>> Táto myšlienka, to
zovšeobecnenie problému,

66
00:03:08,890 --> 00:03:13,410
nám umožňuje rekurzívne
definovať faktoriálu funkcie.

67
00:03:13,410 --> 00:03:15,440
Pri definovaní funkcie
rekurzívne, je tu

68
00:03:15,440 --> 00:03:17,470
dve veci, ktoré musia byť súčasťou toho všetkého.

69
00:03:17,470 --> 00:03:20,990
Musíte mať niečo, čo nazýva
základný prípad, ktorý, keď ho spustiť,

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

71
00:03:22,480 --> 00:03:25,300
>> V opačnom prípade funkcie, ktorá volá
itself-- ako by sa mohlo imagine--

72
00:03:25,300 --> 00:03:26,870
by mohol pokračovať donekonečna.

73
00:03:26,870 --> 00:03:29,047
Funkcia volá funkciu
volanie funkcie volania

74
00:03:29,047 --> 00:03:30,380
Funkcia volá funkciu.

75
00:03:30,380 --> 00:03:32,380
Ak nemáte cestu
ho zastaviť, program

76
00:03:32,380 --> 00:03:34,760
bude účinne prilepené
v nekonečnej slučke.

77
00:03:34,760 --> 00:03:37,176
To sa zrúti nakoniec,
pretože to bude spustiť z pamäte.

78
00:03:37,176 --> 00:03:38,990
Ale to je vedľajšie.

79
00:03:38,990 --> 00:03:42,210
>> Potrebujeme mať nejaký iný spôsob, ako zastaviť
veci, okrem nášho programu zhadzovať,

80
00:03:42,210 --> 00:03:46,010
pretože program, ktorý havaruje je
Pravdepodobne nie krásna a elegantná.

81
00:03:46,010 --> 00:03:47,690
A tak hovoríme to referenčný prípad.

82
00:03:47,690 --> 00:03:50,610
Jedná sa o jednoduché riešenie
na problém, ktorý zastavuje

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

84
00:03:52,770 --> 00:03:55,220
Takže to je jedna časť
rekurzívne funkcie.

85
00:03:55,220 --> 00:03:56,820
>> Druhá časť je rekurzívny prípad.

86
00:03:56,820 --> 00:03:59,195
A to je miesto, kde rekurzia
bude skutočne konať.

87
00:03:59,195 --> 00:04:02,200
To je miesto, kde
Funkcia zavolá sama.

88
00:04:02,200 --> 00:04:05,940
>> Nebude volať seba v presne
rovnako tak, ako to bolo volané.

89
00:04:05,940 --> 00:04:08,880
Bude to nepatrná zmena
ktorá robí problém je to

90
00:04:08,880 --> 00:04:11,497
snaží vyriešiť malinký niečo menšie.

91
00:04:11,497 --> 00:04:14,330
Ale všeobecne prechádza babku
vyriešiť prevažnú časť roztoku

92
00:04:14,330 --> 00:04:17,450
na inú výzvu v rade.

93
00:04:17,450 --> 00:04:20,290
>> Ktorý z týchto pohľadov
ako základné veci tu?

94
00:04:20,290 --> 00:04:25,384
Ktorý z týchto vyzerá
Najjednoduchším riešením problému?

95
00:04:25,384 --> 00:04:27,550
Máme veľa faktoriál,
a tak by sme mohli pokračovať

96
00:04:27,550 --> 00:04:30,470
sa on-- 6, 7, 8, 9, 10, a tak ďalej.

97
00:04:30,470 --> 00:04:34,130
>> Ale jeden z nich vyzerá ako
dobrým príkladom, že je referenčný prípad.

98
00:04:34,130 --> 00:04:35,310
Je to veľmi jednoduché riešenie.

99
00:04:35,310 --> 00:04:37,810
Nemusíme robiť nič zvláštne.

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

101
00:04:40,560 --> 00:04:42,790
Nemusíme robiť akýkoľvek
násobenie vôbec.

102
00:04:42,790 --> 00:04:45,248
Vyzerá to, že v prípade, že budeme
aby sa pokúsila vyriešiť tento problém,

103
00:04:45,248 --> 00:04:47,600
a musíme zastaviť
rekurziu niekde,

104
00:04:47,600 --> 00:04:50,610
Pravdepodobne chceme zastaviť
za to, keď sa dostaneme do 1.

105
00:04:50,610 --> 00:04:54,580
Nechceme zastaviť pred tým.

106
00:04:54,580 --> 00:04:56,660
>> Takže ak budeme definovať
náš faktoriál funkcie,

107
00:04:56,660 --> 00:04:58,690
tu je kostra pre
ako by sme mohli urobiť.

108
00:04:58,690 --> 00:05:03,110
Musíme zapojiť v týchto dvoch things--
základný prípad, a rekurzívne prípad.

109
00:05:03,110 --> 00:05:04,990
Čo je to referenčný prípad?

110
00:05:04,990 --> 00:05:10,150
Ak je n rovné 1, vrátiť 1-- to je
naozaj jednoduchý problém k riešeniu.

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

112
00:05:11,890 --> 00:05:13,860
Nie sú to 1 krát čokoľvek.

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

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

115
00:05:17,170 --> 00:05:19,620
A tak to môže byť naša základňa prípad.

116
00:05:19,620 --> 00:05:24,730
Ak by sme si prešiel 1 do tohto
funkcie, jednoducho budeme vracať 1.

117
00:05:24,730 --> 00:05:27,320
>> Čo je rekurzívny
Prípad pravdepodobne vyzerať?

118
00:05:27,320 --> 00:05:32,445
Pre každý iné číslo
okrem 1, čo je vzor?

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

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

121
00:05:38,160 --> 00:05:42,130
>> Ak vezmeme faktoriál 3,
je to 3 krát faktoriál 3 mínus 1,

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

123
00:05:43,070 --> 00:05:47,330
A tak, keď nie sme
pri pohľade na 1, inak

124
00:05:47,330 --> 00:05:51,710
return n násobok
faktoriál n mínus 1.

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

126
00:05:53,210 --> 00:05:57,360
>> A v záujme mať mierne
čistejšie a elegantnejšie kód,

127
00:05:57,360 --> 00:06:01,440
vedia, že ak máme jednoriadkové slučky
alebo jednoriadkový podmienené vetvy,

128
00:06:01,440 --> 00:06:04,490
sa môžeme zbaviť všetky
zložené zátvorky okolo nich.

129
00:06:04,490 --> 00:06:06,850
Takže môžeme upevniť to k tomu.

130
00:06:06,850 --> 00:06:09,640
To má presne rovnaké
funkcia je tento.

131
00:06:09,640 --> 00:06:13,850
>> Ja som len odnášať kučeravé
traky, pretože tam je len jeden riadok

132
00:06:13,850 --> 00:06:18,500
vo vnútri týchto podmienených vetiev.

133
00:06:18,500 --> 00:06:21,160
Tak to sa správajú rovnako.

134
00:06:21,160 --> 00:06:23,800
Ak je n rovné 1, 1 vrátiť.

135
00:06:23,800 --> 00:06:28,351
V opačnom prípade vracia n-krát
faktoriál n mínus 1.

136
00:06:28,351 --> 00:06:29,850
Takže robíme problém menšie.

137
00:06:29,850 --> 00:06:33,850
Ak n začína ako 5, ideme
vrátiť 5 krát faktoriál 4.

138
00:06:33,850 --> 00:06:37,100
A uvidíme za chvíľu, keď hovoríme
o volanie stack-- v inom videu

139
00:06:37,100 --> 00:06:39,390
kde hovoríme o
zavolajte stack-- dozvieme

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

141
00:06:41,630 --> 00:06:46,970
>> Ale zatiaľ čo faktoriál 5 hovorí:
vrátiť 5 krát faktoriál 4, a 4

142
00:06:46,970 --> 00:06:49,710
sa chystá povedať, OK, dobre, návrat
4 krát faktoriál 3.

143
00:06:49,710 --> 00:06:51,737
A ako môžete vidieť, že sme
druh blíži 1.

144
00:06:51,737 --> 00:06:53,820
Sme stále bližšie a
bližšie k tomuto základnému prípadu.

145
00:06:53,820 --> 00:06:58,180
>> A akonáhle sme narazili základné veci,
všetky predchádzajúce funkcie

146
00:06:58,180 --> 00:07:00,540
poznať odpoveď, ktoré hľadali.

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

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

149
00:07:06,760 --> 00:07:10,090
Takže výzva na faktoriálu
2 môže vrátiť 2 krát 1,

150
00:07:10,090 --> 00:07:13,980
a dať to späť do faktoriál
3, ktorý čaká na tento výsledok.

151
00:07:13,980 --> 00:07:17,110
>> A potom to môže vypočítať
Jej výsledok, 3x 2 je 6,

152
00:07:17,110 --> 00:07:18,907
a vráti ho faktoriál 4.

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

154
00:07:20,740 --> 00:07:23,810
kde je to znázornené trochu
viac než to, čo hovorím teraz.

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 sebe je riešením
výpočet faktoriál čísla.

157
00:07:29,300 --> 00:07:31,527
>> Je to len štyri riadky kódu.

158
00:07:31,527 --> 00:07:32,610
To je celkom v pohode, nie?

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

160
00:07:35,480 --> 00:07:38,580
>> Takže všeobecne, ale nie
vždy, rekurzívne funkcie

161
00:07:38,580 --> 00:07:41,190
môže nahradiť slučkou v
non-rekurzívne funkcie.

162
00:07:41,190 --> 00:07:46,100
Tak tu, vedľa seba, je iteratívny
verzia faktoriálnym funkcie.

163
00:07:46,100 --> 00:07:49,650
Obe tieto vypočítať
presne to isté.

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

165
00:07:52,170 --> 00:07:54,990
Verzia na ľavej strane
používa rekurziu, ako to urobiť.

166
00:07:54,990 --> 00:07:58,320
Verzia na pravej strane
využíva opakovanie, ako to urobiť.

167
00:07:58,320 --> 00:08:02,050
>> A upozornenie, musíme vyhlásiť,
premenná celé číslo produktu.

168
00:08:02,050 --> 00:08:02,940
A potom sme slučka.

169
00:08:02,940 --> 00:08:06,790
Tak dlho, ako n je väčšie ako 0, sme
udržiavať vynásobením tohto výrobku N

170
00:08:06,790 --> 00:08:09,890
a dekrementování n, kým
spočítame produktu.

171
00:08:09,890 --> 00:08:14,600
Takže tieto dve funkcie, opäť,
robiť presne to isté.

172
00:08:14,600 --> 00:08:19,980
Ale nerobia to v
presne rovnakým spôsobom.

173
00:08:19,980 --> 00:08:22,430
>> Teraz je možné
majú viac ako jednu základňu

174
00:08:22,430 --> 00:08:25,770
puzdro alebo viac než jedno
rekurzívne prípad, v závislosti

175
00:08:25,770 --> 00:08:27,670
o Aká je vaša funkcia snaží robiť.

176
00:08:27,670 --> 00:08:31,650
Tie nie sú nevyhnutne len na
jediný referenčný prípad alebo jeden rekurzívne

177
00:08:31,650 --> 00:08:32,370
prípad.

178
00:08:32,370 --> 00:08:35,320
Takže príklad niečoho
s viac základňovými prípadoch

179
00:08:35,320 --> 00:08:37,830
by mohol byť tohle--
Fibonacci poradové číslo.

180
00:08:37,830 --> 00:08:41,549
>> Možno si spomeniete, od
základnej školy dní

181
00:08:41,549 --> 00:08:45,740
že sekvencie Fibonacci je definovaná
ako tohle-- prvý prvok je 0.

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

183
00:08:46,890 --> 00:08:49,230
Obaja to sú len zo svojej podstaty.

184
00:08:49,230 --> 00:08:55,920
>> Potom je definovaný každý iný prvok
ako súčet n mínus 1 a n mínus 2.

185
00:08:55,920 --> 00:09:00,330
Takže tretí prvok
by byť 0 plus 1 je 1.

186
00:09:00,330 --> 00:09:03,280
A potom štvrtý element
by bol druhý prvok, 1,

187
00:09:03,280 --> 00:09:06,550
a tretí prvok, 1.

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

189
00:09:08,507 --> 00:09:09,340
A tak ďalej a tak ďalej.

190
00:09:09,340 --> 00:09:11,680
>> Takže v tomto prípade, máme dve základné prípady.

191
00:09:11,680 --> 00:09:14,850
Ak je n rovné 1, vrátiť 0.

192
00:09:14,850 --> 00:09:18,560
Ak je n rovné 2, 1 vrátiť.

193
00:09:18,560 --> 00:09:25,930
V opačnom prípade vráti Fibonacci n
1 plus mínus Fibonacci n mínus 2.

194
00:09:25,930 --> 00:09:27,180
>> Tak to je viac základné prípady.

195
00:09:27,180 --> 00:09:29,271
A čo viac rekurzívnych prípadoch?

196
00:09:29,271 --> 00:09:31,520
No, je tu niečo,
volal Collatz dohad.

197
00:09:31,520 --> 00:09:34,630
Nebudem hovoriť,
Viete, čo to je,

198
00:09:34,630 --> 00:09:38,170
pretože je to vlastne naša posledná
Problémom pre túto konkrétnu video.

199
00:09:38,170 --> 00:09:43,220
A to je naša cvičenie
pracovať spoločne.

200
00:09:43,220 --> 00:09:46,760
>> Tak tu je to, čo
Collatz dohad je--

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

202
00:09:48,820 --> 00:09:51,500
A to špekuluje, že je to
vždy možné sa dostať späť

203
00:09:51,500 --> 00:09:55,060
1, ak budete postupovať podľa týchto krokov.

204
00:09:55,060 --> 00:09:57,560
Ak n je 1, zastaviť.

205
00:09:57,560 --> 00:10:00,070
Musíme späť na 1, ak n je 1.

206
00:10:00,070 --> 00:10:05,670
>> V opačnom prípade, prejsť tento
proces opäť na n deleno 2.

207
00:10:05,670 --> 00:10:08,200
A uvidíme, či sa môžete vrátiť do 1.

208
00:10:08,200 --> 00:10:13,260
V opačnom prípade, ak je n nepárne, prejsť
tento proces znovu 3n plus 1,

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

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

211
00:10:17,010 --> 00:10:18,430
Ak je n rovné 1, zastaviť.

212
00:10:18,430 --> 00:10:20,230
Nerobíme žiadne ďalšie rekurziu.

213
00:10:20,230 --> 00:10:23,730
>> Ale my máme dve rekurzívne prípady.

214
00:10:23,730 --> 00:10:28,750
Ak n je dokonca, robíme jednu rekurzívne
Prípad, volanie n deleno 2.

215
00:10:28,750 --> 00:10:33,950
Pokiaľ je n nepárne, robíme iný
rekurzívne prípad na 3 krát N plus 1.

216
00:10:33,950 --> 00:10:39,120
>> A tak cieľ pre toto video je
vziať druhý, video pozastaviť,

217
00:10:39,120 --> 00:10:42,440
a pokúsiť sa napísať tento
rekurzívne funkcie Collatz

218
00:10:42,440 --> 00:10:47,640
kde odovzdáte v hodnote n, a
to spočíta, koľko krokov to

219
00:10:47,640 --> 00:10:52,430
znamená dostať na hodnotu 1, ak spustíte z n
a budete postupovať tieto kroky hore.

220
00:10:52,430 --> 00:10:56,660
Ak n je 1, to trvá 0 krokov.

221
00:10:56,660 --> 00:11:00,190
V opačnom prípade, bude to
jeden krok navyše však

222
00:11:00,190 --> 00:11:06,200
rad krokov to trvá na oboch n
delené 2, ak n je dokonca, alebo 3n plus 1

223
00:11:06,200 --> 00:11:08,100
ak n je nepárne.

224
00:11:08,100 --> 00:11:11,190
>> Teraz som dal na obrazovke tu
pár skúšobných vecí pre vás,

225
00:11:11,190 --> 00:11:15,690
pár testov prípadov pre vás, vidieť
čo tieto rôzne počty Collatz sú,

226
00:11:15,690 --> 00:11:17,440
a tiež ilustrácie
z krokov, ktoré

227
00:11:17,440 --> 00:11:20,390
Treba prešiel, takže môžete
druh vidieť tento proces v akcii.

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

229
00:11:24,222 --> 00:11:26,180
Nemusíte robiť
niečo dostať sa späť do 1.

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

231
00:11:27,600 --> 00:11:30,550
>> Ak n je 2, trvá
jeden krok sa dostať 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 nie je rovné 1.

234
00:11:33,100 --> 00:11:36,580
Takže to bude jeden krok
plus však veľa krokoch,

235
00:11:36,580 --> 00:11:38,015
berie na n deleno 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 deleno 2 je 1.

238
00:11:42,910 --> 00:11:47,200
Takže to trvá jeden krok navyše však
rad krokov trvá 1.

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

240
00:11:49,720 --> 00:11:52,370
>> Pre 3, ako môžete vidieť, je tu
pomerne málo krokov zapojiť.

241
00:11:52,370 --> 00:11:53,590
Môžete ísť od 3.

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

243
00:11:56,710 --> 00:11:58,804
To trvá sedem krokov dostať sa späť do 1.

244
00:11:58,804 --> 00:12:01,220
A ako môžete vidieť, je tu
pár ďalších testovacích prípadov tu

245
00:12:01,220 --> 00:12:02,470
vyskúšať program.

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

247
00:12:03,970 --> 00:12:09,210
A ja pôjdem skočiť späť teraz
čo je skutočný proces je tu,

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

249
00:12:11,390 --> 00:12:14,140
>> Uvidíme, či môžete prísť na to,
ako definovať Collatz n

250
00:12:14,140 --> 00:12:19,967
tak, aby sa vypočíta, koľko
kroky trvá dostať na 1.

251
00:12:19,967 --> 00:12:23,050
Takže dúfajme, že ste sa zastavil video
a nie ste práve na mňa čakajú

252
00:12:23,050 --> 00:12:25,820
aby vám odpoveď tu.

253
00:12:25,820 --> 00:12:29,120
Ale ak ste dobre,
tu je odpoveď rovnako.

254
00:12:29,120 --> 00:12:33,070
>> Tak tu je možná definícia
funkcie Collatz.

255
00:12:33,070 --> 00:12:35,610
Naša základňa case-- ak n je
rovné 1, vrátime 0.

256
00:12:35,610 --> 00:12:38,250
Neznamená to však trvať akýkoľvek
Kroky sa dostať späť do 1.

257
00:12:38,250 --> 00:12:42,710
>> Inak máme dve rekurzívne cases--
jeden pre párne čísla a jeden pre nepárne.

258
00:12:42,710 --> 00:12:47,164
Spôsob, akým som test na párnych čísel
je skontrolovať, či n mod 2 = 0.

259
00:12:47,164 --> 00:12:49,080
To je v podstate, opäť,
pýtať na otázku,

260
00:12:49,080 --> 00:12:54,050
Ak si spomínate, čo mod je-- keby som
rozdeliť n o 2 neexistuje žiadny zvyšok?

261
00:12:54,050 --> 00:12:55,470
To by byť párne číslo.

262
00:12:55,470 --> 00:13:01,370
>> A tak, keď n mod 2 = 0 je
testovanie je to párne číslo.

263
00:13:01,370 --> 00:13:04,250
Ak áno, chcem sa vrátiť 1,
preto, že to je určite

264
00:13:04,250 --> 00:13:09,270
pričom jeden krok navyše Collatz z
bez ohľadu na počet je polovica zo mňa.

265
00:13:09,270 --> 00:13:13,910
Inak by som sa chcel vrátiť 1
plus Collatz 3 krát n a 1.

266
00:13:13,910 --> 00:13:16,060
To bol druhý
rekurzívne krok, ktorý sme

267
00:13:16,060 --> 00:13:19,470
mohol vziať na výpočet
Collatz-- počet krokov

268
00:13:19,470 --> 00:13:22,610
to znamená dostať späť
na 1 pridelené číslo.

269
00:13:22,610 --> 00:13:24,610
Tak dúfajme, že tento príklad
ti dal trochu

270
00:13:24,610 --> 00:13:26,620
z chuti rekurzívnych postupov.

271
00:13:26,620 --> 00:13:30,220
Dúfajme, že si myslíte, že kód je
niečo krajšie, ak budú vykonané

272
00:13:30,220 --> 00:13:32,760
v elegantnom, rekurzívne spôsobom.

273
00:13:32,760 --> 00:13:35,955
Ale aj keď nie, rekurzia je
naozaj mocný nástroj však.

274
00:13:35,955 --> 00:13:38,330
A tak je to určite niečo,
dostať hlavu okolo,

275
00:13:38,330 --> 00:13:41,360
pretože budete môcť vytvoriť
celkom v pohode programy pomocou rekurzia

276
00:13:41,360 --> 00:13:45,930
ktoré by inak mohli byť zložité písať
ak používate slučky a iterácie.

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

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

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