1
00:00:00,000 --> 00:00:05,860
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Vostè probablement pensa que
codi només s'utilitza per a realitzar una tasca.

3
00:00:09,530 --> 00:00:10,450
Vostè escriu a terme.

4
00:00:10,450 --> 00:00:11,664
Fa alguna cosa.

5
00:00:11,664 --> 00:00:12,580
Això és més o menys la mateixa.

6
00:00:12,580 --> 00:00:13,160
>> Vostè compilar-lo.

7
00:00:13,160 --> 00:00:13,993
Executa el programa.

8
00:00:13,993 --> 00:00:15,370
Vostè està bo per anar.

9
00:00:15,370 --> 00:00:17,520
>> Però ho creguis o no, si
codificar per un llarg temps,

10
00:00:17,520 --> 00:00:20,550
en realitat es pot arribar a veure
codi com una cosa que és bonic.

11
00:00:20,550 --> 00:00:23,275
Soluciona un problema en
una forma molt interessant,

12
00:00:23,275 --> 00:00:26,510
o hi ha alguna cosa de veritat
endreçada sobre la forma en què es veu.

13
00:00:26,510 --> 00:00:28,750
Vostè podria estar rient
a mi, però és la veritat.

14
00:00:28,750 --> 00:00:31,530
I recursivitat és una forma
per aconseguir una espècie d'aquesta idea

15
00:00:31,530 --> 00:00:34,090
de la bella, d'aspecte elegant codi.

16
00:00:34,090 --> 00:00:37,740
Soluciona problemes de manera que
són interessants, fàcil de visualitzar,

17
00:00:37,740 --> 00:00:39,810
i sorprenentment curt.

18
00:00:39,810 --> 00:00:43,190
>> Les obres manera recursivitat
és, una funció recursiva

19
00:00:43,190 --> 00:00:49,291
es defineix com una funció que crida
a si mateixa com a part de la seva execució.

20
00:00:49,291 --> 00:00:51,790
Això pot semblar una mica estrany,
i anem a veure una mica

21
00:00:51,790 --> 00:00:53,750
sobre com funciona això en un moment.

22
00:00:53,750 --> 00:00:55,560
Però, de nou, aquests
procediments recursius són

23
00:00:55,560 --> 00:00:57,730
serà tan elegant
perquè van

24
00:00:57,730 --> 00:01:00,410
per resoldre aquest problema sense
tenint totes aquestes altres funcions

25
00:01:00,410 --> 00:01:02,710
o aquests llargs bucles.

26
00:01:02,710 --> 00:01:06,310
Vas a veure que aquests recursiva
procediments van a semblar tan curt.

27
00:01:06,310 --> 00:01:10,610
I realment es va a fer
el seu codi semblen molt més bonica.

28
00:01:10,610 --> 00:01:12,560
>> Et vaig a donar un exemple
d'això per veure com

29
00:01:12,560 --> 00:01:14,880
un procediment recursiu pot definir-se.

30
00:01:14,880 --> 00:01:18,202
Així que si vostè està familiaritzat amb aquest
de la classe de matemàtiques, fa molts anys,

31
00:01:18,202 --> 00:01:20,910
Hi ha alguna cosa cridat el
funció factorial, que és generalment

32
00:01:20,910 --> 00:01:25,340
denotat com un signe d'exclamació, que
es defineix sobre tots els enters positius.

33
00:01:25,340 --> 00:01:28,850
I la forma en què n
factorial es calcula

34
00:01:28,850 --> 00:01:31,050
està vostè multiplica tots
els números de menys de

35
00:01:31,050 --> 00:01:33,750
o igual a n junts--
tots els números sencers de menys de

36
00:01:33,750 --> 00:01:34,880
o igual a n junts.

37
00:01:34,880 --> 00:01:39,850
>> Així maig factorial és 5 vegades
4 vegades 3 vegades 2 vegades 1.

38
00:01:39,850 --> 00:01:43,020
I 4 factorial és 4 vegades
3 vegades 2 cops 1 i així successivament.

39
00:01:43,020 --> 00:01:44,800
Vostè aconsegueix la idea.

40
00:01:44,800 --> 00:01:47,060
>> Com programadors, no ho fem
utilitzar n, signe d'exclamació.

41
00:01:47,060 --> 00:01:51,840
Així que anem a definir el factorial
funció com un fet de n.

42
00:01:51,840 --> 00:01:56,897
I utilitzarem factorial per crear
una solució recursiva a un problema.

43
00:01:56,897 --> 00:01:59,230
I crec que podria trobar
que és molt més visual

44
00:01:59,230 --> 00:02:02,380
apel·lant a la iterativa
versió d'aquest, el qual

45
00:02:02,380 --> 00:02:05,010
també anem a fer una ullada a en un moment.

46
00:02:05,010 --> 00:02:08,310
>> Així que aquí hi ha un parell de
joc de paraules facts-- intended--

47
00:02:08,310 --> 00:02:10,169
sobre la factorial--
funció factorial.

48
00:02:10,169 --> 00:02:13,090
El factorial d'1, com ja he dit, és 1.

49
00:02:13,090 --> 00:02:15,690
El factorial de 2 és 2 vegades 1.

50
00:02:15,690 --> 00:02:18,470
El factorial de 3 és 3
Temps 2 Temps 1, i així successivament.

51
00:02:18,470 --> 00:02:20,810
Parlem de 4 i 5 ja.

52
00:02:20,810 --> 00:02:23,940
>> Però en mirar a això, no és això cert?

53
00:02:23,940 --> 00:02:28,220
¿No és el factorial de 2 només
2 vegades el factorial d'1?

54
00:02:28,220 --> 00:02:31,130
Vull dir, el factorial d'1 es 1.

55
00:02:31,130 --> 00:02:34,940
Per què no podem simplement dir que,
des factorial de 2 és 2 vegades 1,

56
00:02:34,940 --> 00:02:38,520
és realment només 2 vegades
el factorial d'1?

57
00:02:38,520 --> 00:02:40,900
>> I després estendre aquesta idea,
no és el factorial de 3

58
00:02:40,900 --> 00:02:44,080
només 3 vegades el factorial de 2?

59
00:02:44,080 --> 00:02:50,350
I el factorial de 4 és 4 vegades
el factorial de 3, i així successivament?

60
00:02:50,350 --> 00:02:52,530
De fet, el factorial
de qualsevol nombre pot simplement

61
00:02:52,530 --> 00:02:54,660
ser expressada si espècie
de portar això a terme sempre.

62
00:02:54,660 --> 00:02:56,870
Podem tipus de generalitzar
el problema factorial

63
00:02:56,870 --> 00:02:59,910
ja que és n vegades els
factorial de n almenys 1.

64
00:02:59,910 --> 00:03:04,840
És n vegades el producte de
tots els nombres menors que jo.

65
00:03:04,840 --> 00:03:08,890
>> Aquesta idea, això
generalització del problema,

66
00:03:08,890 --> 00:03:13,410
ens permet de forma recursiva
definir la funció factorial.

67
00:03:13,410 --> 00:03:15,440
Quan es defineix una funció
recursiva, hi ha

68
00:03:15,440 --> 00:03:17,470
dues coses que han de ser part d'ella.

69
00:03:17,470 --> 00:03:20,990
Vostè necessita tenir una cosa anomenada
cas base, que, quan vostè els activa,

70
00:03:20,990 --> 00:03:22,480
s'aturarà el procés recursiu.

71
00:03:22,480 --> 00:03:25,300
>> Altrament, una funció que crida
itself-- com es podria imagine--

72
00:03:25,300 --> 00:03:26,870
podria continuar per sempre.

73
00:03:26,870 --> 00:03:29,047
Funció crida a la funció
crida a les trucades de funció

74
00:03:29,047 --> 00:03:30,380
la funció crida a la funció.

75
00:03:30,380 --> 00:03:32,380
Si vostè no té una forma
per detenir-lo, el seu programa

76
00:03:32,380 --> 00:03:34,760
serà atrapat amb eficàcia
en un bucle infinit.

77
00:03:34,760 --> 00:03:37,176
Serà estavellar finalment,
perquè es quedarà sense memòria.

78
00:03:37,176 --> 00:03:38,990
Però això no ve al cas.

79
00:03:38,990 --> 00:03:42,210
>> Hem de tenir alguna altra manera d'aturar
coses a més del nostre programa de estavellar-se,

80
00:03:42,210 --> 00:03:46,010
perquè un programa que s'estavella és
Probablement no és bell o elegant.

81
00:03:46,010 --> 00:03:47,690
I així en diem el cas base.

82
00:03:47,690 --> 00:03:50,610
Aquesta és una solució simple
a un problema que s'atura

83
00:03:50,610 --> 00:03:52,770
el procés recursiu que es produeixin.

84
00:03:52,770 --> 00:03:55,220
Així que aquesta és una part de
una funció recursiva.

85
00:03:55,220 --> 00:03:56,820
>> La segona part és el cas recursiu.

86
00:03:56,820 --> 00:03:59,195
I aquí és on la recursivitat
en realitat tenir lloc.

87
00:03:59,195 --> 00:04:02,200
Aquí és on el
funció es digui a si mateix.

88
00:04:02,200 --> 00:04:05,940
>> No va a dir-exactament
de la mateixa manera que es deia.

89
00:04:05,940 --> 00:04:08,880
Serà una lleugera variació
que fa que el problema és

90
00:04:08,880 --> 00:04:11,497
tractant de resoldre una miqueta més petit.

91
00:04:11,497 --> 00:04:14,330
Però en general, passa la pilota
de resoldre la major part de la solució

92
00:04:14,330 --> 00:04:17,450
a una trucada diferent en la línia.

93
00:04:17,450 --> 00:04:20,290
>> Quin d'aquests looks
com el cas base en aquesta llista?

94
00:04:20,290 --> 00:04:25,384
Quin d'aquests looks com el
solució més senzilla a un problema?

95
00:04:25,384 --> 00:04:27,550
Tenim un munt de factorials,
i podríem continuar

96
00:04:27,550 --> 00:04:30,470
anar en-- 6, 7, 8, 9, 10, i així successivament.

97
00:04:30,470 --> 00:04:34,130
>> Però un d'aquests sembla un
bon cas és el cas base.

98
00:04:34,130 --> 00:04:35,310
És una solució molt simple.

99
00:04:35,310 --> 00:04:37,810
No hem de fer res especial.

100
00:04:37,810 --> 00:04:40,560
>> El factorial d'1 es 1.

101
00:04:40,560 --> 00:04:42,790
No hem de fer cap
multiplicació en absolut.

102
00:04:42,790 --> 00:04:45,248
Sembla com si anem
per tractar de resoldre aquest problema,

103
00:04:45,248 --> 00:04:47,600
i hem d'aturar la
recursivitat en algun lloc,

104
00:04:47,600 --> 00:04:50,610
probablement volem aturar
quan vam arribar a 1.

105
00:04:50,610 --> 00:04:54,580
No volem que s'aturi abans d'això.

106
00:04:54,580 --> 00:04:56,660
>> Així que si estem definint
la nostra funció factorial,

107
00:04:56,660 --> 00:04:58,690
aquí està un esquelet per
com podem fer això.

108
00:04:58,690 --> 00:05:03,110
Hem de connectar aquests dos coses--
el cas base i el cas recursiu.

109
00:05:03,110 --> 00:05:04,990
Quin és el cas base?

110
00:05:04,990 --> 00:05:10,150
Si n és igual a 1, tornar 1-- això és
un problema molt simple de resoldre.

111
00:05:10,150 --> 00:05:11,890
>> El factorial d'1 es 1.

112
00:05:11,890 --> 00:05:13,860
No són 1 vegades res.

113
00:05:13,860 --> 00:05:15,020
És només 1.

114
00:05:15,020 --> 00:05:17,170
És un fet molt fàcil.

115
00:05:17,170 --> 00:05:19,620
I perquè pugui ser el nostre cas base.

116
00:05:19,620 --> 00:05:24,730
Si ens passem 1 en aquest
funció, només haurem de tornem gener.

117
00:05:24,730 --> 00:05:27,320
>> Quina és la recursiva
cas probablement sembla?

118
00:05:27,320 --> 00:05:32,445
Per cada altre número
a més d'1, quin és el patró?

119
00:05:32,445 --> 00:05:35,780
Bé, si estem prenent
el factorial de n,

120
00:05:35,780 --> 00:05:38,160
És en moments n el factorial de n almenys 1.

121
00:05:38,160 --> 00:05:42,130
>> Si estem prenent el factorial de 3,
que és 3 vegades el factorial de 3 menys 1,

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

123
00:05:43,070 --> 00:05:47,330
I pel que si no estem
mirant a 1, en cas contrari

124
00:05:47,330 --> 00:05:51,710
retorn n vegades els
factorial de n almenys 1.

125
00:05:51,710 --> 00:05:53,210
És bastant senzill.

126
00:05:53,210 --> 00:05:57,360
>> I pel bé de tenir una mica
més neta i més elegant de codi,

127
00:05:57,360 --> 00:06:01,440
saber que si tenim bucles d'una sola línia
o d'una sola línia de salts condicionals,

128
00:06:01,440 --> 00:06:04,490
podem desfer-nos de tota la
claus al voltant d'ells.

129
00:06:04,490 --> 00:06:06,850
Així que podem consolidar aquest a això.

130
00:06:06,850 --> 00:06:09,640
Això té exactament el mateix
funcionalitat que això.

131
00:06:09,640 --> 00:06:13,850
>> Només estic traient l'arrissat
suports, perquè només hi ha una línia

132
00:06:13,850 --> 00:06:18,500
dins d'aquestes branques condicionals.

133
00:06:18,500 --> 00:06:21,160
Així que aquests es comporten de forma idèntica.

134
00:06:21,160 --> 00:06:23,800
Si n és igual a 1, tornar 1.

135
00:06:23,800 --> 00:06:28,351
Altrament tornarà n vegades
el factorial de n almenys 1.

136
00:06:28,351 --> 00:06:29,850
Així que estem fent el problema més petit.

137
00:06:29,850 --> 00:06:33,850
Si n comença com 5, anem a
tornar 5 vegades el factorial de 4.

138
00:06:33,850 --> 00:06:37,100
I veurem en un minut quan parlem
sobre la stack-- anomenada en un altre vídeo

139
00:06:37,100 --> 00:06:39,390
on es parla de la
cridar stack-- aprendrem

140
00:06:39,390 --> 00:06:41,630
sobre per què exactament aquest procés funciona.

141
00:06:41,630 --> 00:06:46,970
>> Però mentre factorial de 5 diu
tornar 5 vegades factorial de 4, i 4

142
00:06:46,970 --> 00:06:49,710
es dirà, bé, bé, el retorn
4 vegades el factorial de 3.

143
00:06:49,710 --> 00:06:51,737
I com es pot veure, estem
tipus d'apropar a 1.

144
00:06:51,737 --> 00:06:53,820
Estem cada vegada més a prop i
més propera a la del cas base.

145
00:06:53,820 --> 00:06:58,180
>> I una vegada que arribem a la hipòtesi de base,
totes les funcions anteriors

146
00:06:58,180 --> 00:07:00,540
tenir la resposta que estaven buscant.

147
00:07:00,540 --> 00:07:03,900
Factorial de 2 estava dient retorn
2 vegades el factorial d'1.

148
00:07:03,900 --> 00:07:06,760
Bé, factorial d'1 torna 1.

149
00:07:06,760 --> 00:07:10,090
Així que la convocatòria de factorial
de 2 pot tornar 2 cops 1,

150
00:07:10,090 --> 00:07:13,980
i donar aquesta volta a factorial de
3, que està a l'espera d'aquest resultat.

151
00:07:13,980 --> 00:07:17,110
>> I llavors es pot calcular
el seu resultat, 3 vegades 2 és 6,

152
00:07:17,110 --> 00:07:18,907
i donar-li volta a factorial de 4.

153
00:07:18,907 --> 00:07:20,740
I de nou, tenim una
vídeo a la pila de trucades

154
00:07:20,740 --> 00:07:23,810
on això s'il·lustra una mica
més del que estic dient ara.

155
00:07:23,810 --> 00:07:25,300
Però això és tot.

156
00:07:25,300 --> 00:07:29,300
Això per si sol és la solució a
calcular el factorial d'un nombre.

157
00:07:29,300 --> 00:07:31,527
>> És només quatre línies de codi.

158
00:07:31,527 --> 00:07:32,610
Això està molt bé, oi?

159
00:07:32,610 --> 00:07:35,480
És una mica sexy.

160
00:07:35,480 --> 00:07:38,580
>> Així que en general, però no
sempre, una funció recursiva

161
00:07:38,580 --> 00:07:41,190
pot substituir un bucle en una
funció no recursiva.

162
00:07:41,190 --> 00:07:46,100
Així que aquí, al costat de l'altre, és el iteratiu
versió de la funció factorial.

163
00:07:46,100 --> 00:07:49,650
Tots dos calcular
exactament el mateix.

164
00:07:49,650 --> 00:07:52,170
>> Tots dos calcular el factorial de n.

165
00:07:52,170 --> 00:07:54,990
La versió de l'esquerra
utilitza la recursivitat per fer-ho.

166
00:07:54,990 --> 00:07:58,320
La versió a la dreta
utilitza iteració per fer-ho.

167
00:07:58,320 --> 00:08:02,050
>> I fixin-se, hem de declarar
una variable d'un producte sencer.

168
00:08:02,050 --> 00:08:02,940
I després ens bucle.

169
00:08:02,940 --> 00:08:06,790
Sempre i quan n és més gran que 0, es
continuar multiplicant aquest producte per n

170
00:08:06,790 --> 00:08:09,890
i decrementar n fins
calculem el producte.

171
00:08:09,890 --> 00:08:14,600
Així doncs, aquestes dues funcions, una vegada més,
fer exactament el mateix.

172
00:08:14,600 --> 00:08:19,980
Però ells no ho fan en
exactament de la mateixa manera.

173
00:08:19,980 --> 00:08:22,430
>> Ara, és possible
tenir més d'una base de

174
00:08:22,430 --> 00:08:25,770
cas o més d'una
cas recursiu, depenent

175
00:08:25,770 --> 00:08:27,670
en el que la seva funció està tractant de fer.

176
00:08:27,670 --> 00:08:31,650
No està necessàriament només limitat a
un sol cas base o un sol recursiva

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

178
00:08:32,370 --> 00:08:35,320
Així que un exemple d'alguna cosa
amb múltiples casos base

179
00:08:35,320 --> 00:08:37,830
podria ser la això-
Sèrie de Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Vostè pot recordar de
dies d'escola primària

181
00:08:41,549 --> 00:08:45,740
que la seqüència de Fibonacci es defineix
així- el primer element és 0.

182
00:08:45,740 --> 00:08:46,890
El segon element és 1.

183
00:08:46,890 --> 00:08:49,230
Tots dos són simplement per definició.

184
00:08:49,230 --> 00:08:55,920
>> Llavors es defineix tots els altres elements
com la suma de n menys 1 i n almenys 2.

185
00:08:55,920 --> 00:09:00,330
Així que el tercer element
seria 0 + 1 és 1.

186
00:09:00,330 --> 00:09:03,280
I llavors el quart element
seria el segon element, 1,

187
00:09:03,280 --> 00:09:06,550
més el tercer element, 1.

188
00:09:06,550 --> 00:09:08,507
I això seria febrer.

189
00:09:08,507 --> 00:09:09,340
I així successivament i així successivament.

190
00:09:09,340 --> 00:09:11,680
>> Així que en aquest cas, tenim dos casos base.

191
00:09:11,680 --> 00:09:14,850
Si n és igual a 1, retorna 0.

192
00:09:14,850 --> 00:09:18,560
Si n és igual a 2, tornar 1.

193
00:09:18,560 --> 00:09:25,930
Altrament, torni Fibonacci de n
almenys 1 més de Fibonacci de n almenys 2.

194
00:09:25,930 --> 00:09:27,180
>> Així que això és diversos casos base.

195
00:09:27,180 --> 00:09:29,271
Què passa amb múltiples casos recurrents?

196
00:09:29,271 --> 00:09:31,520
Bé, hi ha alguna cosa
crida l'conjectura de Collatz.

197
00:09:31,520 --> 00:09:34,630
Jo no vaig a dir,
vostè sap el que és això,

198
00:09:34,630 --> 00:09:38,170
perquè en realitat és el nostre últim
problema per a aquest vídeo en particular.

199
00:09:38,170 --> 00:09:43,220
I és el nostre exercici
per treballar junts.

200
00:09:43,220 --> 00:09:46,760
>> Així que aquí està el que el
Collatz conjectura és--

201
00:09:46,760 --> 00:09:48,820
que s'aplica a cada nombre enter positiu.

202
00:09:48,820 --> 00:09:51,500
I especula que és
sempre és possible tornar

203
00:09:51,500 --> 00:09:55,060
1 si vostè segueix aquests passos.

204
00:09:55,060 --> 00:09:57,560
Si n és 1, per.

205
00:09:57,560 --> 00:10:00,070
Tenim de nou a 1 si n és 1.

206
00:10:00,070 --> 00:10:05,670
>> Altrament, aneu a través d'aquest
procés de nou a n dividit per 2.

207
00:10:05,670 --> 00:10:08,200
I veure si pot tornar a 1.

208
00:10:08,200 --> 00:10:13,260
Altrament, si n és imparell, anar a través d'
aquest procés nou en 3n més 1,

209
00:10:13,260 --> 00:10:15,552
o 3 vegades N més 1.

210
00:10:15,552 --> 00:10:17,010
Així que aquí tenim un cas base.

211
00:10:17,010 --> 00:10:18,430
Si n és igual a 1, parar.

212
00:10:18,430 --> 00:10:20,230
No estem fent res més recursivitat.

213
00:10:20,230 --> 00:10:23,730
>> Però tenim dos casos recursives.

214
00:10:23,730 --> 00:10:28,750
Si n és parell, ho fem d'un recursiu
cas, trucant n dividit per 2.

215
00:10:28,750 --> 00:10:33,950
Si n és imparell, fem un diferent
cas recursiu en 3 vegades N més 1.

216
00:10:33,950 --> 00:10:39,120
>> I el que l'objectiu d'aquest vídeo és
prendre un segon, fer una pausa en el video,

217
00:10:39,120 --> 00:10:42,440
i tractar d'escriure aquest
funció recursiva Collatz

218
00:10:42,440 --> 00:10:47,640
on es passa en un valor n, i
calcula quants passos

219
00:10:47,640 --> 00:10:52,430
pren per arribar a 1 si s'inicia a partir de n
i vostè segueix aquests passos fins a dalt.

220
00:10:52,430 --> 00:10:56,660
Si n és 1, es triga 0 passos.

221
00:10:56,660 --> 00:11:00,190
En cas contrari, es va a
fer un pas més però

222
00:11:00,190 --> 00:11:06,200
molts passos que es necessita en cada n
dividit per 2 si n és parell, o 3n més 1

223
00:11:06,200 --> 00:11:08,100
si n és imparell.

224
00:11:08,100 --> 00:11:11,190
>> Ara, m'he posat a la pantalla aquí
un parell de coses de prova per a vostè,

225
00:11:11,190 --> 00:11:15,690
un parell de proves de casos per a vostè, per veure
el que aquests diversos números Collatz són,

226
00:11:15,690 --> 00:11:17,440
i també una il·lustració
dels passos que

227
00:11:17,440 --> 00:11:20,390
necessiten ser passat pel que pot
sort de veure aquest procés en acció.

228
00:11:20,390 --> 00:11:24,222
Així que si n és igual a
1, Collatz de n és 0.

229
00:11:24,222 --> 00:11:26,180
Vostè no té a veure
qualsevol cosa per aconseguir de nou a 1.

230
00:11:26,180 --> 00:11:27,600
Vostè és ja allà.

231
00:11:27,600 --> 00:11:30,550
>> Si n és 2, es necessita
un pas per arribar a 1.

232
00:11:30,550 --> 00:11:31,810
Es comença amb 2.

233
00:11:31,810 --> 00:11:33,100
Bé, 2 no és igual a 1.

234
00:11:33,100 --> 00:11:36,580
Així que serà un pas
més però moltes mesures que

235
00:11:36,580 --> 00:11:38,015
adquireix n dividit per 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 dividit per 2 és 1.

238
00:11:42,910 --> 00:11:47,200
Així que pren un pas més però
molts passos que triga 1.

239
00:11:47,200 --> 00:11:49,720
1 presa zero passos.

240
00:11:49,720 --> 00:11:52,370
>> Per a 3, com es pot veure, no hi ha
uns quants passos involucrats.

241
00:11:52,370 --> 00:11:53,590
Es passa de 3.

242
00:11:53,590 --> 00:11:56,710
I després vas a
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Porta set passos per tornar a 1.

244
00:11:58,804 --> 00:12:01,220
I com es pot veure, hi ha una
parell d'altres casos de prova aquí

245
00:12:01,220 --> 00:12:02,470
per posar a prova el seu programa.

246
00:12:02,470 --> 00:12:03,970
Així que de nou, fer una pausa en el vídeo.

247
00:12:03,970 --> 00:12:09,210
I jo aniré a saltar de nou ara
el que el procés real és aquí,

248
00:12:09,210 --> 00:12:11,390
el que aquesta conjectura és.

249
00:12:11,390 --> 00:12:14,140
>> A veure si pots esbrinar
com definir Collatz de n

250
00:12:14,140 --> 00:12:19,967
de manera que calcula quants
els passos que es necessita per arribar a 1.

251
00:12:19,967 --> 00:12:23,050
Així que espero que, d'haver detingut el vídeo
i no està a l'espera de mi

252
00:12:23,050 --> 00:12:25,820
per donar-li la resposta aquí.

253
00:12:25,820 --> 00:12:29,120
Però si vostè és, així,
aquí està la resposta de totes maneres.

254
00:12:29,120 --> 00:12:33,070
>> Així que aquí hi ha una possible definició
de la funció de Collatz.

255
00:12:33,070 --> 00:12:35,610
La nostra base cas-- si n és
igual a 1, tornem 0.

256
00:12:35,610 --> 00:12:38,250
No es necessita cap
passos per arribar de nou a 1.

257
00:12:38,250 --> 00:12:42,710
>> Altrament, tenim dos casos-- recursiva
per als números parells i un altre per imparell.

258
00:12:42,710 --> 00:12:47,164
La forma en què la prova de nombres parells
és comprovar si n mod 2 és igual a 0.

259
00:12:47,164 --> 00:12:49,080
Això és bàsicament, una vegada més,
fer la pregunta,

260
00:12:49,080 --> 00:12:54,050
si vostè recorda ho és-- mod si
dividir n per 2 hi ha cap resta?

261
00:12:54,050 --> 00:12:55,470
Això seria un nombre parell.

262
00:12:55,470 --> 00:13:01,370
>> I així, si n mod 2 és igual a 0 és
aquesta prova és un nombre parell.

263
00:13:01,370 --> 00:13:04,250
Si és així, vull tornar 1,
perquè aquest és, sens dubte

264
00:13:04,250 --> 00:13:09,270
donant un pas més Collatz de
qualsevol que sigui el nombre és la meitat de mi.

265
00:13:09,270 --> 00:13:13,910
En cas contrari, vull tornar 1
més Collatz de 3 vegades n més 1.

266
00:13:13,910 --> 00:13:16,060
Aquesta va ser l'altra
pas recursiu que ens

267
00:13:16,060 --> 00:13:19,470
podria prendre per calcular el
Collatz-- el nombre de passos

268
00:13:19,470 --> 00:13:22,610
que es necessita per tornar
a 1 donat un nombre.

269
00:13:22,610 --> 00:13:24,610
Així que espero que aquest exemple
Li va donar una mica

270
00:13:24,610 --> 00:13:26,620
d'una mostra de procediments recursius.

271
00:13:26,620 --> 00:13:30,220
Amb sort, vostè pensa codi és un
poc més bella si s'apliquen

272
00:13:30,220 --> 00:13:32,760
d'una manera elegant, recursiu.

273
00:13:32,760 --> 00:13:35,955
Però fins i tot si no, la recursivitat és una
eina realment poderosa, però.

274
00:13:35,955 --> 00:13:38,330
I el que és definitivament una cosa
per obtenir el seu cap al voltant,

275
00:13:38,330 --> 00:13:41,360
perquè vostè serà capaç de crear
programes molt interessants utilitzant recursivitat

276
00:13:41,360 --> 00:13:45,930
que d'altra manera podria ser complex per escriure
si vostè està utilitzant loops i iteració.

277
00:13:45,930 --> 00:13:46,980
Sóc Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Això és CS50.

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