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

2
00:00:05,860 --> 00:00:09,530
>> Doug LLOYD: Vi vjerojatno mislite da je
broj je samo koristiti za izvršenje zadatka.

3
00:00:09,530 --> 00:00:10,450
Možete ga napisati.

4
00:00:10,450 --> 00:00:11,664
To čini nešto.

5
00:00:11,664 --> 00:00:12,580
To je prilično zadovoljni.

6
00:00:12,580 --> 00:00:13,160
>> Možete ga sastaviti.

7
00:00:13,160 --> 00:00:13,993
Možete pokrenuti program.

8
00:00:13,993 --> 00:00:15,370
Ti si dobar to ići.

9
00:00:15,370 --> 00:00:17,520
>> No vjerovali ili ne, ako je
što kodirati za dugo vremena,

10
00:00:17,520 --> 00:00:20,550
možda zapravo došli vidjeti
broj kao nešto što je lijepo.

11
00:00:20,550 --> 00:00:23,275
Ona rješava problem u
vrlo zanimljiv način,

12
00:00:23,275 --> 00:00:26,510
ili postoji samo nešto stvarno
uredno o načinu izgleda.

13
00:00:26,510 --> 00:00:28,750
Možda se smijao
na mene, ali to je istina.

14
00:00:28,750 --> 00:00:31,530
I rekurzija je jedan od načina
na neki način dobili tu ideju

15
00:00:31,530 --> 00:00:34,090
od lijepa, elegantna izgleda koda.

16
00:00:34,090 --> 00:00:37,740
To rješava probleme na način koji
su zanimljive, lako vizualizirati,

17
00:00:37,740 --> 00:00:39,810
i iznenađujuće kratko.

18
00:00:39,810 --> 00:00:43,190
>> Način na rekurzije radovi
je, rekurzivna funkcija

19
00:00:43,190 --> 00:00:49,291
definiran kao funkcija koji poziva
sama kao dio njegova izvršenja.

20
00:00:49,291 --> 00:00:51,790
To se može činiti malo čudno,
pa ćemo vidjeti malo

21
00:00:51,790 --> 00:00:53,750
o tome kako to radi u ovom trenutku.

22
00:00:53,750 --> 00:00:55,560
Ali opet, to
rekurzivni postupci

23
00:00:55,560 --> 00:00:57,730
će biti tako elegantna
jer oni će

24
00:00:57,730 --> 00:01:00,410
riješiti ovaj problem bez
ima sve te ostale funkcije

25
00:01:00,410 --> 00:01:02,710
ili ove duge petlje.

26
00:01:02,710 --> 00:01:06,310
Vidjet ćete da su to rekurzivna
Postupci će izgledati tako kratko.

27
00:01:06,310 --> 00:01:10,610
I doista su idući u izraditi
Vaš broj izgleda puno ljepše.

28
00:01:10,610 --> 00:01:12,560
>> Dat ću vam jedan primjer
to vidjeti kako

29
00:01:12,560 --> 00:01:14,880
rekurzivna procedura mogla biti definirana.

30
00:01:14,880 --> 00:01:18,202
Dakle, ako ste upoznati s ovim
iz matematike klase prije mnogo godina,

31
00:01:18,202 --> 00:01:20,910
Ima nešto zove
faktorijalni funkcija, što je obično

32
00:01:20,910 --> 00:01:25,340
označen kao uskličnik, koji
definira se preko svih pozitivnih integers.

33
00:01:25,340 --> 00:01:28,850
A način na koji je n
faktorijalni izračunava

34
00:01:28,850 --> 00:01:31,050
je li pomnožiti sve
brojeve manje od

35
00:01:31,050 --> 00:01:33,750
ili jednaka n together--
svi cijeli brojevi manje od

36
00:01:33,750 --> 00:01:34,880
ili jednak N zajedno.

37
00:01:34,880 --> 00:01:39,850
>> Dakle 5 faktorijalni je 5 puta
4 puta 3 puta 2 puta 1.

38
00:01:39,850 --> 00:01:43,020
A 4 faktorijalni je 4 puta
3 puta 2 puta 1 i tako dalje.

39
00:01:43,020 --> 00:01:44,800
Vi dobijete ideju.

40
00:01:44,800 --> 00:01:47,060
>> Kao programera, mi ne
koristiti N, uskličnik.

41
00:01:47,060 --> 00:01:51,840
Tako ćemo definirati faktorski
djeluju kao činjenicu n.

42
00:01:51,840 --> 00:01:56,897
A mi ćemo koristiti faktorijel stvoriti
rekurzivna rješenje problema.

43
00:01:56,897 --> 00:01:59,230
I mislim da bi mogli naći
da je puno više vizualno

44
00:01:59,230 --> 00:02:02,380
atraktivan nego iterativni
Verzija za to, što

45
00:02:02,380 --> 00:02:05,010
ćemo također uzeti pogledati u trenutku.

46
00:02:05,010 --> 00:02:08,310
>> Dakle ovdje su par
facts-- dosjetka intended--

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

48
00:02:10,169 --> 00:02:13,090
Faktorijel 1, kao što sam rekao, je 1.

49
00:02:13,090 --> 00:02:15,690
Faktorijel 2 je 2 puta 1.

50
00:02:15,690 --> 00:02:18,470
Faktorijel 3 je 3
puta 2 puta 1, i tako dalje.

51
00:02:18,470 --> 00:02:20,810
Razgovarali smo o 4 i 5 već.

52
00:02:20,810 --> 00:02:23,940
>> No, gledajući to, nije li to istina?

53
00:02:23,940 --> 00:02:28,220
Nije faktorijel 2 samo
2 puta faktorijel 1?

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

55
00:02:31,130 --> 00:02:34,940
Pa zašto ne možemo samo reći da je,
budući faktorijalni 2 je 2 puta 1,

56
00:02:34,940 --> 00:02:38,520
To je zapravo samo 2 puta
faktorijel od 1?

57
00:02:38,520 --> 00:02:40,900
>> A onda se širi tu ideju,
nije faktorski 3

58
00:02:40,900 --> 00:02:44,080
samo 3 puta faktorijel 2?

59
00:02:44,080 --> 00:02:50,350
A faktorijalni 4 je 4 puta
faktorijel 3, i tako dalje?

60
00:02:50,350 --> 00:02:52,530
U stvari, faktorijalni
bilo koji broj mogu jednostavno

61
00:02:52,530 --> 00:02:54,660
biti izražena, ako smo vrsta
od nose ovo zauvijek.

62
00:02:54,660 --> 00:02:56,870
Možemo vrsta generalizirati
faktorijel problema

63
00:02:56,870 --> 00:02:59,910
kao što je n puta
faktorijalni n minus 1.

64
00:02:59,910 --> 00:03:04,840
To je n puta proizvod
sve brojeve manje od mene.

65
00:03:04,840 --> 00:03:08,890
>> Ova ideja, ova
generalizacija problema,

66
00:03:08,890 --> 00:03:13,410
omogućuje nam da rekurzivno
definirati faktorsku funkciju.

67
00:03:13,410 --> 00:03:15,440
Kada definirate funkciju
rekurzivno, postoji

68
00:03:15,440 --> 00:03:17,470
dvije stvari koje trebaju biti dio toga.

69
00:03:17,470 --> 00:03:20,990
Morate imati nešto što se zove
osnovni scenarij, koji, kada ga aktiviraju,

70
00:03:20,990 --> 00:03:22,480
će zaustaviti rekurzivni postupak.

71
00:03:22,480 --> 00:03:25,300
>> Inače, funkcija koja poziva
itself-- kao što ste mogli imagine--

72
00:03:25,300 --> 00:03:26,870
mogao ići na zauvijek.

73
00:03:26,870 --> 00:03:29,047
Funkcija poziva funkciju
poziva funkcijske pozive

74
00:03:29,047 --> 00:03:30,380
funkcija poziva funkcije.

75
00:03:30,380 --> 00:03:32,380
Ako nemate način
kako ga zaustaviti, vaš program

76
00:03:32,380 --> 00:03:34,760
će biti učinkovito zaglavio
u beskonačnu petlju.

77
00:03:34,760 --> 00:03:37,176
To će se sudariti s vremenom,
jer će ponestati memorije.

78
00:03:37,176 --> 00:03:38,990
Ali to je uz točku.

79
00:03:38,990 --> 00:03:42,210
>> Moramo imati neki drugi način da se zaustavi
stvari osim našeg programa pad sustava,

80
00:03:42,210 --> 00:03:46,010
jer program koji ruši se
vjerojatno nije lijepa ili elegantne.

81
00:03:46,010 --> 00:03:47,690
I tako mi to nazivamo osnovnom scenariju.

82
00:03:47,690 --> 00:03:50,610
To je jednostavno rješenje
na problem koji zaustavlja

83
00:03:50,610 --> 00:03:52,770
rekurzivna proces iz pojavio.

84
00:03:52,770 --> 00:03:55,220
Dakle, to je jedan dio
rekurzivna funkcija.

85
00:03:55,220 --> 00:03:56,820
>> Drugi dio je rekurzivna slučaj.

86
00:03:56,820 --> 00:03:59,195
I ovo je mjesto gdje se rekurzija
zaista i dogoditi.

87
00:03:59,195 --> 00:04:02,200
Ovo je mjesto gdje
Funkcija će se zvati.

88
00:04:02,200 --> 00:04:05,940
>> Neće se pozvati na točno
isti način na koji je bio pozvan.

89
00:04:05,940 --> 00:04:08,880
To će biti neznatno varijacije
koji čini problem je to

90
00:04:08,880 --> 00:04:11,497
pokušava riješiti teeny malo manji.

91
00:04:11,497 --> 00:04:14,330
Ali to uglavnom prolazi mužjak
rješavanja većinu rješenja

92
00:04:14,330 --> 00:04:17,450
na drugi poziv niz liniju.

93
00:04:17,450 --> 00:04:20,290
>> Koji od ovih pogleda
kao osnovnog ovdje slučaj?

94
00:04:20,290 --> 00:04:25,384
Koji od tih izgleda kao
Najjednostavnije rješenje problema?

95
00:04:25,384 --> 00:04:27,550
Imamo hrpu factorials,
a mi mogao nastaviti

96
00:04:27,550 --> 00:04:30,470
ide on-- 6, 7, 8, 9, 10, i tako dalje.

97
00:04:30,470 --> 00:04:34,130
>> No, jedan od tih izgleda kao
dobar slučaj da je osnovni scenarij.

98
00:04:34,130 --> 00:04:35,310
To je vrlo jednostavno rješenje.

99
00:04:35,310 --> 00:04:37,810
Ne morate učiniti ništa posebno.

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

101
00:04:40,560 --> 00:04:42,790
Ne morate učiniti bilo
množenja uopće.

102
00:04:42,790 --> 00:04:45,248
Čini se kao da ćemo
pokušati riješiti ovaj problem,

103
00:04:45,248 --> 00:04:47,600
i moramo zaustaviti
rekurzije negdje,

104
00:04:47,600 --> 00:04:50,610
smo vjerojatno želite da se zaustavi
da kad dođemo do 1.

105
00:04:50,610 --> 00:04:54,580
Mi ne želimo zaustaviti prije toga.

106
00:04:54,580 --> 00:04:56,660
>> Dakle, ako smo definiranja
naš faktorijalni funkcija,

107
00:04:56,660 --> 00:04:58,690
ovdje je kostur za
Kako bismo mogli to učiniti.

108
00:04:58,690 --> 00:05:03,110
Moramo uključiti u te dvije things--
osnovni slučaj i rekurzivni slučaj.

109
00:05:03,110 --> 00:05:04,990
Što je osnovni scenarij?

110
00:05:04,990 --> 00:05:10,150
Ako je n jednak 1, povratak 1-- to
stvarno jednostavan problem riješiti.

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

112
00:05:11,890 --> 00:05:13,860
To nije 1 puta ništa.

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

114
00:05:15,020 --> 00:05:17,170
To je vrlo jednostavno činjenica.

115
00:05:17,170 --> 00:05:19,620
I tako to može biti naša baza slučaj.

116
00:05:19,620 --> 00:05:24,730
Ako biste smo prošli 1 u ovo
funkcija, samo ćemo se vratiti 1.

117
00:05:24,730 --> 00:05:27,320
>> Što je rekurzivna
Slučaj je vjerojatno izgledati?

118
00:05:27,320 --> 00:05:32,445
Za svaki drugi broj
osim 1, što je uzorak?

119
00:05:32,445 --> 00:05:35,780
Pa, ako ćemo uzimati
faktorijel n,

120
00:05:35,780 --> 00:05:38,160
to je n puta faktorijalni n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Ako nas da faktorijel 3,
to je 3 puta faktorijalni 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
I tako, ako nismo
gleda na 1, inače

124
00:05:47,330 --> 00:05:51,710
Povratak n puta
faktorijalni n minus 1.

125
00:05:51,710 --> 00:05:53,210
To je prilično jednostavan.

126
00:05:53,210 --> 00:05:57,360
>> A radi ima malo
čišći i elegantniji broj,

127
00:05:57,360 --> 00:06:01,440
znam da ako imamo jednog retka petlje
ili jednog retka uvjetna grana,

128
00:06:01,440 --> 00:06:04,490
možemo riješiti sve od
vitičastih zagrada oko njih.

129
00:06:04,490 --> 00:06:06,850
Tako možemo objediniti to to.

130
00:06:06,850 --> 00:06:09,640
To je točno isti
funkcionalnost kao ovaj.

131
00:06:09,640 --> 00:06:13,850
>> Samo oduzimanje kovrčavu
aparatić, jer postoji samo jedan redak

132
00:06:13,850 --> 00:06:18,500
unutar tih uvjetnih grana.

133
00:06:18,500 --> 00:06:21,160
Dakle, to se ponašaju identično.

134
00:06:21,160 --> 00:06:23,800
Ako je n jednak 1, povratak 1.

135
00:06:23,800 --> 00:06:28,351
Inače vratiti n puta
faktorijel n minus 1.

136
00:06:28,351 --> 00:06:29,850
Tako činimo problem manji.

137
00:06:29,850 --> 00:06:33,850
Ako je n počinje kao 5, idemo
vratiti 5 puta faktorijel 4.

138
00:06:33,850 --> 00:06:37,100
A vidjet ćemo za minutu, kada govorimo
o stack-- poziva u drugom videu

139
00:06:37,100 --> 00:06:39,390
gdje smo razgovarati o
pozvati stack-- ćemo naučiti

140
00:06:39,390 --> 00:06:41,630
o tome zašto upravo taj proces funkcionira.

141
00:06:41,630 --> 00:06:46,970
>> No, dok faktorijalni 5 kaže
vratiti 5 puta faktorijalni 4 i 4

142
00:06:46,970 --> 00:06:49,710
će reći, u redu, dobro, povratak
4 puta faktorijel 3.

143
00:06:49,710 --> 00:06:51,737
I kao što možete vidjeti, mi smo
vrsta približava 1.

144
00:06:51,737 --> 00:06:53,820
Mi smo sve bliže i
bliže tom osnovnom scenariju.

145
00:06:53,820 --> 00:06:58,180
>> A kad smo hit bazu slučaj,
svim prethodnim funkcija

146
00:06:58,180 --> 00:07:00,540
imaju odgovor su tražili.

147
00:07:00,540 --> 00:07:03,900
Faktorijalni 2 je govorio povratak
2 puta faktorijel od 1.

148
00:07:03,900 --> 00:07:06,760
Pa, faktorijel 1 vraća 1.

149
00:07:06,760 --> 00:07:10,090
Tako je poziv za faktorski
2 može vratiti 2 puta 1,

150
00:07:10,090 --> 00:07:13,980
i dati da leđa faktorijel
3, koji je čeka za taj rezultat.

151
00:07:13,980 --> 00:07:17,110
>> I onda se može izračunati
njegov rezultat, 3 puta 2 je 6,

152
00:07:17,110 --> 00:07:18,907
i dati ga natrag faktorijel 4.

153
00:07:18,907 --> 00:07:20,740
I opet, imamo
Video na stogu poziva

154
00:07:20,740 --> 00:07:23,810
ako je to ilustrirano malo
više nego što govorim sada.

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

156
00:07:25,300 --> 00:07:29,300
To samo po sebi je rješenje za
izračunavanje faktorijel broja.

157
00:07:29,300 --> 00:07:31,527
>> To je samo četiri linije koda.

158
00:07:31,527 --> 00:07:32,610
To je prilično cool, zar ne?

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

160
00:07:35,480 --> 00:07:38,580
>> Tako je u cjelini, ali ne
Uvijek, rekurzivna funkcija

161
00:07:38,580 --> 00:07:41,190
može zamijeniti petlju se u
nerekurzivni funkcija.

162
00:07:41,190 --> 00:07:46,100
Dakle ovdje, rame uz rame, je iterativan
verzija faktorska funkcije.

163
00:07:46,100 --> 00:07:49,650
Obje od tih izračunati
upravo ista stvar.

164
00:07:49,650 --> 00:07:52,170
>> Obojica su izračunali faktorijel n.

165
00:07:52,170 --> 00:07:54,990
Verzija lijevo
koristi rekurzija za to.

166
00:07:54,990 --> 00:07:58,320
Verzija desno
koristi iteracija za to.

167
00:07:58,320 --> 00:08:02,050
>> I napomena, moramo proglasiti
varijabla cijeli proizvod.

168
00:08:02,050 --> 00:08:02,940
A onda smo petlje.

169
00:08:02,940 --> 00:08:06,790
Tako dugo dok je n veći od 0,
zadržati množenjem taj proizvod po n

170
00:08:06,790 --> 00:08:09,890
i decrementing n do
možemo izračunati proizvod.

171
00:08:09,890 --> 00:08:14,600
Dakle, ove dvije funkcije, opet,
učiniti istu stvar.

172
00:08:14,600 --> 00:08:19,980
Ali oni ne to učiniti u
točno na isti način.

173
00:08:19,980 --> 00:08:22,430
>> Sada je moguće
imaju više od jedne baze

174
00:08:22,430 --> 00:08:25,770
Slučaj ili više
rekurzivni slučaj, ovisno

175
00:08:25,770 --> 00:08:27,670
na što vaš funkcija pokušava učiniti.

176
00:08:27,670 --> 00:08:31,650
Vi ne nužno samo ograničeni na
jedan osnovni scenarij ili jedan rekurzivna

177
00:08:31,650 --> 00:08:32,370
slučaj.

178
00:08:32,370 --> 00:08:35,320
Dakle, primjer nečega
s više slučajeva baznih

179
00:08:35,320 --> 00:08:37,830
možda this--
Fibonacci nizu broj.

180
00:08:37,830 --> 00:08:41,549
>> Vi svibanj podsjetiti iz
osnovnoškolci dana

181
00:08:41,549 --> 00:08:45,740
da je Fibonacci slijed definiran
kao 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
Oboje su to samo po definiciji.

184
00:08:49,230 --> 00:08:55,920
>> Zatim svaki drugi element koji definira
kao zbroj n i n minus 1 minus 2.

185
00:08:55,920 --> 00:09:00,330
Tako trećeg elementa
će biti 0 i 1 je 1.

186
00:09:00,330 --> 00:09:03,280
A onda Četvrti element
bi drugi element, 1,

187
00:09:03,280 --> 00:09:06,550
plus treći element, 1.

188
00:09:06,550 --> 00:09:08,507
I to bi bilo 2.

189
00:09:08,507 --> 00:09:09,340
I tako dalje i tako dalje.

190
00:09:09,340 --> 00:09:11,680
>> Dakle, u ovom slučaju, imamo dvije bazne slučajeve.

191
00:09:11,680 --> 00:09:14,850
Ako je n jednak 1, povratak 0.

192
00:09:14,850 --> 00:09:18,560
Ako je n jednak 2, povratak 1.

193
00:09:18,560 --> 00:09:25,930
Inače, povratak Fibonacci n
minus 1 plus Fibonacci n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Dakle, to je više slučajeva baze.

195
00:09:27,180 --> 00:09:29,271
Što je više rekurzivnih slučajevima?

196
00:09:29,271 --> 00:09:31,520
Pa, ima nešto
zove Collatz nagađanje.

197
00:09:31,520 --> 00:09:34,630
Neću reći,
znate što je to,

198
00:09:34,630 --> 00:09:38,170
jer to je zapravo naš konačni
Problem za ovaj video.

199
00:09:38,170 --> 00:09:43,220
I to je naša vježbe
raditi na zajedno.

200
00:09:43,220 --> 00:09:46,760
>> Dakle, ovdje je ono što je
Collatz nagađanje is--

201
00:09:46,760 --> 00:09:48,820
to se odnosi na sve pozitivni cijeli broj.

202
00:09:48,820 --> 00:09:51,500
I to pretpostavlja da je
Uvijek je moguće vratiti

203
00:09:51,500 --> 00:09:55,060
na 1 ako slijedite ove korake.

204
00:09:55,060 --> 00:09:57,560
Ako n predstavlja 1, zaustavi.

205
00:09:57,560 --> 00:10:00,070
Moramo vratiti na 1 ako je n 1.

206
00:10:00,070 --> 00:10:05,670
>> Inače, proći kroz ova
Proces opet na n podijeljena 2.

207
00:10:05,670 --> 00:10:08,200
I vidjeti ako možete dobiti natrag na 1.

208
00:10:08,200 --> 00:10:13,260
Inače, ako je n neparan, proći kroz
taj proces opet na 3N plus 1,

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

210
00:10:15,552 --> 00:10:17,010
Dakle, ovdje imamo jedan osnovni slučaj.

211
00:10:17,010 --> 00:10:18,430
Ako je n jednak 1, zaustavi.

212
00:10:18,430 --> 00:10:20,230
Mi ne radite bilo više rekurzija.

213
00:10:20,230 --> 00:10:23,730
>> No, imamo dva rekurzivni slučajeva.

214
00:10:23,730 --> 00:10:28,750
Ako je n čak, mi radimo jedan Rekurzivno
Slučaj, pozivajući n podijeljena 2.

215
00:10:28,750 --> 00:10:33,950
Ako je n neparan, mi drugačiji
rekurzivna slučaj na 3 puta n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> I tako je cilj za ovu videu
uzeti sekundu, pauziranje videozapisa,

217
00:10:39,120 --> 00:10:42,440
i pokušati ovo napisati
rekurzivna funkcija Collatz

218
00:10:42,440 --> 00:10:47,640
gdje prolaze u vrijednosti n, te
izračunava koliko ih koraka

219
00:10:47,640 --> 00:10:52,430
potrebno da biste dobili na 1 ako počnete od n
i slijedite one korake iznad.

220
00:10:52,430 --> 00:10:56,660
Ako n predstavlja 1, potrebno je 0 koraka.

221
00:10:56,660 --> 00:11:00,190
Inače, to će
uzeti jedan korak plus međutim

222
00:11:00,190 --> 00:11:06,200
mnogo koraka da preuzima bilo n
podijeljeno s 2 ako je n čak, ili 3n plus 1

223
00:11:06,200 --> 00:11:08,100
ako je n neparan.

224
00:11:08,100 --> 00:11:11,190
>> Sada sam stavio gore na zaslonu ovdje
par ispitnih stvari za vas,

225
00:11:11,190 --> 00:11:15,690
par testova predmeta za vas, vidjeti
što ti razni Collatz brojevi,

226
00:11:15,690 --> 00:11:17,440
i ilustracija
od koraka koje

227
00:11:17,440 --> 00:11:20,390
treba proći kroz tako da možete
vidjeti kakve taj proces u akciji.

228
00:11:20,390 --> 00:11:24,222
Dakle, ako je n jednak
1, Collatz n je 0.

229
00:11:24,222 --> 00:11:26,180
Vi ne morate učiniti
ništa se vratiti do 1.

230
00:11:26,180 --> 00:11:27,600
Ti si već tamo.

231
00:11:27,600 --> 00:11:30,550
>> Ako je n 2, potrebno
jedan korak da se na 1.

232
00:11:30,550 --> 00:11:31,810
Možete početi s 2.

233
00:11:31,810 --> 00:11:33,100
Pa, 2 nije jednak 1.

234
00:11:33,100 --> 00:11:36,580
Dakle, to će biti jedan korak
plus no mnogi ga koraka

235
00:11:36,580 --> 00:11:38,015
poprima n podijeljena 2.

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

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

238
00:11:42,910 --> 00:11:47,200
Dakle, to traje jedan korak plus međutim
mnogo koraka koje je potrebno za 1.

239
00:11:47,200 --> 00:11:49,720
1 traje nula korake.

240
00:11:49,720 --> 00:11:52,370
>> Za 3, kao što možete vidjeti, postoji
dosta koraka koji su uključeni.

241
00:11:52,370 --> 00:11:53,590
Možete ići od 3.

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

243
00:11:56,710 --> 00:11:58,804
Potrebno je sedam koraka za povratak na 1.

244
00:11:58,804 --> 00:12:01,220
I kao što možete vidjeti, postoji
Par drugi test slučajevi ovdje

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

246
00:12:02,470 --> 00:12:03,970
Pa opet, pauziranje videozapisa.

247
00:12:03,970 --> 00:12:09,210
A ja ću skočiti natrag sada
što je stvarni proces je ovdje,

248
00:12:09,210 --> 00:12:11,390
što je to pretpostavka je.

249
00:12:11,390 --> 00:12:14,140
>> Pogledajte ako možete shvatiti
kako definirati Collatz n

250
00:12:14,140 --> 00:12:19,967
tako da se izračunava koliko
korake koje je potrebno da se na 1.

251
00:12:19,967 --> 00:12:23,050
Pa nadajmo se, da ste zastao video
a ne samo me čeka

252
00:12:23,050 --> 00:12:25,820
vam dati odgovor.

253
00:12:25,820 --> 00:12:29,120
Ali, ako ste, dobro,
Ovdje je odgovor svejedno.

254
00:12:29,120 --> 00:12:33,070
>> Dakle, ovdje je moguće definicija
funkcije Collatz.

255
00:12:33,070 --> 00:12:35,610
Naša baza case-- ako je n
jednaki 1, vraćamo 0.

256
00:12:35,610 --> 00:12:38,250
To ne uzeti bilo
koraci da se vratim na 1.

257
00:12:38,250 --> 00:12:42,710
>> Inače, imamo dva rekurzivni cases--
jedan za parnih brojeva i jedan za ak.

258
00:12:42,710 --> 00:12:47,164
Način na koji sam testirati čak i brojeva
je provjeriti ako je n mod 2 jednaka 0.

259
00:12:47,164 --> 00:12:49,080
To je u osnovi, opet,
postavlja pitanje,

260
00:12:49,080 --> 00:12:54,050
ako sjetiti što mod is-- ako
podijeli N 2 je nema ostatak?

261
00:12:54,050 --> 00:12:55,470
To bi bio paran broj.

262
00:12:55,470 --> 00:13:01,370
>> I tako, ako je n mod 2 jednaka 0 je
Ispitivanje je to paran broj.

263
00:13:01,370 --> 00:13:04,250
Ako je tako, želim se vratiti 1,
jer ovo je svakako

264
00:13:04,250 --> 00:13:09,270
uzimanje jedan korak plus Collatz od
bez obzira na broj je polovica mene.

265
00:13:09,270 --> 00:13:13,910
Inače, želim se vratiti 1
plus Collatz od 3 puta n plus 1.

266
00:13:13,910 --> 00:13:16,060
To je bio drugi
rekurzivna korak koji smo

267
00:13:16,060 --> 00:13:19,470
mogao uzeti za izračun
Collatz-- broj koraka

268
00:13:19,470 --> 00:13:22,610
je potrebno da se vrati
na 1 daje broj.

269
00:13:22,610 --> 00:13:24,610
Dakle, nadamo se, ovaj primjer
dao malo

270
00:13:24,610 --> 00:13:26,620
od okusom rekurzivnih postupaka.

271
00:13:26,620 --> 00:13:30,220
Nadam se, mislite broj je
malo ljepše ako se provodi

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

273
00:13:32,760 --> 00:13:35,955
No, čak i ako nije, rekurzija je
stvarno moćan alat svejedno.

274
00:13:35,955 --> 00:13:38,330
I to je definitivno nešto
dobiti svoju glavu okolo,

275
00:13:38,330 --> 00:13:41,360
jer ćete biti u stanju stvoriti
prilično kul programi koriste rekurzija

276
00:13:41,360 --> 00:13:45,930
koji bi inače biti složen pisati
ako koristite petlje i iteracija.

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

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

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