1
00:00:00,000 --> 00:00:05,860
>> [MUSIC JOC]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Probabil Crezi că
cod este folosit doar pentru a realiza o sarcină.

3
00:00:09,530 --> 00:00:10,450
Ai scrie.

4
00:00:10,450 --> 00:00:11,664
Ea face ceva.

5
00:00:11,664 --> 00:00:12,580
Asta e destul de mult.

6
00:00:12,580 --> 00:00:13,160
>> Ai compilați.

7
00:00:13,160 --> 00:00:13,993
Rulați programul.

8
00:00:13,993 --> 00:00:15,370
Tu esti bine să plec.

9
00:00:15,370 --> 00:00:17,520
>> Dar crezi sau nu, în cazul în care
vă codul de mult timp,

10
00:00:17,520 --> 00:00:20,550
de fapt, s-ar putea veni tu pentru a vedea
cod ca ceva care este frumos.

11
00:00:20,550 --> 00:00:23,275
Se rezolvă o problemă în
un mod foarte interesant,

12
00:00:23,275 --> 00:00:26,510
sau e doar ceva cu adevărat
elegant despre felul in care arata.

13
00:00:26,510 --> 00:00:28,750
S-ar putea râde
la mine, dar e adevărat.

14
00:00:28,750 --> 00:00:31,530
Și recursivitate este o modalitate
la fel de a obține această idee

15
00:00:31,530 --> 00:00:34,090
Codul de frumos, elegant cu aspect.

16
00:00:34,090 --> 00:00:37,740
Se rezolvă problemele în moduri care
sunt interesante, ușor de vizualizat,

17
00:00:37,740 --> 00:00:39,810
și surprinzător de scurt.

18
00:00:39,810 --> 00:00:43,190
>> Lucrările mod recursivitate
este, o funcție recursivă

19
00:00:43,190 --> 00:00:49,291
este definit ca o funcție care solicită
se ca parte a executării sale.

20
00:00:49,291 --> 00:00:51,790
Care ar putea părea un pic ciudat,
si vom vedea un pic

21
00:00:51,790 --> 00:00:53,750
despre modul în care funcționează într-o clipă.

22
00:00:53,750 --> 00:00:55,560
Dar, din nou, acestea
Procedurile sunt recursive

23
00:00:55,560 --> 00:00:57,730
O să fie atât de elegant
pentru că ei vor

24
00:00:57,730 --> 00:01:00,410
pentru a rezolva această problemă, fără
având toate aceste alte funcții

25
00:01:00,410 --> 00:01:02,710
sau aceste bucle lungi.

26
00:01:02,710 --> 00:01:06,310
Veți vedea că aceste recursive
Procedurile vor arata atat de scurt.

27
00:01:06,310 --> 00:01:10,610
Și ei cu adevărat de gând să facă
codul arata mult mai frumos.

28
00:01:10,610 --> 00:01:12,560
>> Am să vă dau un exemplu
de această pentru a vedea cum

29
00:01:12,560 --> 00:01:14,880
o procedură recursivă poate fi definit.

30
00:01:14,880 --> 00:01:18,202
Deci, dacă sunteți familiarizați cu această
de la ora de matematică mulți ani în urmă,

31
00:01:18,202 --> 00:01:20,910
E ceva numit
Funcția factorială, care este de obicei

32
00:01:20,910 --> 00:01:25,340
notat ca un semn de exclamare, care
este definită peste toate numere întregi pozitive.

33
00:01:25,340 --> 00:01:28,850
Și modul în care n
factorial este calculat

34
00:01:28,850 --> 00:01:31,050
este vă înmulțiți toate
numerele mai puțin

35
00:01:31,050 --> 00:01:33,750
sau egal cu n together--
toate numerele întregi mai puțin decât

36
00:01:33,750 --> 00:01:34,880
sau egală cu n împreună.

37
00:01:34,880 --> 00:01:39,850
>> Deci 5 factorial este de 5 ori
4 ori 3 ori 2 ori 1.

38
00:01:39,850 --> 00:01:43,020
Și 4 factorial este de 4 ori
De 3 ori 2 ori 1 și așa mai departe.

39
00:01:43,020 --> 00:01:44,800
Ai idee.

40
00:01:44,800 --> 00:01:47,060
>> Ca programatori, nu avem
utiliza n, semn de exclamare.

41
00:01:47,060 --> 00:01:51,840
Deci, vom defini factorialului
funcționează ca fapt de n.

42
00:01:51,840 --> 00:01:56,897
Și vom folosi pentru a crea factorial
o soluție recursivă a unei probleme.

43
00:01:56,897 --> 00:01:59,230
Și cred că ar putea găsi
că este mult mai vizual

44
00:01:59,230 --> 00:02:02,380
atrăgătoare decât iterativ
versiune a acestui, care

45
00:02:02,380 --> 00:02:05,010
vom lua de asemenea, o privire la într-o clipă.

46
00:02:05,010 --> 00:02:08,310
>> Deci, aici sunt un cuplu de
joc de cuvinte facts-- intended--

47
00:02:08,310 --> 00:02:10,169
despre factorial--
Funcția factorial.

48
00:02:10,169 --> 00:02:13,090
Factorialul 1, așa cum am spus, este o.

49
00:02:13,090 --> 00:02:15,690
Factorialul 2 este de 2 ori 1.

50
00:02:15,690 --> 00:02:18,470
Factorialul 3 este 3
ori de 2 ori 1, și așa mai departe.

51
00:02:18,470 --> 00:02:20,810
Am vorbit despre 4 și 5 deja.

52
00:02:20,810 --> 00:02:23,940
>> Dar uita la asta, nu e adevărat?

53
00:02:23,940 --> 00:02:28,220
Nu este factorială a 2 doar
2 ori factorial de 1?

54
00:02:28,220 --> 00:02:31,130
Adică, factorialul 1 este de 1.

55
00:02:31,130 --> 00:02:34,940
Deci, de ce nu putem spune doar că,
deoarece factorial de 2 este de 2 ori 1,

56
00:02:34,940 --> 00:02:38,520
este într-adevăr doar de 2 ori
factorialul 1?

57
00:02:38,520 --> 00:02:40,900
>> Și apoi se extinde această idee,
nu este factorialul 3

58
00:02:40,900 --> 00:02:44,080
doar de 3 ori factorial de 2?

59
00:02:44,080 --> 00:02:50,350
Și factorialul 4 este de 4 ori
factorialul 3, și așa mai departe?

60
00:02:50,350 --> 00:02:52,530
De fapt, factorialul
de orice număr poate doar

61
00:02:52,530 --> 00:02:54,660
fi exprimată dacă ne-am cam
a efectua acest lucru pentru totdeauna.

62
00:02:54,660 --> 00:02:56,870
Putem fel de generaliza
problema factorial

63
00:02:56,870 --> 00:02:59,910
ca este de n ori
factorial de n minus 1.

64
00:02:59,910 --> 00:03:04,840
Este n ori produsul de
toate numerele mai mici decât mine.

65
00:03:04,840 --> 00:03:08,890
>> Această idee, aceasta
generalizare a problemei,

66
00:03:08,890 --> 00:03:13,410
ne permite să recursiv
defini funcția factorial.

67
00:03:13,410 --> 00:03:15,440
Când definiți o funcție
recursiv, nu e

68
00:03:15,440 --> 00:03:17,470
două lucruri care trebuie să fie o parte din ea.

69
00:03:17,470 --> 00:03:20,990
Ai nevoie de ceva numit un
cazul de bază, care, atunci când îl declanșa,

70
00:03:20,990 --> 00:03:22,480
va opri procesul recursiv.

71
00:03:22,480 --> 00:03:25,300
>> În caz contrar, o funcție care solicită
itself-- ca s-ar putea imagine--

72
00:03:25,300 --> 00:03:26,870
ar putea continua la nesfârșit.

73
00:03:26,870 --> 00:03:29,047
Funcția apelează funcția
solicită apelurile de funcții

74
00:03:29,047 --> 00:03:30,380
funcția apelează funcția.

75
00:03:30,380 --> 00:03:32,380
Dacă nu aveți un mod
să-l oprească, programul

76
00:03:32,380 --> 00:03:34,760
va fi blocat în mod eficient
la o buclă infinită.

77
00:03:34,760 --> 00:03:37,176
Acesta se va prăbuși în cele din urmă,
deoarece acesta va alerga afară de memorie.

78
00:03:37,176 --> 00:03:38,990
Dar asta e pe langa punctul de.

79
00:03:38,990 --> 00:03:42,210
>> Avem nevoie de un alt mod de a opri
lucruri în afară de crashing programul nostru,

80
00:03:42,210 --> 00:03:46,010
deoarece un program care blochează este
probabil, nu frumos sau elegant.

81
00:03:46,010 --> 00:03:47,690
Și astfel noi numim acest caz de bază.

82
00:03:47,690 --> 00:03:50,610
Aceasta este o soluție simplă
la o problemă care se oprește

83
00:03:50,610 --> 00:03:52,770
procesul recursiv de la care apar.

84
00:03:52,770 --> 00:03:55,220
Deci asta este o parte din
o funcție recursivă.

85
00:03:55,220 --> 00:03:56,820
>> A doua parte este cazul recursiv.

86
00:03:56,820 --> 00:03:59,195
Și acest lucru este în cazul în care recursivitate
va avea loc de fapt.

87
00:03:59,195 --> 00:04:02,200
Acest lucru este în cazul în care
Funcția se va apela.

88
00:04:02,200 --> 00:04:05,940
>> Ea nu se va apela în exact
la fel a fost numit.

89
00:04:05,940 --> 00:04:08,880
Va fi o ușoară variație
care face problema este

90
00:04:08,880 --> 00:04:11,497
încearcă să rezolve un pic teeny mici.

91
00:04:11,497 --> 00:04:14,330
Dar, în general, trece dolar
de rezolvare cea mai mare parte a soluției

92
00:04:14,330 --> 00:04:17,450
la un apel diferit pe linie.

93
00:04:17,450 --> 00:04:20,290
>> Care dintre aceste priviri
cum ar fi cazul de bază aici?

94
00:04:20,290 --> 00:04:25,384
Care dintre aceste arata ca
simplă soluție la o problemă?

95
00:04:25,384 --> 00:04:27,550
Avem o grămadă de factorialele,
și am putea continua

96
00:04:27,550 --> 00:04:30,470
merge on-- 6, 7, 8, 9, 10, și așa mai departe.

97
00:04:30,470 --> 00:04:34,130
>> Dar unul dintre aceste arata ca un
caz bun pentru a fi cazul de bază.

98
00:04:34,130 --> 00:04:35,310
Este o soluție foarte simplă.

99
00:04:35,310 --> 00:04:37,810
Noi nu trebuie să facem nimic special.

100
00:04:37,810 --> 00:04:40,560
>> Factorialul 1 este la doar 1.

101
00:04:40,560 --> 00:04:42,790
Noi nu trebuie să facem nici un
multiplicare, la toate.

102
00:04:42,790 --> 00:04:45,248
Se pare că, dacă vrem
pentru a încerca și de a rezolva această problemă,

103
00:04:45,248 --> 00:04:47,600
si avem nevoie pentru a opri
recursivitate undeva,

104
00:04:47,600 --> 00:04:50,610
probabil că doriți să opriți
aceasta când vom ajunge la 1.

105
00:04:50,610 --> 00:04:54,580
Noi nu vrem să se oprească înainte de asta.

106
00:04:54,580 --> 00:04:56,660
>> Deci, dacă suntem definirea
Funcția noastră factorial,

107
00:04:56,660 --> 00:04:58,690
aici e un schelet de
cum am putea face asta.

108
00:04:58,690 --> 00:05:03,110
Avem nevoie să conectați în cele două lucruri--
cazul de bază și în cazul recursiv.

109
00:05:03,110 --> 00:05:04,990
Care e cazul de bază?

110
00:05:04,990 --> 00:05:10,150
Dacă n este egal cu 1, se întoarcă 1-- e
o problemă foarte simplu de rezolvat.

111
00:05:10,150 --> 00:05:11,890
>> Factorialul 1 este de 1.

112
00:05:11,890 --> 00:05:13,860
Este nu 1 ori nimic.

113
00:05:13,860 --> 00:05:15,020
E doar o.

114
00:05:15,020 --> 00:05:17,170
Este un fapt foarte ușor.

115
00:05:17,170 --> 00:05:19,620
Și astfel încât să poată fi cazul nostru de bază.

116
00:05:19,620 --> 00:05:24,730
Dacă suntem trecut 1 în această
funcție, vom returna doar 1.

117
00:05:24,730 --> 00:05:27,320
>> Care este recursiv
caz, probabil, arata ca?

118
00:05:27,320 --> 00:05:32,445
Pentru fiecare alt număr
în afară de 1, ceea ce este modelul?

119
00:05:32,445 --> 00:05:35,780
Ei bine, dacă luăm
factorialul lui n,

120
00:05:35,780 --> 00:05:38,160
Este n ori factorialul lui n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Dacă luăm factorialul 3,
e de 3 ori factorialul 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
Și așa, dacă nu suntem
uita la 1, în caz contrar

124
00:05:47,330 --> 00:05:51,710
întoarcere n ori a
factorial de n minus 1.

125
00:05:51,710 --> 00:05:53,210
E destul de simplu.

126
00:05:53,210 --> 00:05:57,360
>> Și de dragul de a avea ceva
mai curat și mai elegant cod,

127
00:05:57,360 --> 00:06:01,440
știu că, dacă avem bucle singură linie
sau o singură linie de sucursale condiționale,

128
00:06:01,440 --> 00:06:04,490
putem scăpa de cele de mai
acolade în jurul lor.

129
00:06:04,490 --> 00:06:06,850
Astfel încât să putem consolida acest lucru acest lucru.

130
00:06:06,850 --> 00:06:09,640
Acest lucru are exact la fel
funcționalitate ca aceasta.

131
00:06:09,640 --> 00:06:13,850
>> Eu doar ținând departe cret
bretele, pentru că nu există decât o singură linie

132
00:06:13,850 --> 00:06:18,500
în interiorul acestor ramuri condiționate.

133
00:06:18,500 --> 00:06:21,160
Astfel încât acestea să se comporte identic.

134
00:06:21,160 --> 00:06:23,800
Dacă n este egal cu 1, randamentul 1.

135
00:06:23,800 --> 00:06:28,351
În caz contrar, se întoarcă de n ori
factorialul lui n minus 1.

136
00:06:28,351 --> 00:06:29,850
Deci facem problema mici.

137
00:06:29,850 --> 00:06:33,850
Dacă n începe ca 5, vom
a reveni de 5 ori factorialul 4.

138
00:06:33,850 --> 00:06:37,100
Și vom vedea într-un minut atunci când vorbim
despre stack-- apel într-un alt film

139
00:06:37,100 --> 00:06:39,390
în cazul în care vorbim despre
apel stack-- vom afla

140
00:06:39,390 --> 00:06:41,630
despre ce exact acest proces funcționează.

141
00:06:41,630 --> 00:06:46,970
>> Dar în timp ce factorial de 5 spune
reveni de 5 ori factorial de 4, și 4

142
00:06:46,970 --> 00:06:49,710
se va spune, OK, bine, întoarcere
4 ori factorial de 3.

143
00:06:49,710 --> 00:06:51,737
Și, după cum puteți vedea, suntem
un fel de abordare 1.

144
00:06:51,737 --> 00:06:53,820
Ne apropiem și
mai aproape de acest caz de bază.

145
00:06:53,820 --> 00:06:58,180
>> Și odată ce ne-am lovit cazul de bază,
toate funcțiile anterioare

146
00:06:58,180 --> 00:07:00,540
au răspuns ei căutau.

147
00:07:00,540 --> 00:07:03,900
Factorial de 2 spunea retur
2 ori factorial de 1.

148
00:07:03,900 --> 00:07:06,760
Ei bine, factorial de 1 revine 1.

149
00:07:06,760 --> 00:07:10,090
Deci, apelul pentru factorial
de 2 poate returna de 2 ori 1,

150
00:07:10,090 --> 00:07:13,980
și să dea înapoi la factorial de
3, care este în așteptare pentru acest rezultat.

151
00:07:13,980 --> 00:07:17,110
>> Si apoi poate calcula
sale de rezultat, de 3 ori 2 este de 6,

152
00:07:17,110 --> 00:07:18,907
și da înapoi factorial de 4.

153
00:07:18,907 --> 00:07:20,740
Și din nou, avem o
video de pe stiva de apel

154
00:07:20,740 --> 00:07:23,810
în cazul în care acest lucru este ilustrat un pic
mai mult decât ceea ce spun acum.

155
00:07:23,810 --> 00:07:25,300
Dar asta este.

156
00:07:25,300 --> 00:07:29,300
Numai acest lucru este soluția la
calcularea factorialul unui număr.

157
00:07:29,300 --> 00:07:31,527
>> E doar patru linii de cod.

158
00:07:31,527 --> 00:07:32,610
Asta e destul de tare, nu?

159
00:07:32,610 --> 00:07:35,480
E un fel de sexy.

160
00:07:35,480 --> 00:07:38,580
>> Deci, în general, dar nu
întotdeauna, o funcție recursivă

161
00:07:38,580 --> 00:07:41,190
poate înlocui o buclă într-o
Funcția non-recursive.

162
00:07:41,190 --> 00:07:46,100
Deci, aici, cot la cot, este iterativ
versiune a funcției factorial.

163
00:07:46,100 --> 00:07:49,650
Ambele calcula
exact același lucru.

164
00:07:49,650 --> 00:07:52,170
>> Amândoi calcula factorialul lui n.

165
00:07:52,170 --> 00:07:54,990
Versiunea pe stânga
foloseste recursivitate să o facă.

166
00:07:54,990 --> 00:07:58,320
Versiunea pe dreapta
foloseste repetare a face acest lucru.

167
00:07:58,320 --> 00:08:02,050
>> Și notificare, trebuie să declare
o variabilă un produs număr întreg.

168
00:08:02,050 --> 00:08:02,940
Și apoi am bucla.

169
00:08:02,940 --> 00:08:06,790
Atât timp cât n este mai mare decât 0, am
păstra înmulțirea acest produs de n

170
00:08:06,790 --> 00:08:09,890
și decrementarea n până
vom calcula produsul.

171
00:08:09,890 --> 00:08:14,600
Deci, aceste două funcții, din nou,
face exact același lucru.

172
00:08:14,600 --> 00:08:19,980
Dar ei nu o fac în
exact în același mod.

173
00:08:19,980 --> 00:08:22,430
>> Acum, este posibil să se
au mai mult de un punct

174
00:08:22,430 --> 00:08:25,770
caz sau mai mult de un
caz recursiv, în funcție

175
00:08:25,770 --> 00:08:27,670
asupra a ceea ce funcția încearcă să facă.

176
00:08:27,670 --> 00:08:31,650
Tu nu sunt neapărat doar limitate la
un singur caz de bază sau un singur recursive

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

178
00:08:32,370 --> 00:08:35,320
Deci un exemplu de ceva
cu cazuri de bază multiple

179
00:08:35,320 --> 00:08:37,830
ar putea fi asta:
Secvență număr Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Vă amintiți de la
zile de școală elementară

181
00:08:41,549 --> 00:08:45,740
că secvența Fibonacci este definit
ca asta: primul element este 0.

182
00:08:45,740 --> 00:08:46,890
Al doilea element este de 1.

183
00:08:46,890 --> 00:08:49,230
Ambele sunt doar prin definiție.

184
00:08:49,230 --> 00:08:55,920
>> Apoi fiecare alt element este definit
ca suma n minus 1 și n minus 2.

185
00:08:55,920 --> 00:09:00,330
Deci al treilea element
ar fi 0 plus 1 este 1.

186
00:09:00,330 --> 00:09:03,280
Apoi al patrulea element
ar fi al doilea element, 1,

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

188
00:09:06,550 --> 00:09:08,507
Și care ar fi de 2.

189
00:09:08,507 --> 00:09:09,340
Și așa mai departe și așa mai departe.

190
00:09:09,340 --> 00:09:11,680
>> Deci, în acest caz, avem două cazuri de bază.

191
00:09:11,680 --> 00:09:14,850
Dacă n este egal cu 1, randamentul 0.

192
00:09:14,850 --> 00:09:18,560
Dacă n este egal cu 2, se întoarcă 1.

193
00:09:18,560 --> 00:09:25,930
În caz contrar, se întoarcă Fibonacci de n
minus 1 plus Fibonacci de n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Așa că e cazul de bază multiple.

195
00:09:27,180 --> 00:09:29,271
Ce zici de mai multe cazuri recursive?

196
00:09:29,271 --> 00:09:31,520
Ei bine, e ceva
numit conjectura COLLATZ.

197
00:09:31,520 --> 00:09:34,630
Eu nu am de gând să spun,
Știi ce este că,

198
00:09:34,630 --> 00:09:38,170
pentru că este de fapt ultima noastră
problemă pentru acest videoclip special.

199
00:09:38,170 --> 00:09:43,220
Și este exercițiul nostru
să lucreze împreună.

200
00:09:43,220 --> 00:09:46,760
>> Deci, aici e ceea ce
COLLATZ conjecture este--

201
00:09:46,760 --> 00:09:48,820
se aplică pentru orice număr întreg pozitiv.

202
00:09:48,820 --> 00:09:51,500
Și se speculează că este
întotdeauna posibil să mă întorc

203
00:09:51,500 --> 00:09:55,060
la 1, dacă urmați acești pași.

204
00:09:55,060 --> 00:09:57,560
Dacă n este 1, opri.

205
00:09:57,560 --> 00:10:00,070
Avem înapoi la 1 dacă n este 1.

206
00:10:00,070 --> 00:10:05,670
>> În caz contrar, trece prin aceasta
proces din nou pe n împărțit la 2.

207
00:10:05,670 --> 00:10:08,200
Și a vedea dacă puteți obține înapoi la 1.

208
00:10:08,200 --> 00:10:13,260
În caz contrar, dacă n este impar, trece prin
acest proces din nou pe 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
sau de 3 ori n plus 1.

210
00:10:15,552 --> 00:10:17,010
Deci, aici avem un singur caz de bază.

211
00:10:17,010 --> 00:10:18,430
Dacă n este egal cu 1, opri.

212
00:10:18,430 --> 00:10:20,230
Nu facem nici mai recursivitate.

213
00:10:20,230 --> 00:10:23,730
>> Dar avem două cazuri recursive.

214
00:10:23,730 --> 00:10:28,750
Dacă n este chiar, vom face o recursive
caz, de asteptare n împărțit la 2.

215
00:10:28,750 --> 00:10:33,950
Dacă n este impar, facem un alt
caz recursiv pe 3 ori n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Și astfel obiectivul pentru acest videoclip este
pentru a lua un al doilea, întrerupe clipul video,

217
00:10:39,120 --> 00:10:42,440
și să încerce și să scrie acest
Funcția recursive COLLATZ

218
00:10:42,440 --> 00:10:47,640
în cazul în care va trece într-o valoare n, și
se calculează câte măsurile pe care le

219
00:10:47,640 --> 00:10:52,430
nevoie pentru a ajunge la 1, dacă începeți de la n
și să urmați acești pași deasupra.

220
00:10:52,430 --> 00:10:56,660
Dacă n este 1, este nevoie de 0 pași.

221
00:10:56,660 --> 00:11:00,190
În caz contrar, se va
ia un pas plus cu toate acestea

222
00:11:00,190 --> 00:11:06,200
mulți pași pe care le ia pe fiecare n
împărțit la 2, dacă n este chiar, sau 3n plus 1

223
00:11:06,200 --> 00:11:08,100
dacă n este impar.

224
00:11:08,100 --> 00:11:11,190
>> Acum, am pus pe ecran aici
o serie de lucruri de testare pentru tine,

225
00:11:11,190 --> 00:11:15,690
un cuplu de cazuri teste pentru tine, pentru a vedea
ce aceste diferite numere COLLATZ sunt,

226
00:11:15,690 --> 00:11:17,440
și, de asemenea, o ilustrare
cu privire la măsurile care

227
00:11:17,440 --> 00:11:20,390
trebuie să fie trecut prin astfel încât să puteți
un fel de a vedea acest proces în acțiune.

228
00:11:20,390 --> 00:11:24,222
Deci, dacă n este egal cu
1, COLLATZ lui n este 0.

229
00:11:24,222 --> 00:11:26,180
Tu nu trebuie să faci
orice să mă întorc la 1.

230
00:11:26,180 --> 00:11:27,600
Ești deja acolo.

231
00:11:27,600 --> 00:11:30,550
>> Dacă n este 2, este nevoie
un pas pentru a ajunge la 1.

232
00:11:30,550 --> 00:11:31,810
Începi cu 2.

233
00:11:31,810 --> 00:11:33,100
Ei bine, 2 nu este egal cu 1.

234
00:11:33,100 --> 00:11:36,580
Deci, va fi un pas
Cu toate acestea, plus mai multe etape IT

235
00:11:36,580 --> 00:11:38,015
capătă n împărțit la 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 împărțit la 2 este 1.

238
00:11:42,910 --> 00:11:47,200
Deci, este nevoie de un pas în plus, dar
mulți pași este nevoie de timp de 1.

239
00:11:47,200 --> 00:11:49,720
1 ia de zero pași.

240
00:11:49,720 --> 00:11:52,370
>> Pentru 3, după cum puteți vedea, există
destul de câțiva pași implicate.

241
00:11:52,370 --> 00:11:53,590
Tu du-te de la 3.

242
00:11:53,590 --> 00:11:56,710
Și apoi te duci la
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Este nevoie de șapte pași pentru a obține înapoi la 1.

244
00:11:58,804 --> 00:12:01,220
Și, după cum puteți vedea, există o
cuplu alte cazuri de testare aici

245
00:12:01,220 --> 00:12:02,470
pentru a testa programul.

246
00:12:02,470 --> 00:12:03,970
Deci, din nou, întrerupe clipul video.

247
00:12:03,970 --> 00:12:09,210
Și voi merge sări înapoi acum la
ce procesul real este aici,

248
00:12:09,210 --> 00:12:11,390
ceea ce aceasta presupunere este.

249
00:12:11,390 --> 00:12:14,140
>> Vezi dacă poți da seama
cum de a defini COLLATZ de n

250
00:12:14,140 --> 00:12:19,967
astfel încât acesta calculează câte
pașii este nevoie pentru a ajunge la 1.

251
00:12:19,967 --> 00:12:23,050
Deci sperăm, le-ați întrerupt video
și nu sunt doar de așteptare pentru mine

252
00:12:23,050 --> 00:12:25,820
pentru a vă oferi răspunsul aici.

253
00:12:25,820 --> 00:12:29,120
Dar dacă sunteți, ei bine,
aici e răspunsul oricum.

254
00:12:29,120 --> 00:12:33,070
>> Deci, aici este o posibilă definiție
a funcției COLLATZ.

255
00:12:33,070 --> 00:12:35,610
Baza noastra de case-- dacă n este
egală cu 1, ne întoarcem 0.

256
00:12:35,610 --> 00:12:38,250
Aceasta nu ia nici o
pași pentru a obține înapoi la 1.

257
00:12:38,250 --> 00:12:42,710
>> În caz contrar, avem două cases-- recursiv
unul pentru numerele chiar și unul pentru ciudat.

258
00:12:42,710 --> 00:12:47,164
Modul în care am testa pentru numere chiar
este de a verifica dacă n mod 2 este egal cu 0.

259
00:12:47,164 --> 00:12:49,080
Aceasta este, în principiu, din nou,
pune întrebarea,

260
00:12:49,080 --> 00:12:54,050
dacă vă amintiți ce este-- mod dacă am
divide n prin 2 nu există nici o rest?

261
00:12:54,050 --> 00:12:55,470
Asta ar fi un număr par.

262
00:12:55,470 --> 00:13:01,370
>> Și așa că, dacă n mod 2 este egal cu 0 este
Testarea este aceasta un număr par.

263
00:13:01,370 --> 00:13:04,250
Dacă este așa, vreau să se întoarcă 1,
pentru că acest lucru este cu siguranta

264
00:13:04,250 --> 00:13:09,270
luând un pas plus COLLATZ de
indiferent de numărul este de jumătate din mine.

265
00:13:09,270 --> 00:13:13,910
În caz contrar, vreau să se întoarcă 1
plus COLLATZ de 3 ori n plus 1.

266
00:13:13,910 --> 00:13:16,060
Asta a fost de altă parte
pas recursiv pe care le

267
00:13:16,060 --> 00:13:19,470
ar putea lua pentru a calcula
Collatz-- numărul de trepte

268
00:13:19,470 --> 00:13:22,610
este nevoie să mă întorc
la 1 atribuie un număr.

269
00:13:22,610 --> 00:13:24,610
Deci sperăm că, acest exemplu
ți-a dat un pic

270
00:13:24,610 --> 00:13:26,620
de un gust de proceduri recursive.

271
00:13:26,620 --> 00:13:30,220
Sperăm că, crezi că este un cod
puțin mai frumos dacă ar fi aplicate

272
00:13:30,220 --> 00:13:32,760
într-un mod elegant, recursiv.

273
00:13:32,760 --> 00:13:35,955
Dar chiar dacă nu, recursivitate este un
instrument foarte puternic cu toate acestea.

274
00:13:35,955 --> 00:13:38,330
Și așa este cu siguranta ceva
pentru a obține capul în jurul valorii de,

275
00:13:38,330 --> 00:13:41,360
pentru că vei fi capabil de a crea
programe destul de rece, folosind recursivitate

276
00:13:41,360 --> 00:13:45,930
care altfel ar putea fi dificil de a scrie
dacă utilizați bucle și repetare.

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

278
00:13:46,980 --> 00:13:48,780
Acest lucru este CS50.

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