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

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Usted probablemente piensa que
código sólo se utiliza para realizar una tarea.

3
00:00:09,530 --> 00:00:10,450
Usted escribe a cabo.

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

5
00:00:11,664 --> 00:00:12,580
Eso es practicamente todo.

6
00:00:12,580 --> 00:00:13,160
>> Usted compilarlo.

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

8
00:00:13,993 --> 00:00:15,370
Usted está bueno para ir.

9
00:00:15,370 --> 00:00:17,520
>> Pero lo creas o no, si
codificar por un largo tiempo,

10
00:00:17,520 --> 00:00:20,550
en realidad se puede llegar a ver
código como algo que es hermoso.

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

12
00:00:23,275 --> 00:00:26,510
o hay algo de verdad
aseada sobre la forma en que se ve.

13
00:00:26,510 --> 00:00:28,750
Usted podría estar riendo
a mí, pero es la verdad.

14
00:00:28,750 --> 00:00:31,530
Y recursividad es una forma
para conseguir una especie de esta idea

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

16
00:00:34,090 --> 00:00:37,740
Soluciona problemas de manera que
son interesantes, fácil de visualizar,

17
00:00:37,740 --> 00:00:39,810
y sorprendentemente corto.

18
00:00:39,810 --> 00:00:43,190
>> Las obras manera recursividad
es, una función recursiva

19
00:00:43,190 --> 00:00:49,291
se define como una función que llama
a sí misma como parte de su ejecución.

20
00:00:49,291 --> 00:00:51,790
Esto puede parecer un poco extraño,
y vamos a ver un poco

21
00:00:51,790 --> 00:00:53,750
acerca de cómo funciona esto en un momento.

22
00:00:53,750 --> 00:00:55,560
Pero, de nuevo, estos
procedimientos recursivos son

23
00:00:55,560 --> 00:00:57,730
va a ser tan elegante
porque van

24
00:00:57,730 --> 00:01:00,410
para resolver este problema sin
teniendo todas estas otras funciones

25
00:01:00,410 --> 00:01:02,710
o estos largos bucles.

26
00:01:02,710 --> 00:01:06,310
Vas a ver que éstos recursiva
procedimientos van a parecer tan corto.

27
00:01:06,310 --> 00:01:10,610
Y realmente se va a hacer
su código parecen mucho más hermosa.

28
00:01:10,610 --> 00:01:12,560
>> Te voy a dar un ejemplo
de esto para ver cómo

29
00:01:12,560 --> 00:01:14,880
un procedimiento recursivo puede definirse.

30
00:01:14,880 --> 00:01:18,202
Así que si usted está familiarizado con este
de la clase de matemáticas, hace muchos años,

31
00:01:18,202 --> 00:01:20,910
Hay algo llamado el
función factorial, que es generalmente

32
00:01:20,910 --> 00:01:25,340
denotado como un signo de exclamación, que
se define sobre todos los enteros positivos.

33
00:01:25,340 --> 00:01:28,850
Y la forma en que n
factorial se calcula

34
00:01:28,850 --> 00:01:31,050
está usted multiplica todos
los números de menos de

35
00:01:31,050 --> 00:01:33,750
o igual a n juntos--
todos los números enteros de menos de

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

37
00:01:34,880 --> 00:01:39,850
>> Así 5 factorial es 5 veces
4 veces 3 veces 2 veces 1.

38
00:01:39,850 --> 00:01:43,020
Y 4 factorial es 4 veces
3 veces 2 veces 1 y así sucesivamente.

39
00:01:43,020 --> 00:01:44,800
Usted consigue la idea.

40
00:01:44,800 --> 00:01:47,060
>> Como programadores, no lo hacemos
utilizar n, signo de exclamación.

41
00:01:47,060 --> 00:01:51,840
Así que vamos a definir el factorial
función como un hecho de n.

42
00:01:51,840 --> 00:01:56,897
Y vamos a utilizar factorial para crear
una solución recursiva a un problema.

43
00:01:56,897 --> 00:01:59,230
Y creo que podría encontrar
que es mucho más visual

44
00:01:59,230 --> 00:02:02,380
apelando a la iterativa
versión de este, el cual

45
00:02:02,380 --> 00:02:05,010
también vamos a echar un vistazo a en un momento.

46
00:02:05,010 --> 00:02:08,310
>> Así que aquí hay un par de
juego de palabras facts-- intended--

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

48
00:02:10,169 --> 00:02:13,090
El factorial de 1, como ya he dicho, es 1.

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

50
00:02:15,690 --> 00:02:18,470
El factorial de 3 es 3
Tiempos 2 Tiempos 1, y así sucesivamente.

51
00:02:18,470 --> 00:02:20,810
Hablamos de 4 y 5 ya.

52
00:02:20,810 --> 00:02:23,940
>> Pero al mirar a esto, no es esto cierto?

53
00:02:23,940 --> 00:02:28,220
¿No es el factorial de 2 solo
2 veces el factorial de 1?

54
00:02:28,220 --> 00:02:31,130
Quiero decir, el factorial de 1 es 1.

55
00:02:31,130 --> 00:02:34,940
¿Por qué no podemos simplemente decir que,
desde factorial de 2 es 2 veces 1,

56
00:02:34,940 --> 00:02:38,520
es realmente sólo 2 veces
el factorial de 1?

57
00:02:38,520 --> 00:02:40,900
>> Y luego extender esa idea,
no es el factorial de 3

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

59
00:02:44,080 --> 00:02:50,350
Y el factorial de 4 es 4 veces
el factorial de 3, y así sucesivamente?

60
00:02:50,350 --> 00:02:52,530
De hecho, el factorial
de cualquier número puede simplemente

61
00:02:52,530 --> 00:02:54,660
ser expresada si especie
de llevar esto a cabo siempre.

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

63
00:02:56,870 --> 00:02:59,910
ya que es n veces los
factorial de n menos 1.

64
00:02:59,910 --> 00:03:04,840
Es n veces el producto de
todos los números menores que yo.

65
00:03:04,840 --> 00:03:08,890
>> Esta idea, esto
generalización del problema,

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

67
00:03:13,410 --> 00:03:15,440
Cuando se define una función
recursiva, hay

68
00:03:15,440 --> 00:03:17,470
dos cosas que deben ser parte de ella.

69
00:03:17,470 --> 00:03:20,990
Usted necesita tener algo llamado
caso base, que, cuando usted los activa,

70
00:03:20,990 --> 00:03:22,480
se detendrá el proceso recursivo.

71
00:03:22,480 --> 00:03:25,300
>> De lo contrario, una función que llama
itself-- como se podría imagine--

72
00:03:25,300 --> 00:03:26,870
podría continuar para siempre.

73
00:03:26,870 --> 00:03:29,047
Función llama a la función
llama a las llamadas de función

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

75
00:03:30,380 --> 00:03:32,380
Si usted no tiene una forma
para detenerlo, su programa

76
00:03:32,380 --> 00:03:34,760
será atrapado con eficacia
en un bucle infinito.

77
00:03:34,760 --> 00:03:37,176
Será estrellarse finalmente,
porque va a quedarse sin memoria.

78
00:03:37,176 --> 00:03:38,990
Pero eso no viene al caso.

79
00:03:38,990 --> 00:03:42,210
>> Tenemos que tener alguna otra forma de detener
cosas además de nuestro programa de estrellarse,

80
00:03:42,210 --> 00:03:46,010
porque un programa que se estrella es
Probablemente no es bello o elegante.

81
00:03:46,010 --> 00:03:47,690
Y así lo llamamos el caso base.

82
00:03:47,690 --> 00:03:50,610
Esta es una solución simple
a un problema que se detiene

83
00:03:50,610 --> 00:03:52,770
el proceso recursivo que se produzcan.

84
00:03:52,770 --> 00:03:55,220
Así que esa es una parte de
una función recursiva.

85
00:03:55,220 --> 00:03:56,820
>> La segunda parte es el caso recursivo.

86
00:03:56,820 --> 00:03:59,195
Y aquí es donde la recursividad
en realidad tener lugar.

87
00:03:59,195 --> 00:04:02,200
Aquí es donde el
función se llame a sí mismo.

88
00:04:02,200 --> 00:04:05,940
>> No va a llamarse exactamente
de la misma manera que se llamaba.

89
00:04:05,940 --> 00:04:08,880
Será una ligera variación
que hace que el problema es

90
00:04:08,880 --> 00:04:11,497
tratando de resolver un poquitín más pequeño.

91
00:04:11,497 --> 00:04:14,330
Pero en general, pasa la pelota
de resolver la mayor parte de la solución

92
00:04:14,330 --> 00:04:17,450
a una llamada diferente en la línea.

93
00:04:17,450 --> 00:04:20,290
>> ¿Cuál de estos looks
como el caso base en esta lista?

94
00:04:20,290 --> 00:04:25,384
¿Cuál de estos looks como el
solución más sencilla a un problema?

95
00:04:25,384 --> 00:04:27,550
Tenemos un montón de factoriales,
y podríamos continuar

96
00:04:27,550 --> 00:04:30,470
ir en-- 6, 7, 8, 9, 10, y así sucesivamente.

97
00:04:30,470 --> 00:04:34,130
>> Pero uno de estos parece un
buen caso es el caso base.

98
00:04:34,130 --> 00:04:35,310
Es una solución muy simple.

99
00:04:35,310 --> 00:04:37,810
No tenemos que hacer nada especial.

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

101
00:04:40,560 --> 00:04:42,790
No tenemos que hacer ningún
multiplicación en absoluto.

102
00:04:42,790 --> 00:04:45,248
Parece como si vamos
para tratar de resolver este problema,

103
00:04:45,248 --> 00:04:47,600
y tenemos que detener la
recursividad en alguna parte,

104
00:04:47,600 --> 00:04:50,610
probablemente queremos parar
cuando llegamos a 1.

105
00:04:50,610 --> 00:04:54,580
No queremos que se detenga antes de eso.

106
00:04:54,580 --> 00:04:56,660
>> Así que si estamos definiendo
nuestra función factorial,

107
00:04:56,660 --> 00:04:58,690
aquí está un esqueleto para
cómo podemos hacer eso.

108
00:04:58,690 --> 00:05:03,110
Tenemos que conectar esos dos cosas--
el caso base y el caso recursivo.

109
00:05:03,110 --> 00:05:04,990
¿Cuál es el caso base?

110
00:05:04,990 --> 00:05:10,150
Si n es igual a 1, volver 1-- eso es
un problema muy simple de resolver.

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

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

113
00:05:13,860 --> 00:05:15,020
Es sólo 1.

114
00:05:15,020 --> 00:05:17,170
Es un hecho muy fácil.

115
00:05:17,170 --> 00:05:19,620
Y para que pueda ser nuestro caso base.

116
00:05:19,620 --> 00:05:24,730
Si nos pasamos 1 en este
función, sólo tendremos que regresemos 1.

117
00:05:24,730 --> 00:05:27,320
>> ¿Cuál es la recursiva
caso probablemente parece?

118
00:05:27,320 --> 00:05:32,445
Por cada otro número
además de 1, ¿cuál es el patrón?

119
00:05:32,445 --> 00:05:35,780
Bueno, si estamos tomando
el factorial de n,

120
00:05:35,780 --> 00:05:38,160
Es en momentos n el factorial de n menos 1.

121
00:05:38,160 --> 00:05:42,130
>> Si estamos tomando el factorial de 3,
que es 3 veces el factorial de 3 menos 1,

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

123
00:05:43,070 --> 00:05:47,330
Y por lo que si no estamos
mirando a 1, de lo contrario

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

125
00:05:51,710 --> 00:05:53,210
Es bastante sencillo.

126
00:05:53,210 --> 00:05:57,360
>> Y por el bien de tener un poco
más limpia y más elegante de código,

127
00:05:57,360 --> 00:06:01,440
saber que si tenemos bucles de una sola línea
o de una sola línea de saltos condicionales,

128
00:06:01,440 --> 00:06:04,490
podemos deshacernos de toda la
llaves alrededor de ellos.

129
00:06:04,490 --> 00:06:06,850
Así que podemos consolidar este a esto.

130
00:06:06,850 --> 00:06:09,640
Esto tiene exactamente el mismo
funcionalidad que esto.

131
00:06:09,640 --> 00:06:13,850
>> Sólo estoy quitando el rizado
apoyos, porque sólo hay una línea

132
00:06:13,850 --> 00:06:18,500
dentro de esas ramas condicionales.

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

134
00:06:21,160 --> 00:06:23,800
Si n es igual a 1, volver 1.

135
00:06:23,800 --> 00:06:28,351
De lo contrario volverá n veces
el factorial de n menos 1.

136
00:06:28,351 --> 00:06:29,850
Así que estamos haciendo el problema más pequeño.

137
00:06:29,850 --> 00:06:33,850
Si n comienza como 5, vamos a
volver 5 veces el factorial de 4.

138
00:06:33,850 --> 00:06:37,100
Y veremos en un minuto cuando hablamos
acerca de la stack-- llamada en otro video

139
00:06:37,100 --> 00:06:39,390
donde se habla de la
llamar stack-- aprenderemos

140
00:06:39,390 --> 00:06:41,630
acerca de por qué exactamente este proceso funciona.

141
00:06:41,630 --> 00:06:46,970
>> Pero mientras factorial de 5 dice
volver 5 veces factorial de 4, y 4

142
00:06:46,970 --> 00:06:49,710
se va a decir, bien, bien, el regreso
4 veces el factorial de 3.

143
00:06:49,710 --> 00:06:51,737
Y como se puede ver, estamos
tipo de acercarse a 1.

144
00:06:51,737 --> 00:06:53,820
Estamos cada vez más cerca y
más cercana a la del caso base.

145
00:06:53,820 --> 00:06:58,180
>> Y una vez que llegamos a la hipótesis de base,
todas las funciones anteriores

146
00:06:58,180 --> 00:07:00,540
tener la respuesta que estaban buscando.

147
00:07:00,540 --> 00:07:03,900
Factorial de 2 estaba diciendo retorno
2 veces el factorial de 1.

148
00:07:03,900 --> 00:07:06,760
Bueno, factorial de 1 devuelve 1.

149
00:07:06,760 --> 00:07:10,090
Así que la convocatoria de factorial
de 2 puede volver 2 veces 1,

150
00:07:10,090 --> 00:07:13,980
y dar esa vuelta a factorial de
3, que está a la espera de ese resultado.

151
00:07:13,980 --> 00:07:17,110
>> Y entonces se puede calcular
su resultado, 3 veces 2 es 6,

152
00:07:17,110 --> 00:07:18,907
y darle vuelta a factorial de 4.

153
00:07:18,907 --> 00:07:20,740
Y de nuevo, tenemos una
video en la pila de llamadas

154
00:07:20,740 --> 00:07:23,810
donde esto se ilustra un poco
más de lo que estoy diciendo ahora.

155
00:07:23,810 --> 00:07:25,300
Pero eso es todo.

156
00:07:25,300 --> 00:07:29,300
Esto por sí solo es la solución a
calcular el factorial de un número.

157
00:07:29,300 --> 00:07:31,527
>> Es sólo cuatro líneas de código.

158
00:07:31,527 --> 00:07:32,610
Eso está muy bien, ¿verdad?

159
00:07:32,610 --> 00:07:35,480
Es un poco sexy.

160
00:07:35,480 --> 00:07:38,580
>> Así que en general, pero no
siempre, una función recursiva

161
00:07:38,580 --> 00:07:41,190
puede sustituir a un bucle en una
función no recursiva.

162
00:07:41,190 --> 00:07:46,100
Así que aquí, al lado del otro, es el iterativo
versión de la función factorial.

163
00:07:46,100 --> 00:07:49,650
Ambos calcular
exactamente lo mismo.

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

165
00:07:52,170 --> 00:07:54,990
La versión de la izquierda
utiliza la recursividad para hacerlo.

166
00:07:54,990 --> 00:07:58,320
La versión a la derecha
utiliza iteración para hacerlo.

167
00:07:58,320 --> 00:08:02,050
>> Y fíjense, tenemos que declarar
una variable de un producto entero.

168
00:08:02,050 --> 00:08:02,940
Y luego nos bucle.

169
00:08:02,940 --> 00:08:06,790
Siempre y cuando n es mayor que 0, se
continuar multiplicándose ese producto por n

170
00:08:06,790 --> 00:08:09,890
y decrementar n hasta
calculamos el producto.

171
00:08:09,890 --> 00:08:14,600
Así pues, estas dos funciones, una vez más,
hacer exactamente lo mismo.

172
00:08:14,600 --> 00:08:19,980
Pero ellos no lo hacen en
exactamente de la misma manera.

173
00:08:19,980 --> 00:08:22,430
>> Ahora, es posible
tener más de una base de

174
00:08:22,430 --> 00:08:25,770
caso o más de una
caso recursivo, dependiendo

175
00:08:25,770 --> 00:08:27,670
en lo que su función está tratando de hacer.

176
00:08:27,670 --> 00:08:31,650
Usted no está necesariamente sólo limitado a
un solo caso base o un solo recursiva

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

178
00:08:32,370 --> 00:08:35,320
Así que un ejemplo de algo
con múltiples casos base

179
00:08:35,320 --> 00:08:37,830
podría ser la esto-
Serie de Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Usted puede recordar de
días de escuela primaria

181
00:08:41,549 --> 00:08:45,740
que la secuencia de Fibonacci se define
así- el primer elemento es 0.

182
00:08:45,740 --> 00:08:46,890
El segundo elemento es 1.

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

184
00:08:49,230 --> 00:08:55,920
>> Entonces se define todos los demás elementos
como la suma de n menos 1 y n menos 2.

185
00:08:55,920 --> 00:09:00,330
Así que el tercer elemento
sería 0 + 1 es 1.

186
00:09:00,330 --> 00:09:03,280
Y entonces el cuarto elemento
sería el segundo elemento, 1,

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

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

189
00:09:08,507 --> 00:09:09,340
Y así sucesivamente y así sucesivamente.

190
00:09:09,340 --> 00:09:11,680
>> Así que en este caso, tenemos dos casos base.

191
00:09:11,680 --> 00:09:14,850
Si n es igual a 1, devuelve 0.

192
00:09:14,850 --> 00:09:18,560
Si n es igual a 2, volver 1.

193
00:09:18,560 --> 00:09:25,930
De lo contrario, vuelva Fibonacci de n
menos 1 más de Fibonacci de n menos 2.

194
00:09:25,930 --> 00:09:27,180
>> Así que eso es varios casos base.

195
00:09:27,180 --> 00:09:29,271
¿Qué pasa con múltiples casos recurrentes?

196
00:09:29,271 --> 00:09:31,520
Bueno, hay algo
llama la conjetura de Collatz.

197
00:09:31,520 --> 00:09:34,630
Yo no voy a decir,
usted sabe lo que es eso,

198
00:09:34,630 --> 00:09:38,170
porque en realidad es nuestro último
problema para este video en particular.

199
00:09:38,170 --> 00:09:43,220
Y es nuestro ejercicio
para trabajar juntos.

200
00:09:43,220 --> 00:09:46,760
>> Así que aquí está lo que el
Collatz conjetura es--

201
00:09:46,760 --> 00:09:48,820
que se aplica a cada número entero positivo.

202
00:09:48,820 --> 00:09:51,500
Y especula que es
siempre es posible volver

203
00:09:51,500 --> 00:09:55,060
1 si usted sigue estos pasos.

204
00:09:55,060 --> 00:09:57,560
Si n es 1, para.

205
00:09:57,560 --> 00:10:00,070
Tenemos de nuevo a 1 si n es 1.

206
00:10:00,070 --> 00:10:05,670
>> De lo contrario, vaya a través de este
proceso de nuevo en n dividido por 2.

207
00:10:05,670 --> 00:10:08,200
Y ver si puede volver a 1.

208
00:10:08,200 --> 00:10:13,260
De lo contrario, si n es impar, ir a través de
este proceso nuevo en 3n más 1,

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

210
00:10:15,552 --> 00:10:17,010
Así que aquí tenemos un caso base.

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

212
00:10:18,430 --> 00:10:20,230
No estamos haciendo nada más recursividad.

213
00:10:20,230 --> 00:10:23,730
>> Pero tenemos dos casos recursivas.

214
00:10:23,730 --> 00:10:28,750
Si n es par, lo hacemos de un recursivo
caso, llamando n dividido por 2.

215
00:10:28,750 --> 00:10:33,950
Si n es impar, hacemos un diferente
caso recursivo en 3 veces N más 1.

216
00:10:33,950 --> 00:10:39,120
>> Y lo que el objetivo de este vídeo es
tomar un segundo, hacer una pausa en el video,

217
00:10:39,120 --> 00:10:42,440
y tratar de escribir este
función recursiva Collatz

218
00:10:42,440 --> 00:10:47,640
donde se pasa en un valor n, y
calcula cuántos pasos

219
00:10:47,640 --> 00:10:52,430
toma para llegar a 1 si se inicia a partir de n
y usted sigue estos pasos hasta arriba.

220
00:10:52,430 --> 00:10:56,660
Si n es 1, se tarda 0 pasos.

221
00:10:56,660 --> 00:11:00,190
De lo contrario, se va a
dar un paso más sin embargo

222
00:11:00,190 --> 00:11:06,200
muchos pasos que se necesita en cada n
dividido por 2 si n es par, o 3n plus 1

223
00:11:06,200 --> 00:11:08,100
si n es impar.

224
00:11:08,100 --> 00:11:11,190
>> Ahora, me he puesto en la pantalla aquí
un par de cosas de prueba para usted,

225
00:11:11,190 --> 00:11:15,690
un par de pruebas de casos para usted, para ver
lo que estos diversos números Collatz son,

226
00:11:15,690 --> 00:11:17,440
y también una ilustración
de los pasos que

227
00:11:17,440 --> 00:11:20,390
necesitan ser pasado por lo que puede
suerte de ver este proceso en acción.

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

229
00:11:24,222 --> 00:11:26,180
Usted no tiene que ver
cualquier cosa para conseguir de nuevo a 1.

230
00:11:26,180 --> 00:11:27,600
Usted es ya allí.

231
00:11:27,600 --> 00:11:30,550
>> Si n es 2, se necesita
un paso para llegar a 1.

232
00:11:30,550 --> 00:11:31,810
Se empieza con 2.

233
00:11:31,810 --> 00:11:33,100
Bueno, 2 no es igual a 1.

234
00:11:33,100 --> 00:11:36,580
Así que va a ser un paso
más sin embargo muchas medidas que

235
00:11:36,580 --> 00:11:38,015
adquiere n dividido por 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 dividido por 2 es 1.

238
00:11:42,910 --> 00:11:47,200
Así que toma un paso más sin embargo
muchos pasos que tarda 1.

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

240
00:11:49,720 --> 00:11:52,370
>> Para 3, como se puede ver, no hay
unos cuantos pasos involucrados.

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

242
00:11:53,590 --> 00:11:56,710
Y luego vas a
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Lleva siete pasos para volver a 1.

244
00:11:58,804 --> 00:12:01,220
Y como se puede ver, hay una
par de otros casos de prueba aquí

245
00:12:01,220 --> 00:12:02,470
para poner a prueba su programa.

246
00:12:02,470 --> 00:12:03,970
Así que de nuevo, hacer una pausa en el vídeo.

247
00:12:03,970 --> 00:12:09,210
Y yo iré a saltar de nuevo ahora
lo que el proceso real está aquí,

248
00:12:09,210 --> 00:12:11,390
lo que esta conjetura es.

249
00:12:11,390 --> 00:12:14,140
>> A ver si puedes averiguar
cómo definir Collatz de n

250
00:12:14,140 --> 00:12:19,967
de modo que calcula cuántos
los pasos que se necesita para llegar a 1.

251
00:12:19,967 --> 00:12:23,050
Así que espero que, de haber detenido el video
y no está a la espera de mí

252
00:12:23,050 --> 00:12:25,820
para darle la respuesta aquí.

253
00:12:25,820 --> 00:12:29,120
Pero si usted es, así,
aquí está la respuesta de todos modos.

254
00:12:29,120 --> 00:12:33,070
>> Así que aquí está una posible definición
de la función de Collatz.

255
00:12:33,070 --> 00:12:35,610
Nuestra base caso-- si n es
igual a 1, volvemos 0.

256
00:12:35,610 --> 00:12:38,250
No se necesita ninguna
pasos para llegar de nuevo a 1.

257
00:12:38,250 --> 00:12:42,710
>> De lo contrario, tenemos dos casos-- recursiva
una para los números pares y otro para impar.

258
00:12:42,710 --> 00:12:47,164
La forma en que la prueba de números pares
es comprobar si n mod 2 es igual a 0.

259
00:12:47,164 --> 00:12:49,080
Esto es básicamente, una vez más,
hacer la pregunta,

260
00:12:49,080 --> 00:12:54,050
si usted recuerda lo es-- mod si
dividir n por 2 hay ningún resto?

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

262
00:12:55,470 --> 00:13:01,370
>> Y así, si n mod 2 es igual a 0 es
esta prueba es un número par.

263
00:13:01,370 --> 00:13:04,250
Si es así, quiero regresar 1,
porque este es, sin duda

264
00:13:04,250 --> 00:13:09,270
dando un paso más Collatz de
cualquiera que sea el número es la mitad de mí.

265
00:13:09,270 --> 00:13:13,910
De lo contrario, quiero volver 1
más Collatz de 3 veces n más 1.

266
00:13:13,910 --> 00:13:16,060
Esa fue la otra
paso recursivo que nos

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

268
00:13:19,470 --> 00:13:22,610
que se necesita para volver
a 1 dado un número.

269
00:13:22,610 --> 00:13:24,610
Así que espero que este ejemplo
Le dio un poco

270
00:13:24,610 --> 00:13:26,620
de una muestra de procedimientos recursivos.

271
00:13:26,620 --> 00:13:30,220
Con suerte, usted piensa código es un
poco más hermosa si se aplican

272
00:13:30,220 --> 00:13:32,760
de una manera elegante, recursivo.

273
00:13:32,760 --> 00:13:35,955
Pero incluso si no, la recursividad es una
herramienta realmente poderosa, no obstante.

274
00:13:35,955 --> 00:13:38,330
Y lo que es definitivamente algo
para obtener su cabeza alrededor,

275
00:13:38,330 --> 00:13:41,360
porque usted será capaz de crear
programas muy interesantes utilizando recursividad

276
00:13:41,360 --> 00:13:45,930
que de otra manera podría ser complejo para escribir
si usted está utilizando loops y iteración.

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

278
00:13:46,980 --> 00:13:48,780
Esto es CS50.

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