1
00:00:00,000 --> 00:00:05,860
>> [Música tocando]

2
00:00:05,860 --> 00:00:09,530
>> Doug LLOYD: Probablemente pensa que
código só é usado para realizar unha tarefa.

3
00:00:09,530 --> 00:00:10,450
Escribe o para fora.

4
00:00:10,450 --> 00:00:11,664
Fai algo.

5
00:00:11,664 --> 00:00:12,580
Iso é moi fermoso isto.

6
00:00:12,580 --> 00:00:13,160
>> Vostede compilalo.

7
00:00:13,160 --> 00:00:13,993
Executar o programa.

8
00:00:13,993 --> 00:00:15,370
Está preparado para ir.

9
00:00:15,370 --> 00:00:17,520
>> Pero, cren ou non, se
vostede codificar para un longo período de tempo,

10
00:00:17,520 --> 00:00:20,550
realmente pode chegar a ver
código como algo que é bonito.

11
00:00:20,550 --> 00:00:23,275
Resolve un problema en
un xeito moi interesante,

12
00:00:23,275 --> 00:00:26,510
ou hai algo realmente
puro sobre a forma que parece.

13
00:00:26,510 --> 00:00:28,750
Podes estar rindo
para min, pero é verdade.

14
00:00:28,750 --> 00:00:31,530
E recursão é un xeito
a sorte de obter esa idea

15
00:00:31,530 --> 00:00:34,090
da fermosa código, de aspecto elegante.

16
00:00:34,090 --> 00:00:37,740
El resolve os problemas de forma que
son interesantes, fácil de ver,

17
00:00:37,740 --> 00:00:39,810
e sorprendentemente curta.

18
00:00:39,810 --> 00:00:43,190
>> As obras xeito de recursão
é, unha función recursiva

19
00:00:43,190 --> 00:00:49,291
defínese como unha función que chama
Se como parte da súa execución.

20
00:00:49,291 --> 00:00:51,790
Isto pode parecer un pouco raro,
e veremos un pouco

21
00:00:51,790 --> 00:00:53,750
sobre como funciona en un momento.

22
00:00:53,750 --> 00:00:55,560
Pero, de novo, estes
procedementos recursiva son

23
00:00:55,560 --> 00:00:57,730
vai ser tan elegante
porque eles van

24
00:00:57,730 --> 00:01:00,410
para solucionar este problema, sen
Tendo en todas estas outras funcións

25
00:01:00,410 --> 00:01:02,710
ou estes longos loops.

26
00:01:02,710 --> 00:01:06,310
Vai ver que estes recursiva
procedementos van ollar tan curto.

27
00:01:06,310 --> 00:01:10,610
E realmente van facer
seu código ollar moito máis bonito.

28
00:01:10,610 --> 00:01:12,560
>> Vou che dar un exemplo
deste para ver como

29
00:01:12,560 --> 00:01:14,880
un procedemento recursiva pode ser definido.

30
00:01:14,880 --> 00:01:18,202
Entón, se está familiarizado con este
de clase de matemáticas hai moitos anos,

31
00:01:18,202 --> 00:01:20,910
Hai algo chamado
función factorial, que adoita

32
00:01:20,910 --> 00:01:25,340
denotado como un signo de admiración, que
defínese ao longo do todos os enteiros positivos.

33
00:01:25,340 --> 00:01:28,850
E a forma que n
factorial calcúlase

34
00:01:28,850 --> 00:01:31,050
é vostede multiplicar todos
os números de menos de

35
00:01:31,050 --> 00:01:33,750
ou igual a n together--
Todos os números enteiros inferiores a

36
00:01:33,750 --> 00:01:34,880
ou igual a n xuntos.

37
00:01:34,880 --> 00:01:39,850
>> Entón factorial 5 é 5 veces
4 veces 3 veces 2 veces 1.

38
00:01:39,850 --> 00:01:43,020
E 4 factorial é 4 veces
3 veces 2 veces 1 e así por diante.

39
00:01:43,020 --> 00:01:44,800
Comeza a idea.

40
00:01:44,800 --> 00:01:47,060
>> Como programadores, non
usar n, signo de admiración.

41
00:01:47,060 --> 00:01:51,840
Entón, imos definir o factorial
función como feito de n.

42
00:01:51,840 --> 00:01:56,897
E nós imos usar para crear factorial
unha solución para un problema recursiva.

43
00:01:56,897 --> 00:01:59,230
E eu creo que pode atopar
que é moito máis visual

44
00:01:59,230 --> 00:02:02,380
atractivo que o iterativo
versión deste, que

45
00:02:02,380 --> 00:02:05,010
nós tamén imos dar un ollo en un momento.

46
00:02:05,010 --> 00:02:08,310
>> Entón, aquí están un par de
xogo de palabras facts-- intended--

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

48
00:02:10,169 --> 00:02:13,090
O factorial dun, como dixen, é unha.

49
00:02:13,090 --> 00:02:15,690
O factorial de 2 é 2 veces 1.

50
00:02:15,690 --> 00:02:18,470
O factorial de 3 a 3
veces 2 veces 1, e así por diante.

51
00:02:18,470 --> 00:02:20,810
Nós falamos sobre 4 e 5 xa.

52
00:02:20,810 --> 00:02:23,940
>> Pero mirando para iso, non é verdade?

53
00:02:23,940 --> 00:02:28,220
Non é só factorial 2
2 veces o factorial dun?

54
00:02:28,220 --> 00:02:31,130
Quero dicir, o factorial dun é un.

55
00:02:31,130 --> 00:02:34,940
Entón, por que non podemos simplemente dicir que,
desde factorial 2 é 2 veces 1,

56
00:02:34,940 --> 00:02:38,520
É realmente só 2 veces
o factorial dun?

57
00:02:38,520 --> 00:02:40,900
>> E entón estender esa idea,
non é o factorial de 3

58
00:02:40,900 --> 00:02:44,080
só a 3 veces o factorial de 2?

59
00:02:44,080 --> 00:02:50,350
E o factorial de 4 é 4 veces
o factorial de 3, e así por diante?

60
00:02:50,350 --> 00:02:52,530
En realidade, o factorial
de calquera número pode só

61
00:02:52,530 --> 00:02:54,660
ser expresado si tipo
de realizalo la para sempre.

62
00:02:54,660 --> 00:02:56,870
Podemos tipo de xeneralizar
o problema factorial

63
00:02:56,870 --> 00:02:59,910
Como é n veces os
factorial de n menos 1.

64
00:02:59,910 --> 00:03:04,840
É n veces o produto
todos os números menos ca min.

65
00:03:04,840 --> 00:03:08,890
>> Esta idea, esta
xeneralización do problema,

66
00:03:08,890 --> 00:03:13,410
permítenos de forma recursiva
definir a función factorial.

67
00:03:13,410 --> 00:03:15,440
Cando define unha función
de forma recursiva, non hai

68
00:03:15,440 --> 00:03:17,470
dúas cousas que teñen que ser unha parte dela.

69
00:03:17,470 --> 00:03:20,990
Ten que ter unha cousa chamada
caso base, o que, cando active-lo,

70
00:03:20,990 --> 00:03:22,480
deter o proceso recursivo.

71
00:03:22,480 --> 00:03:25,300
>> Se non, unha función que chama
itself-- como pode imagine--

72
00:03:25,300 --> 00:03:26,870
podería ir para sempre.

73
00:03:26,870 --> 00:03:29,047
Función chama a función
chama chamadas de función

74
00:03:29,047 --> 00:03:30,380
a función chama a función.

75
00:03:30,380 --> 00:03:32,380
Se non ten unha forma
para-lo, o seu programa

76
00:03:32,380 --> 00:03:34,760
será efectivamente detido
en un loop infinito.

77
00:03:34,760 --> 00:03:37,176
Ha fallar eventualmente
porque só pode ir sen memoria.

78
00:03:37,176 --> 00:03:38,990
Pero iso non vén ao caso.

79
00:03:38,990 --> 00:03:42,210
>> Necesitamos a ter algunha outra forma de deixar
cousas alén do noso programa que deixa de funcionar,

80
00:03:42,210 --> 00:03:46,010
porque un programa que falla é
probablemente non bonito ou elegante.

81
00:03:46,010 --> 00:03:47,690
E así chamamos este escenario de base.

82
00:03:47,690 --> 00:03:50,610
Esta é unha solución sinxela
para un problema que para

83
00:03:50,610 --> 00:03:52,770
o proceso recursivo ocorra.

84
00:03:52,770 --> 00:03:55,220
Entón esta é unha parte da
unha función recursiva.

85
00:03:55,220 --> 00:03:56,820
>> A segunda parte é o caso recursiva.

86
00:03:56,820 --> 00:03:59,195
E é aquí onde a recursão
vai realmente ocorrer.

87
00:03:59,195 --> 00:04:02,200
Este é o lugar onde a
función pode chamar a si mesma.

88
00:04:02,200 --> 00:04:05,940
>> Non vai chamar-se exactamente
do mesmo xeito que foi chamado.

89
00:04:05,940 --> 00:04:08,880
Vai ser unha pequena variación
que fai que o problema é

90
00:04:08,880 --> 00:04:11,497
intentando resolver un pouquiño máis pequeno.

91
00:04:11,497 --> 00:04:14,330
Pero xeralmente pasa o fanfarrão
de resolver a maior parte da solución de

92
00:04:14,330 --> 00:04:17,450
para unha chamada diferente para abaixo da liña.

93
00:04:17,450 --> 00:04:20,290
>> Cal destes looks
como é o caso base aquí?

94
00:04:20,290 --> 00:04:25,384
Cal destes miradas como o
máis simple solución para un problema?

95
00:04:25,384 --> 00:04:27,550
Temos unha morea de factoriais,
e poderiamos seguir

96
00:04:27,550 --> 00:04:30,470
indo on-- 6, 7, 8, 9, 10, e así por diante.

97
00:04:30,470 --> 00:04:34,130
>> Pero un deses miradas como un
bo caso para ser o caso base.

98
00:04:34,130 --> 00:04:35,310
É unha solución moi sinxela.

99
00:04:35,310 --> 00:04:37,810
Non temos que facer nada especial.

100
00:04:37,810 --> 00:04:40,560
>> O factorial dun é un esbozo.

101
00:04:40,560 --> 00:04:42,790
Non temos que facer calquera
multiplicación de todo.

102
00:04:42,790 --> 00:04:45,248
Parece que se imos
para tratar de solucionar este problema,

103
00:04:45,248 --> 00:04:47,600
e necesitamos a deter o
recursão nalgún lugar,

104
00:04:47,600 --> 00:04:50,610
nós probablemente quere deixar
cando chegamos a 1.

105
00:04:50,610 --> 00:04:54,580
Non queremos deixar antes diso.

106
00:04:54,580 --> 00:04:56,660
>> Entón, se estamos definindo
nosa función factorial,

107
00:04:56,660 --> 00:04:58,690
aquí está un esqueleto para
como podemos facelo.

108
00:04:58,690 --> 00:05:03,110
Necesitamos conectar estes dous coisas-
o caso base eo caso recursiva.

109
00:05:03,110 --> 00:05:04,990
¿Que é o caso base?

110
00:05:04,990 --> 00:05:10,150
Se n é igual a 1, de regreso que é 1--
un problema moi sinxelo de resolver.

111
00:05:10,150 --> 00:05:11,890
>> O factorial dun é un.

112
00:05:11,890 --> 00:05:13,860
Non son 1 veces nada.

113
00:05:13,860 --> 00:05:15,020
É só un.

114
00:05:15,020 --> 00:05:17,170
É un feito moi fácil.

115
00:05:17,170 --> 00:05:19,620
E así que pode ser o noso caso base.

116
00:05:19,620 --> 00:05:24,730
Se conseguir pasar 1 a este
función, imos voltar 1.

117
00:05:24,730 --> 00:05:27,320
>> Cal é a recursiva
caso probablemente se parece?

118
00:05:27,320 --> 00:05:32,445
Para cada outro número
ademais de un, que é o patrón?

119
00:05:32,445 --> 00:05:35,780
Ben, se estamos tomando
o factorial de n,

120
00:05:35,780 --> 00:05:38,160
É n veces o factorial de n menos 1.

121
00:05:38,160 --> 00:05:42,130
>> Se estamos levando o factorial de 3,
é 3 veces o factorial de 3 menos 1,

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

123
00:05:43,070 --> 00:05:47,330
E por iso, se non estamos
mirando para un, se non,

124
00:05:47,330 --> 00:05:51,710
retorno n veces os
factorial de n menos 1.

125
00:05:51,710 --> 00:05:53,210
É moi sinxelo.

126
00:05:53,210 --> 00:05:57,360
>> E por unha cuestión de ter un pouco
máis limpo e máis elegante código,

127
00:05:57,360 --> 00:06:01,440
sabemos que si ten lazos de liña única
ou single liña desvíos condicionais,

128
00:06:01,440 --> 00:06:04,490
podemos librar de todos os
claves en torno a eles.

129
00:06:04,490 --> 00:06:06,850
Así, podemos consolidar esa a iso.

130
00:06:06,850 --> 00:06:09,640
Isto exactamente a mesma
como esta función.

131
00:06:09,640 --> 00:06:13,850
>> Eu só estou tirando o rizado
cintas, porque hai só unha liña

132
00:06:13,850 --> 00:06:18,500
dentro destes desvíos condicionais.

133
00:06:18,500 --> 00:06:21,160
Así, estes se comportan de forma idéntica.

134
00:06:21,160 --> 00:06:23,800
Se n é igual a 1, de regreso 1.

135
00:06:23,800 --> 00:06:28,351
Se non, voltar n veces
o factorial de n menos 1.

136
00:06:28,351 --> 00:06:29,850
Entón, nós estamos facendo o problema menor.

137
00:06:29,850 --> 00:06:33,850
Se n comeza como 5, imos
volver 5 veces o factorial de catro.

138
00:06:33,850 --> 00:06:37,100
E veremos nun minuto cando falamos
sobre a stack-- chamada noutro vídeo

139
00:06:37,100 --> 00:06:39,390
onde falamos sobre o
chamar stack-- imos aprender

140
00:06:39,390 --> 00:06:41,630
sobre por que exactamente ese proceso funciona.

141
00:06:41,630 --> 00:06:46,970
>> Pero mentres factorial de 5 di
volver 5 veces factorial de 4, e 4

142
00:06:46,970 --> 00:06:49,710
vai dicir, OK, así, retorno
4 veces o factorial de 3.

143
00:06:49,710 --> 00:06:51,737
E como se pode ver, estamos
tipo de aproximación 1.

144
00:06:51,737 --> 00:06:53,820
Estamos chegando máis preto e
máis preto dese caso base.

145
00:06:53,820 --> 00:06:58,180
>> E xa que se loita o caso base,
todas as funcións anteriores

146
00:06:58,180 --> 00:07:00,540
teño a resposta que estaban a buscar.

147
00:07:00,540 --> 00:07:03,900
Factorial de 2 estaba dicindo retorno
2 veces o factorial dun.

148
00:07:03,900 --> 00:07:06,760
Ben, factorial de 1 retorna 1.

149
00:07:06,760 --> 00:07:10,090
Así, o anuncio de convocatoria de factorial
2 pode volver 2 veces 1,

150
00:07:10,090 --> 00:07:13,980
e dar iso ao factorial
3, que está esperando por ese resultado.

151
00:07:13,980 --> 00:07:17,110
>> E, a continuación, pode calcular
O seu resultado, 3 veces 2 é 6,

152
00:07:17,110 --> 00:07:18,907
e devolve-lo ó factorial de 4.

153
00:07:18,907 --> 00:07:20,740
E, de novo, temos un
vídeo na pila de chamadas

154
00:07:20,740 --> 00:07:23,810
onde iso é ilustrado algo
máis que o que estou dicindo agora.

155
00:07:23,810 --> 00:07:25,300
Pero é iso.

156
00:07:25,300 --> 00:07:29,300
Isto por si só, é a solución de
calcular o factorial dun número.

157
00:07:29,300 --> 00:07:31,527
>> É só catro liñas de código.

158
00:07:31,527 --> 00:07:32,610
Iso é moi legal, non?

159
00:07:32,610 --> 00:07:35,480
É unha especie de sexy.

160
00:07:35,480 --> 00:07:38,580
>> Así, en xeral, pero non
sempre, unha función recursiva

161
00:07:38,580 --> 00:07:41,190
poden substituír un circuíto nunha
función non recursiva.

162
00:07:41,190 --> 00:07:46,100
Entón, aquí, de xeito conxunto, é o iterativo
versión da función factorial.

163
00:07:46,100 --> 00:07:49,650
Ambos calcule
exactamente o mesmo.

164
00:07:49,650 --> 00:07:52,170
>> Ambos calcular o factorial de n.

165
00:07:52,170 --> 00:07:54,990
A versión da esquerda
usa recursão para facelo.

166
00:07:54,990 --> 00:07:58,320
A versión á dereita
usa iteración para facelo.

167
00:07:58,320 --> 00:08:02,050
>> E observen, temos que declarar
unha variable dun produto enteiro.

168
00:08:02,050 --> 00:08:02,940
E entón nós loop.

169
00:08:02,940 --> 00:08:06,790
Así, sempre que n é maior que 0, nós
manter multiplicando este producto por n

170
00:08:06,790 --> 00:08:09,890
e diminuíndo n ata
calculamos o produto.

171
00:08:09,890 --> 00:08:14,600
Así, estas dúas funcións, de novo,
facer exactamente o mesmo.

172
00:08:14,600 --> 00:08:19,980
Pero eles non facelo en
exactamente igual.

173
00:08:19,980 --> 00:08:22,430
>> Agora, é posible
ter máis dunha base

174
00:08:22,430 --> 00:08:25,770
caso de un ou máis
caso recursiva, dependendo

175
00:08:25,770 --> 00:08:27,670
en que a función está intentando facer.

176
00:08:27,670 --> 00:08:31,650
Non é necesariamente só limitado a
un caso base ou a unha única recursiva

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

178
00:08:32,370 --> 00:08:35,320
Entón, un exemplo de algo
con varios casos base

179
00:08:35,320 --> 00:08:37,830
pode ser o o--
Secuencia de números de Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Ten que se lembrar de
días de escola primaria

181
00:08:41,549 --> 00:08:45,740
que a secuencia de Fibonacci defínese
isto-- como o primeiro elemento é 0.

182
00:08:45,740 --> 00:08:46,890
O segundo elemento é 1.

183
00:08:46,890 --> 00:08:49,230
Ambos estes son só por definición.

184
00:08:49,230 --> 00:08:55,920
>> A continuación, as demais elementos defínese
como a suma de n menos 1 e n menos 2.

185
00:08:55,920 --> 00:09:00,330
Así, o terceiro elemento
0 sería máis 1 é 1.

186
00:09:00,330 --> 00:09:03,280
E, a continuación, o cuarto elemento
sería o segundo elemento, 1,

187
00:09:03,280 --> 00:09:06,550
máis o terceiro elemento, 1.

188
00:09:06,550 --> 00:09:08,507
E iso sería 2.

189
00:09:08,507 --> 00:09:09,340
E así por diante e así por diante.

190
00:09:09,340 --> 00:09:11,680
>> Polo tanto, neste caso, temos dous casos base.

191
00:09:11,680 --> 00:09:14,850
Se n é igual a 1, 0 regreso.

192
00:09:14,850 --> 00:09:18,560
Se n é igual a 2, o retorno 1.

193
00:09:18,560 --> 00:09:25,930
Se non, o regreso de Fibonacci n
menos 1 máis Fibonacci n menos 2.

194
00:09:25,930 --> 00:09:27,180
>> Entón é iso varios casos base.

195
00:09:27,180 --> 00:09:29,271
E sobre varios casos recursiva?

196
00:09:29,271 --> 00:09:31,520
Así, hai algo
chamado a conxectura de Collatz.

197
00:09:31,520 --> 00:09:34,630
Non vou dicir,
vostede sabe o que é,

198
00:09:34,630 --> 00:09:38,170
porque é realmente o noso último
problema para este vídeo particular.

199
00:09:38,170 --> 00:09:43,220
E é o noso exercicio
para traballar en conxunto.

200
00:09:43,220 --> 00:09:46,760
>> Entón aquí está o que o
Collatz conxectura é--

201
00:09:46,760 --> 00:09:48,820
que se aplica a cada enteiro positivo.

202
00:09:48,820 --> 00:09:51,500
E especula que é
sempre pode volver

203
00:09:51,500 --> 00:09:55,060
1 se seguir estes pasos.

204
00:09:55,060 --> 00:09:57,560
Se n é 1, parar.

205
00:09:57,560 --> 00:10:00,070
Temos ao 1 se n é 1.

206
00:10:00,070 --> 00:10:05,670
>> Se non, pasar por iso
proceso de novo en N dividida por 2.

207
00:10:05,670 --> 00:10:08,200
E vexa se pode obter de volta a 1.

208
00:10:08,200 --> 00:10:13,260
Se non, se n é impar, pasar por
este proceso unha vez en 3N + 1,

209
00:10:13,260 --> 00:10:15,552
ou 3 veces n máis 1.

210
00:10:15,552 --> 00:10:17,010
Entón aquí temos un único caso base.

211
00:10:17,010 --> 00:10:18,430
Se n é igual a 1, pare.

212
00:10:18,430 --> 00:10:20,230
Non estamos facendo máis recursão.

213
00:10:20,230 --> 00:10:23,730
>> Pero temos dous casos recursiva.

214
00:10:23,730 --> 00:10:28,750
Se n é par, nós facemos unha recursiva
caso, chamando n dividido por dous.

215
00:10:28,750 --> 00:10:33,950
Se n é impar, facemos unha diferente
caso recursiva en 3 veces n máis 1.

216
00:10:33,950 --> 00:10:39,120
>> E así, o obxectivo para este vídeo é
para tomar unha segunda, deter o vídeo,

217
00:10:39,120 --> 00:10:42,440
e tentar escribir este
función recursiva Collatz

218
00:10:42,440 --> 00:10:47,640
onde pasar un valor n, e
el calcula cantos pasos

219
00:10:47,640 --> 00:10:52,430
leva para chegar a 1 se comezar a partir de n
e seguir os pasos anteriores.

220
00:10:52,430 --> 00:10:56,660
Se n é 1, que leva 0 etapas.

221
00:10:56,660 --> 00:11:00,190
Se non, vai
dar un paso máis con todo

222
00:11:00,190 --> 00:11:06,200
moitos pasos que ten en ambos os n
dividido por 2, se n é par, ou 3N +1

223
00:11:06,200 --> 00:11:08,100
se n é impar.

224
00:11:08,100 --> 00:11:11,190
>> Agora, eu coloque na pantalla aquí
un par de cousas proba para ti,

225
00:11:11,190 --> 00:11:15,690
un par de probas de casos para ti, a ver
o que estes varios números de Collatz son,

226
00:11:15,690 --> 00:11:17,440
e tamén unha ilustración
de que os pasos

227
00:11:17,440 --> 00:11:20,390
teñen que ser atravesado para que poida
tipo de ver este proceso en acción.

228
00:11:20,390 --> 00:11:24,222
Así, se n é igual a
1, Collatz de n é 0.

229
00:11:24,222 --> 00:11:26,180
Non ten que facer
algo para volver a 1.

230
00:11:26,180 --> 00:11:27,600
Xa está aí.

231
00:11:27,600 --> 00:11:30,550
>> Se n é 2, que leva
un paso para chegar a 1.

232
00:11:30,550 --> 00:11:31,810
Comeza con dous.

233
00:11:31,810 --> 00:11:33,100
Ben, 2 non é igual a 1.

234
00:11:33,100 --> 00:11:36,580
Por iso, será un paso
con todo, máis moitos pasos de TI

235
00:11:36,580 --> 00:11:38,015
n asume dividida por 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 divídese por 2 1.

238
00:11:42,910 --> 00:11:47,200
Por iso, dá un paso máis con todo
moitos pasos que leva a 1.

239
00:11:47,200 --> 00:11:49,720
1 comporta de cero pasos.

240
00:11:49,720 --> 00:11:52,370
>> Para 3, como se pode ver, hai
moi poucos pasos implicados.

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

242
00:11:53,590 --> 00:11:56,710
E entón vai para
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Leva sete pasos para volver a un.

244
00:11:58,804 --> 00:12:01,220
E como se pode ver, hai unha
algúns outros casos de proba aquí

245
00:12:01,220 --> 00:12:02,470
para probar o seu programa.

246
00:12:02,470 --> 00:12:03,970
Entón, de novo, deter o vídeo.

247
00:12:03,970 --> 00:12:09,210
E eu vou ir para atrás agora
o que o proceso real é aquí,

248
00:12:09,210 --> 00:12:11,390
o que é esa conxectura.

249
00:12:11,390 --> 00:12:14,140
>> Vexa se pode descubrir
como configurar Collatz n

250
00:12:14,140 --> 00:12:19,967
de xeito que calcula cantos
os pasos que leva para chegar a 1.

251
00:12:19,967 --> 00:12:23,050
Polo tanto, esperamos que, fixo unha pausa o vídeo
e non están só esperando por min

252
00:12:23,050 --> 00:12:25,820
para darlle a resposta aquí.

253
00:12:25,820 --> 00:12:29,120
Pero se é así,
aquí está a resposta de todos os xeitos.

254
00:12:29,120 --> 00:12:33,070
>> Entón aquí está unha posible definición
da función Collatz.

255
00:12:33,070 --> 00:12:35,610
Nosa base case-- se n é
igual a 1, volvemos 0.

256
00:12:35,610 --> 00:12:38,250
Non hai que calquera
pasos para obter de volta a un.

257
00:12:38,250 --> 00:12:42,710
>> Se non, temos dous cases-- recursiva
unha para números pares e outro para impar.

258
00:12:42,710 --> 00:12:47,164
O xeito que eu probar a números pares
é verificar que n mod 2 é igual a 0.

259
00:12:47,164 --> 00:12:49,080
Isto é, basicamente, unha vez máis,
facer a pregunta,

260
00:12:49,080 --> 00:12:54,050
se recorda o que é-- mod si
divide n por 2 que non hai resto?

261
00:12:54,050 --> 00:12:55,470
Iso sería un número par.

262
00:12:55,470 --> 00:13:01,370
>> E por iso, se n mod 2 é igual a 0 é
proba é este un número par.

263
00:13:01,370 --> 00:13:04,250
Se é así, eu quero volver 1,
porque este é sempre

264
00:13:04,250 --> 00:13:09,270
dando un paso máis aló de Collatz
o que número é metade de min.

265
00:13:09,270 --> 00:13:13,910
Se non, eu quero volver 1
ademais de Collatz de 3 veces n máis 1.

266
00:13:13,910 --> 00:13:16,060
Esa foi a outra
mentres que recursiva

267
00:13:16,060 --> 00:13:19,470
podería tomar para calcular o
Collatz-- o número de pasos

268
00:13:19,470 --> 00:13:22,610
fai falta para volver
1 dado un número.

269
00:13:22,610 --> 00:13:24,610
Polo tanto, esperamos que este exemplo
deulle un pouco

270
00:13:24,610 --> 00:13:26,620
dun gusto de procedementos recursiva.

271
00:13:26,620 --> 00:13:30,220
Con sorte, pensas que é un código
pouco máis bonito se aplicado

272
00:13:30,220 --> 00:13:32,760
dunha forma elegante, recursiva.

273
00:13:32,760 --> 00:13:35,955
Pero aínda que non, a recursividade é unha
realmente poderosa ferramenta, con todo.

274
00:13:35,955 --> 00:13:38,330
E por iso é sempre algo
para obter a súa cabeza en torno,

275
00:13:38,330 --> 00:13:41,360
porque vai ser capaz de crear
programas moi legal usando recursão

276
00:13:41,360 --> 00:13:45,930
que doutro xeito poderían ser complexo para escribir
se está a usar loops e iteración.

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

278
00:13:46,980 --> 00:13:48,780
Este é CS50.

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