1
00:00:00,000 --> 00:00:05,860
>> [Predvaja glasba]

2
00:00:05,860 --> 00:00:09,530
>> Doug LLOYD: Verjetno mislite, da
Koda se samo uporablja za dokončanje naloge.

3
00:00:09,530 --> 00:00:10,450
Pišete ven.

4
00:00:10,450 --> 00:00:11,664
To počne nekaj.

5
00:00:11,664 --> 00:00:12,580
To je precej to.

6
00:00:12,580 --> 00:00:13,160
>> Vam pripravijo ga.

7
00:00:13,160 --> 00:00:13,993
Zaženete program.

8
00:00:13,993 --> 00:00:15,370
Ste na dobri poti.

9
00:00:15,370 --> 00:00:17,520
>> Ampak verjeli ali ne, če
ste kodo za dolgo časa,

10
00:00:17,520 --> 00:00:20,550
ste dejansko lahko prišli pogledat
oznaka, kot nekaj, kar je lepo.

11
00:00:20,550 --> 00:00:23,275
Rešuje težave v
Zelo zanimiv način,

12
00:00:23,275 --> 00:00:26,510
ali pa je samo nekaj res
čeden o tem, kako to izgleda.

13
00:00:26,510 --> 00:00:28,750
Morda se smejala
vame, ampak je res.

14
00:00:28,750 --> 00:00:31,530
In rekurzija je eden od načinov
da nekako dobili to idejo

15
00:00:31,530 --> 00:00:34,090
lepe, elegantne-videti kodo.

16
00:00:34,090 --> 00:00:37,740
To rešuje probleme na načine, ki
zanimiv, enostaven za vizualizacijo,

17
00:00:37,740 --> 00:00:39,810
in presenetljivo kratek.

18
00:00:39,810 --> 00:00:43,190
>> Način rekurzija deluje
je rekurzivna funkcija

19
00:00:43,190 --> 00:00:49,291
je opredeljena kot funkcija, ki kliče
sama kot del njegove izvedbe.

20
00:00:49,291 --> 00:00:51,790
To se morda zdi malo čudno,
in bomo videli malo

21
00:00:51,790 --> 00:00:53,750
o tem, kako to deluje v trenutku.

22
00:00:53,750 --> 00:00:55,560
Ampak še enkrat, ti
rekurzivni postopki

23
00:00:55,560 --> 00:00:57,730
bo tako elegantno
ker oni gredo

24
00:00:57,730 --> 00:01:00,410
da bi rešili ta problem, ne da
ob vseh teh drugih funkcij

25
00:01:00,410 --> 00:01:02,710
ali te dolge zanke.

26
00:01:02,710 --> 00:01:06,310
Boste videli, da ti rekurzivna
Postopki bodo videti tako kratka.

27
00:01:06,310 --> 00:01:10,610
In res se dogaja, da bi
kodo videti veliko lepša.

28
00:01:10,610 --> 00:01:12,560
>> Dal vam bom primer
to, da vidim, kako

29
00:01:12,560 --> 00:01:14,880
rekurzivni postopek se lahko opredeliti.

30
00:01:14,880 --> 00:01:18,202
Torej, če ste seznanjeni s tem
iz matematike razred pred mnogimi leti,

31
00:01:18,202 --> 00:01:20,910
Nekaj ​​je imenovan
Funkcija faktorski, ki je ponavadi

32
00:01:20,910 --> 00:01:25,340
označimo kot klicajem, ki
je opredeljena kot vsa pozitivna cela števila.

33
00:01:25,340 --> 00:01:28,850
In način, ki n
factorial se izračuna

34
00:01:28,850 --> 00:01:31,050
se ti množijo vse
številke manj kot

35
00:01:31,050 --> 00:01:33,750
ali enako n together--
vsa cela števila manj kot

36
00:01:33,750 --> 00:01:34,880
ali enaka n skupaj.

37
00:01:34,880 --> 00:01:39,850
>> Torej 5 faktorsko je 5-krat
4-krat 3 krat 2-krat 1.

38
00:01:39,850 --> 00:01:43,020
In 4 faktorsko je 4-krat
3 krat 2-krat 1 in tako naprej.

39
00:01:43,020 --> 00:01:44,800
Dobiš idejo.

40
00:01:44,800 --> 00:01:47,060
>> Kot programerji, ne bomo
uporabite N klicaj.

41
00:01:47,060 --> 00:01:51,840
Torej bomo opredeliti factorial
Funkcija kot dejstvo n.

42
00:01:51,840 --> 00:01:56,897
In bomo uporabili fakulteto za ustvarjanje
rekurzivna rešitev problema.

43
00:01:56,897 --> 00:01:59,230
In mislim, da bi našli
da je veliko bolj vizualno

44
00:01:59,230 --> 00:02:02,380
privlačna kot iterativni
različica tega, kar

45
00:02:02,380 --> 00:02:05,010
bomo lahko tudi pogled na v tem trenutku.

46
00:02:05,010 --> 00:02:08,310
>> Torej, tukaj je nekaj
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
o factorial--
factorial funkcija.

48
00:02:10,169 --> 00:02:13,090
Fakulteto 1, kot sem rekel, je 1.

49
00:02:13,090 --> 00:02:15,690
Fakulteto 2 je 2-krat 1.

50
00:02:15,690 --> 00:02:18,470
Fakulteto 3 3
krat 2 krat 1, in tako naprej.

51
00:02:18,470 --> 00:02:20,810
Pogovarjala sva se o 4. in 5. že.

52
00:02:20,810 --> 00:02:23,940
>> Ampak gledamo na to, ali ni to res?

53
00:02:23,940 --> 00:02:28,220
Ne fakulteto 2 le
2-krat fakulteto 1?

54
00:02:28,220 --> 00:02:31,130
Mislim, faktorsko od 1. 1.

55
00:02:31,130 --> 00:02:34,940
Torej, zakaj ne moremo ravno reči, da,
saj faktorsko od 2 je 2-krat 1,

56
00:02:34,940 --> 00:02:38,520
to je res samo 2-krat
fakulteto 1?

57
00:02:38,520 --> 00:02:40,900
>> In potem se razteza to idejo,
ni factorial od 3

58
00:02:40,900 --> 00:02:44,080
le 3-krat fakulteto 2?

59
00:02:44,080 --> 00:02:50,350
In faktorsko dne 4. je 4-krat
fakulteto 3, in tako naprej?

60
00:02:50,350 --> 00:02:52,530
V bistvu, faktorsko
poljubnega števila lahko samo

61
00:02:52,530 --> 00:02:54,660
se je izrazil, če bi nekako
za opravljanje tole večno.

62
00:02:54,660 --> 00:02:56,870
Mi lahko nekako posploševati
fakulteto problem

63
00:02:56,870 --> 00:02:59,910
saj je n-krat
faktorski n minus 1.

64
00:02:59,910 --> 00:03:04,840
To je n-krat produkt
vse številke manj kot mene.

65
00:03:04,840 --> 00:03:08,890
>> Ta ideja, to
posplošitev problema,

66
00:03:08,890 --> 00:03:13,410
nam omogoča, da rekurzivno
opredeliti faktorsko funkcijo.

67
00:03:13,410 --> 00:03:15,440
Ko določite funkcijo
rekurzivno, tam je

68
00:03:15,440 --> 00:03:17,470
dve stvari, ki jih potrebujejo, da se del tega.

69
00:03:17,470 --> 00:03:20,990
Morate imeti nekaj, kar se imenuje
osnovna ureditev, ki, ko ga sproži,

70
00:03:20,990 --> 00:03:22,480
bodo prenehali rekurzivno proces.

71
00:03:22,480 --> 00:03:25,300
>> Sicer funkcija, ki zahteva
itself-- kot si morda imagine--

72
00:03:25,300 --> 00:03:26,870
bi šel na večno.

73
00:03:26,870 --> 00:03:29,047
Funkcija pokliče funkcijo
poziva funkcijskih klicev

74
00:03:29,047 --> 00:03:30,380
funkcija pokliče funkcijo.

75
00:03:30,380 --> 00:03:32,380
Če nimate pot
da bi ga ustavili, vaš program

76
00:03:32,380 --> 00:03:34,760
bo učinkovito zatakne
na neskončno zanko.

77
00:03:34,760 --> 00:03:37,176
To bo crash na koncu,
ker bo zmanjkalo pomnilnika.

78
00:03:37,176 --> 00:03:38,990
Ampak to je poleg točke.

79
00:03:38,990 --> 00:03:42,210
>> Moramo imeti kak drug način za ustavitev
Stvari poleg našega programa treskav,

80
00:03:42,210 --> 00:03:46,010
ker je program, ki se zruši, je
Verjetno ni lepa in elegantna.

81
00:03:46,010 --> 00:03:47,690
In zato pravimo ta osnovna ureditev.

82
00:03:47,690 --> 00:03:50,610
To je enostavna rešitev
na problem, ki se ustavi

83
00:03:50,610 --> 00:03:52,770
rekurzivni proces, ki se pojavljajo.

84
00:03:52,770 --> 00:03:55,220
Torej, to je en del
rekurzivna funkcija.

85
00:03:55,220 --> 00:03:56,820
>> Drugi del je rekurzivnega primera.

86
00:03:56,820 --> 00:03:59,195
In to je, če rekurzijska
bo dejansko potekala.

87
00:03:59,195 --> 00:04:02,200
To je, če
Funkcija bo sam poklical.

88
00:04:02,200 --> 00:04:05,940
>> To se ne bo poklical v točno
na enak način je bil imenovan.

89
00:04:05,940 --> 00:04:08,880
To bo rahla sprememba
da naredi problem, da je

90
00:04:08,880 --> 00:04:11,497
poskuša rešiti poskočno malo manjši.

91
00:04:11,497 --> 00:04:14,330
Vendar je na splošno prehaja buck
reševanja večji del raztopine

92
00:04:14,330 --> 00:04:17,450
v drug klic po vrsti.

93
00:04:17,450 --> 00:04:20,290
>> Kateri od teh pogledov
kot osnovnem scenariju tukaj?

94
00:04:20,290 --> 00:04:25,384
Kateri od teh izgleda
Najpreprostejša rešitev problema?

95
00:04:25,384 --> 00:04:27,550
Imamo kup factorials,
in bi še naprej

96
00:04:27,550 --> 00:04:30,470
tekoč on-- 6, 7, 8, 9, 10, in tako naprej.

97
00:04:30,470 --> 00:04:34,130
>> Toda eden od teh izgleda kot
dober primer, da je osnovna.

98
00:04:34,130 --> 00:04:35,310
To je zelo preprosta rešitev.

99
00:04:35,310 --> 00:04:37,810
Nimamo narediti nič posebnega.

100
00:04:37,810 --> 00:04:40,560
>> Fakulteto 1. je samo 1.

101
00:04:40,560 --> 00:04:42,790
Mi ne bi bilo treba storiti vse
množenje sploh.

102
00:04:42,790 --> 00:04:45,248
Zdi se, kot če gremo
poskusiti in rešiti ta problem,

103
00:04:45,248 --> 00:04:47,600
in moramo ustaviti
rekurzije nekje,

104
00:04:47,600 --> 00:04:50,610
bomo verjetno želeli ustaviti
da ko pridemo do 1.

105
00:04:50,610 --> 00:04:54,580
Mi ne želimo ustaviti pred tem.

106
00:04:54,580 --> 00:04:56,660
>> Torej, če smo opredeljevanju
naša faktorski funkcija,

107
00:04:56,660 --> 00:04:58,690
tukaj je okostje za
kako lahko to storimo.

108
00:04:58,690 --> 00:05:03,110
Moramo priključiti v teh dveh things--
osnovna ureditev in rekurzivni primer.

109
00:05:03,110 --> 00:05:04,990
Kakšna je osnovna?

110
00:05:04,990 --> 00:05:10,150
Če je n enak 1, vrne 1-- to
res preprost problem rešiti.

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

112
00:05:11,890 --> 00:05:13,860
To ni 1 krat karkoli.

113
00:05:13,860 --> 00:05:15,020
To je samo 1.

114
00:05:15,020 --> 00:05:17,170
To je zelo preprosto dejstvo.

115
00:05:17,170 --> 00:05:19,620
In tako, da se lahko naša baza primera.

116
00:05:19,620 --> 00:05:24,730
Če se bomo opravili 1 v to
funkcija, bomo samo vrniti 1.

117
00:05:24,730 --> 00:05:27,320
>> Kaj je rekurzivna
primer verjetno izgledal?

118
00:05:27,320 --> 00:05:32,445
Za vsako drugo številko
poleg 1, kaj je vzorec?

119
00:05:32,445 --> 00:05:35,780
No, če smo ob
fakulteto n,

120
00:05:35,780 --> 00:05:38,160
da je n-krat faktorsko n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Če smo ob fakulteto od 3,
to je 3-krat fakulteto 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
In tako, če ne bomo
gledamo na 1, sicer

124
00:05:47,330 --> 00:05:51,710
donosnost n krat
faktorski n minus 1.

125
00:05:51,710 --> 00:05:53,210
To je precej preprosta.

126
00:05:53,210 --> 00:05:57,360
>> In zaradi nekoliko ob
čistejše in bolj elegantno kodo,

127
00:05:57,360 --> 00:06:01,440
vem, da če imamo enovrstični zanke
ali enovrstični pogojni panoge,

128
00:06:01,440 --> 00:06:04,490
bomo lahko znebiti vse
zaviti oklepaji okoli njih.

129
00:06:04,490 --> 00:06:06,850
Tako bomo lahko to utrditi s tem.

130
00:06:06,850 --> 00:06:09,640
To je popolnoma enaka
funkcionalnosti, kot je ta.

131
00:06:09,640 --> 00:06:13,850
>> Jaz sem samo jemlje kodrasti
naramnice, ker tam je samo ena vrstica

132
00:06:13,850 --> 00:06:18,500
znotraj teh pogojnih podružnic.

133
00:06:18,500 --> 00:06:21,160
Torej ti se obnašajo enako.

134
00:06:21,160 --> 00:06:23,800
Če je n enak 1, vrne 1.

135
00:06:23,800 --> 00:06:28,351
V nasprotnem primeru vrne n-krat
fakulteto n minus 1.

136
00:06:28,351 --> 00:06:29,850
Tako smo kar problem manjši.

137
00:06:29,850 --> 00:06:33,850
Če n začne kot 5, se bomo
vrne 5-krat fakulteto 4.

138
00:06:33,850 --> 00:06:37,100
In bomo videli čez minuto, ko govorimo
o razpisu stack-- v drugi video

139
00:06:37,100 --> 00:06:39,390
kadar govorimo o
pokličite stack-- bomo naučili

140
00:06:39,390 --> 00:06:41,630
o tem, zakaj ravno ta proces deluje.

141
00:06:41,630 --> 00:06:46,970
>> Toda medtem ko faktorsko 5 pravi,
vrne 5-krat fakulteto 4 in 4

142
00:06:46,970 --> 00:06:49,710
je reči, OK, dobro, vračanje
4-krat fakulteto 3.

143
00:06:49,710 --> 00:06:51,737
In kot vidite, smo
nekako približuje 1.

144
00:06:51,737 --> 00:06:53,820
Mi smo bližje in
bližje tej osnovni scenarij.

145
00:06:53,820 --> 00:06:58,180
>> In ko smo zadeli osnovno zadevo,
vseh prejšnjih funkcij

146
00:06:58,180 --> 00:07:00,540
imajo odgovor so iskali.

147
00:07:00,540 --> 00:07:03,900
Faktorski dne 2. rekel donos
2-krat fakulteto 1.

148
00:07:03,900 --> 00:07:06,760
No, faktorski od 1 donosov 1.

149
00:07:06,760 --> 00:07:10,090
Tako da je razpis za fakulteto
z dne 2. lahko vrnete 2-krat 1,

150
00:07:10,090 --> 00:07:13,980
in dal to nazaj na fakulteto
3, ki je čakala za ta rezultat.

151
00:07:13,980 --> 00:07:17,110
>> In potem lahko izračunamo
njegove rezultat, 3 krat 2 je 6,

152
00:07:17,110 --> 00:07:18,907
in ga dal nazaj na fakulteto 4.

153
00:07:18,907 --> 00:07:20,740
In spet, imamo
video na klicni dimnika

154
00:07:20,740 --> 00:07:23,810
če je to prikazano malo
več kot to, kar sem rekel, prav zdaj.

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

156
00:07:25,300 --> 00:07:29,300
Že samo s tem je rešitev za
izračuna fakulteto števila.

157
00:07:29,300 --> 00:07:31,527
>> To je le štiri vrstice kode.

158
00:07:31,527 --> 00:07:32,610
To je zelo kul, kajne?

159
00:07:32,610 --> 00:07:35,480
To je nekako seksi.

160
00:07:35,480 --> 00:07:38,580
>> Torej v splošnem, toda ne
Vedno, rekurzivna funkcija

161
00:07:38,580 --> 00:07:41,190
more nadomestiti zanke v
non-rekurzivna funkcija.

162
00:07:41,190 --> 00:07:46,100
Torej, tukaj, drug ob drugem, je iterativen
različica faktorski funkcije.

163
00:07:46,100 --> 00:07:49,650
Oba izračunajte
natanko isto stvar.

164
00:07:49,650 --> 00:07:52,170
>> Oba izračuna fakulteto n.

165
00:07:52,170 --> 00:07:54,990
Različica na levi
uporablja rekurzijo, da to storite.

166
00:07:54,990 --> 00:07:58,320
Različica na desni
uporablja ponovitev, da to storite.

167
00:07:58,320 --> 00:08:02,050
>> In obvestilo, da moramo razglasiti
spremenljivka celo izdelek.

168
00:08:02,050 --> 00:08:02,940
In potem smo zanka.

169
00:08:02,940 --> 00:08:06,790
Dokler je n večji kot 0, smo
obdržati pomnoži ta izdelek z N

170
00:08:06,790 --> 00:08:09,890
in pomanjšanja n do
izračunamo izdelek.

171
00:08:09,890 --> 00:08:14,600
Torej ti dve funkciji, še enkrat,
narediti točno isto stvar.

172
00:08:14,600 --> 00:08:19,980
Ampak tega ne stori v
na povsem enak način.

173
00:08:19,980 --> 00:08:22,430
>> Zdaj je mogoče
imajo več kot eno bazo

174
00:08:22,430 --> 00:08:25,770
Primer ali več kot eno
rekurzivno primeru, odvisno

175
00:08:25,770 --> 00:08:27,670
na kaj vaša funkcija se poskuša narediti.

176
00:08:27,670 --> 00:08:31,650
Niste nujno omejen samo na
enotna osnova primer ali enojno rekurzivno

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

178
00:08:32,370 --> 00:08:35,320
Torej primer nečesa
z več baznih primerih

179
00:08:35,320 --> 00:08:37,830
morda this--
Fibonaccijevo zaporedje števil.

180
00:08:37,830 --> 00:08:41,549
>> Morda se boste spomnili iz
osnovne šole dni

181
00:08:41,549 --> 00:08:45,740
da je sekvenca Fibonaccijevo definirano
kot this-- prvi element je 0.

182
00:08:45,740 --> 00:08:46,890
Drugi element je 1.

183
00:08:46,890 --> 00:08:49,230
Oba sta le po definiciji.

184
00:08:49,230 --> 00:08:55,920
>> Potem je vsak drugi element je opredeljen
kot vsota n minus 1 in n minus 2.

185
00:08:55,920 --> 00:09:00,330
Torej tretjega elementa
bi 0 in 1 1.

186
00:09:00,330 --> 00:09:03,280
In nato četrti element
bi drugi element, 1,

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

188
00:09:06,550 --> 00:09:08,507
In da bi bila 2.

189
00:09:08,507 --> 00:09:09,340
In tako naprej in tako naprej.

190
00:09:09,340 --> 00:09:11,680
>> Torej, v tem primeru imamo dve osnovnih zadev.

191
00:09:11,680 --> 00:09:14,850
Če je n enak 1, vrne 0.

192
00:09:14,850 --> 00:09:18,560
Če je n enak 2, vrne 1.

193
00:09:18,560 --> 00:09:25,930
V nasprotnem primeru, se vrnite Fibonacci n
minus 1 plus Fibonaccijevo n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Torej, to je več baznih primere.

195
00:09:27,180 --> 00:09:29,271
Kaj več rekurzivnih primerih?

196
00:09:29,271 --> 00:09:31,520
No, nekaj je
imenuje Collatz ugibanje.

197
00:09:31,520 --> 00:09:34,630
Ne bom povedal,
veste, kaj to je,

198
00:09:34,630 --> 00:09:38,170
ker je dejansko naša končna
Problem pri tem videu.

199
00:09:38,170 --> 00:09:43,220
In to je naša vadba
delati skupaj.

200
00:09:43,220 --> 00:09:46,760
>> Torej, tukaj je tisto, kar
Collatz domneva is--

201
00:09:46,760 --> 00:09:48,820
to velja za vsako pozitivno celo število.

202
00:09:48,820 --> 00:09:51,500
In špekulira, da je
vedno mogoče, da bi dobili nazaj

203
00:09:51,500 --> 00:09:55,060
1, če boste sledili korakom.

204
00:09:55,060 --> 00:09:57,560
Če je n 1, ustavi.

205
00:09:57,560 --> 00:10:00,070
Dobili smo nazaj na 1, če je n 1.

206
00:10:00,070 --> 00:10:05,670
>> V nasprotnem primeru, iti skozi to
Postopek spet na n deljeno z 2.

207
00:10:05,670 --> 00:10:08,200
In videli, če lahko dobite nazaj na 1.

208
00:10:08,200 --> 00:10:13,260
V nasprotnem primeru, če je n liho, iti skozi
ta proces spet na 3N plus 1,

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

210
00:10:15,552 --> 00:10:17,010
Torej, tukaj imamo eno samo osnovno zadevo.

211
00:10:17,010 --> 00:10:18,430
Če je n enak 1, ustavi.

212
00:10:18,430 --> 00:10:20,230
Mi ne delaš nič več rekurzijo.

213
00:10:20,230 --> 00:10:23,730
>> Ampak imamo dve rekurzivne primere.

214
00:10:23,730 --> 00:10:28,750
Če je n celo, naredimo eno rekurzivno
Primer, ki pristajajo n deljeno z 2.

215
00:10:28,750 --> 00:10:33,950
Če je n liho, delamo drugačen
rekurzivni primer na 3-krat n + 1.

216
00:10:33,950 --> 00:10:39,120
>> In tako je cilj za ta video je
vzeti sekundo, pavza video,

217
00:10:39,120 --> 00:10:42,440
in poskusite napisati to
rekurzivna funkcija Collatz

218
00:10:42,440 --> 00:10:47,640
kjer se boste peljali v vrednosti n, in
izračunava koliko korakov je

219
00:10:47,640 --> 00:10:52,430
meni, da bi dobili 1, če začnete z n
in sledite tiste korake tam zgoraj.

220
00:10:52,430 --> 00:10:56,660
Če je n 1, je potrebno 0 korake.

221
00:10:56,660 --> 00:11:00,190
Sicer pa se dogaja, da
vzemite en korak plus Vendar

222
00:11:00,190 --> 00:11:06,200
veliko korakov je potrebnih, na obeh n
deliti z 2, če je n celo ali 3n plus 1

223
00:11:06,200 --> 00:11:08,100
če je n sodo.

224
00:11:08,100 --> 00:11:11,190
>> Sedaj sem dal gor na zaslonu tukaj
nekaj testnih stvari za vas,

225
00:11:11,190 --> 00:11:15,690
nekaj testov primerih za vas, da bi videli
kaj ti različni Collatz številke,

226
00:11:15,690 --> 00:11:17,440
in tudi ilustracija
od korakov, ki

227
00:11:17,440 --> 00:11:20,390
treba šla skozi, tako da lahko
nekako se ta proces v akciji.

228
00:11:20,390 --> 00:11:24,222
Torej, če je n enak
1, Collatz n je 0.

229
00:11:24,222 --> 00:11:26,180
Nimate storiti
karkoli, da bi dobili nazaj na 1.

230
00:11:26,180 --> 00:11:27,600
Ste že tam.

231
00:11:27,600 --> 00:11:30,550
>> Če je n 2, je potrebno
en korak, da pridete do 1.

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

233
00:11:31,810 --> 00:11:33,100
No, 2 ni enak 1.

234
00:11:33,100 --> 00:11:36,580
Tako se dogaja, da so en korak
plus pa veliko korakov je

235
00:11:36,580 --> 00:11:38,015
prevzame n deljeno z 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 deljeno z 2 1.

238
00:11:42,910 --> 00:11:47,200
Tako da traja en korak plus Vendar
veliko korakov je potrebno za 1.

239
00:11:47,200 --> 00:11:49,720
1 je nič korake.

240
00:11:49,720 --> 00:11:52,370
>> Za 3, kot lahko vidite, obstaja
vključenih kar nekaj korakov.

241
00:11:52,370 --> 00:11:53,590
Greš od 3.

242
00:11:53,590 --> 00:11:56,710
In potem greš na
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
To traja sedem korakov, da bi dobili nazaj na 1.

244
00:11:58,804 --> 00:12:01,220
In kot lahko vidite, obstaja
Nekaj ​​drugih testnih primerov tukaj

245
00:12:01,220 --> 00:12:02,470
preizkusiti svoj program.

246
00:12:02,470 --> 00:12:03,970
Torej še enkrat, pavza video.

247
00:12:03,970 --> 00:12:09,210
In jaz bom skočil nazaj zdaj
kaj je dejanski proces je tukaj,

248
00:12:09,210 --> 00:12:11,390
kaj je ta domneva je.

249
00:12:11,390 --> 00:12:14,140
>> Glejte, če lahko ugotovimo,
kako opredeliti Collatz n

250
00:12:14,140 --> 00:12:19,967
tako, da izračunava koliko
korakov je potrebno, da pridete do 1.

251
00:12:19,967 --> 00:12:23,050
Torej upajmo, da ste zamrznili video
in vi ste ne samo me čaka

252
00:12:23,050 --> 00:12:25,820
da vam odgovora.

253
00:12:25,820 --> 00:12:29,120
Ampak, če ste, no,
tukaj je odgovor vseeno.

254
00:12:29,120 --> 00:12:33,070
>> Torej, tukaj je možna opredelitev
funkcije Collatz.

255
00:12:33,070 --> 00:12:35,610
Naša baza case-- če je n
enaka 1, se vrnemo 0.

256
00:12:35,610 --> 00:12:38,250
To ne bo vsaka
koraki, da bi dobili nazaj na 1.

257
00:12:38,250 --> 00:12:42,710
>> Sicer pa imamo dve rekurzivni cases--
eden za celo številk in eno za sodo.

258
00:12:42,710 --> 00:12:47,164
Pot I test za celo števil
je, da preveri, če n mod 2 enak 0.

259
00:12:47,164 --> 00:12:49,080
To je v bistvu, še enkrat,
asking vprašanje,

260
00:12:49,080 --> 00:12:54,050
Če se spomnimo, kaj mod is-- če sem
razkorak n z 2 ne obstaja preostanek?

261
00:12:54,050 --> 00:12:55,470
To bi bilo sodo število.

262
00:12:55,470 --> 00:13:01,370
>> In tako, če n mod 2 enaka 0, je
Testiranje je to celo število.

263
00:13:01,370 --> 00:13:04,250
Če je tako, želim, da se vrnete 1,
ker to je definitivno

264
00:13:04,250 --> 00:13:09,270
pri čemer en korak plus Collatz od
ne glede na število je polovica mene.

265
00:13:09,270 --> 00:13:13,910
Sicer pa želim, da se vrnete 1
plus Collatz za 3-krat n plus 1.

266
00:13:13,910 --> 00:13:16,060
To je bila druga
rekurzivni korak, ki smo

267
00:13:16,060 --> 00:13:19,470
bi lahko za izračun
Collatz-- število korakov

268
00:13:19,470 --> 00:13:22,610
je potrebno, da bi dobili nazaj
do 1. dobijo številko.

269
00:13:22,610 --> 00:13:24,610
Torej, upam, da ta primer
ti je dal malo

270
00:13:24,610 --> 00:13:26,620
z okusom rekurzivnih postopkov.

271
00:13:26,620 --> 00:13:30,220
Upam, da misliš, da koda je
malo lepše, če izvajajo

272
00:13:30,220 --> 00:13:32,760
v elegantnem, rekurzivni način.

273
00:13:32,760 --> 00:13:35,955
Toda tudi če ne, rekurzija je
res močno orodje vseeno.

274
00:13:35,955 --> 00:13:38,330
In zato je definitivno nekaj
, da bi dobili svojo glavo okoli,

275
00:13:38,330 --> 00:13:41,360
saj boste lahko ustvarili
precej kul programi uporabljajo rekurzijo

276
00:13:41,360 --> 00:13:45,930
ki bi sicer zapletena, da napišete
če uporabljate zank in ponovitev.

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

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

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