1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Con el fin de entender
recursividad, se debe

3
00:00:10,190 --> 00:00:13,820
primero entender la recursividad.

4
00:00:13,820 --> 00:00:17,280
Tener la recursividad en el programa de diseño de medios
que tiene autorreferencial

5
00:00:17,280 --> 00:00:18,570
definiciones.

6
00:00:18,570 --> 00:00:21,520
Estructuras de datos recursivas, por ejemplo,
son estructuras de datos que

7
00:00:21,520 --> 00:00:23,990
incluir a sí mismos en
sus definiciones.

8
00:00:23,990 --> 00:00:27,160
Pero hoy en día, nos vamos a centrar
en funciones recursivas.

9
00:00:27,160 --> 00:00:31,160
>> Recordemos que las funciones necesitan insumos,
argumentos y devuelve un valor como su

10
00:00:31,160 --> 00:00:34,480
de salida representado por
este diagrama aquí.

11
00:00:34,480 --> 00:00:38,060
Ya pensaremos en la caja como el cuerpo de
la función, que contiene el conjunto de

12
00:00:38,060 --> 00:00:42,340
instrucciones que interpretan el
de entrada y proporcionar una salida.

13
00:00:42,340 --> 00:00:45,660
Tomando una mirada más cercana en el interior del cuerpo de
la función podría revelar las llamadas a

14
00:00:45,660 --> 00:00:47,430
otras funciones también.

15
00:00:47,430 --> 00:00:51,300
Tome esta función simple, foo, que
toma una sola cadena como entrada y

16
00:00:51,300 --> 00:00:54,630
impresiones de cuántas letras
esa cadena tiene.

17
00:00:54,630 --> 00:00:58,490
El strlen función, por longitud de la cadena,
se llama, cuya salida es

18
00:00:58,490 --> 00:01:01,890
requerido para la llamada a printf.

19
00:01:01,890 --> 00:01:05,770
>> Ahora, lo que hace una función recursiva
especial es que se llama a sí misma.

20
00:01:05,770 --> 00:01:09,610
Podemos representar este recursiva
llamar con esta flecha naranja

21
00:01:09,610 --> 00:01:11,360
bucle de nuevo a sí mismo.

22
00:01:11,360 --> 00:01:15,630
Pero la ejecución en sí de nuevo sólo se
realizar otra llamada recursiva, y

23
00:01:15,630 --> 00:01:17,150
otro y otro.

24
00:01:17,150 --> 00:01:19,100
Pero las funciones recursivas
no puede ser infinito.

25
00:01:19,100 --> 00:01:23,490
Tienen que acabar de alguna manera, o en su
programa se ejecutará siempre.

26
00:01:23,490 --> 00:01:27,680
>> Así que tenemos que encontrar una manera de romper
de las llamadas recursivas.

27
00:01:27,680 --> 00:01:29,900
A esto le llamamos el caso base.

28
00:01:29,900 --> 00:01:33,570
Cuando se cumple la condición de caso base,
la función devuelve sin hacer

29
00:01:33,570 --> 00:01:34,950
otra llamada recursiva.

30
00:01:34,950 --> 00:01:39,610
Tome esta función, hi, una función void
que toma un entero n como entrada.

31
00:01:39,610 --> 00:01:41,260
El caso base es lo primero.

32
00:01:41,260 --> 00:01:46,220
Si n es menor que cero, adiós de impresión y
volver Para todos los demás casos, el

33
00:01:46,220 --> 00:01:49,400
función imprimirá hi y ejecutar
la llamada recursiva.

34
00:01:49,400 --> 00:01:53,600
Otra llamada a la función con hi
un valor de entrada decrementa.

35
00:01:53,600 --> 00:01:56,790
>> Ahora, a pesar de que imprimimos hi, la
función no terminará hasta que

36
00:01:56,790 --> 00:02:00,370
devolver su tipo de retorno,
en este caso sin efecto.

37
00:02:00,370 --> 00:02:04,830
Así, por cada n que no sea el caso base,
esta función hi hi volverá

38
00:02:04,830 --> 00:02:06,890
de n menos 1.

39
00:02:06,890 --> 00:02:10,050
Dado que esta función no es válida, sin embargo, que
no se escriba explícitamente regreso aquí.

40
00:02:10,050 --> 00:02:12,000
Acabábamos ejecutaremos la función.

41
00:02:12,000 --> 00:02:16,960
Así que llamar hi (3) imprimirá hola y
ejecutar hi (2), que ejecuta hi (1) una

42
00:02:16,960 --> 00:02:20,560
que ejecuta hi (0), en el que el
se cumple la condición de caso base.

43
00:02:20,560 --> 00:02:24,100
Así hi (0) imprime bye y vuelve.

44
00:02:24,100 --> 00:02:24,990
>> Aceptar.

45
00:02:24,990 --> 00:02:28,690
Así que ahora que entendemos los fundamentos de la
funciones recursivas, que necesitan

46
00:02:28,690 --> 00:02:32,730
al menos un caso base, así como un
llamada recursiva, vamos a pasar a un

47
00:02:32,730 --> 00:02:34,120
ejemplo más significativo.

48
00:02:34,120 --> 00:02:37,830
Uno que no sólo volver
anular no importa qué.

49
00:02:37,830 --> 00:02:41,340
>> Vamos a echar un vistazo a el factorial
operación más comúnmente utilizado en

50
00:02:41,340 --> 00:02:43,660
cálculos de probabilidad.

51
00:02:43,660 --> 00:02:48,120
Factorial de n es el producto de todos los
número entero positivo menor

52
00:02:48,120 --> 00:02:49,400
e igual a n.

53
00:02:49,400 --> 00:02:56,731
Así que cinco factorial es 5 veces 4 veces
3 veces 2 veces 1 para dar 120.

54
00:02:56,731 --> 00:03:01,400
Cuatro factorial es 4 veces 3 veces
2 veces 1 para dar 24.

55
00:03:01,400 --> 00:03:04,910
Y se aplica la misma regla
a cualquier número entero positivo.

56
00:03:04,910 --> 00:03:08,670
>> Entonces, ¿cómo podríamos escribir una recursiva
función que calcula el factorial

57
00:03:08,670 --> 00:03:09,960
de un número?

58
00:03:09,960 --> 00:03:14,700
Bueno, vamos a necesitar para identificar tanto el
caso base y la llamada recursiva.

59
00:03:14,700 --> 00:03:18,250
La llamada recursiva será el mismo
para todos los casos excepto para la base

60
00:03:18,250 --> 00:03:21,420
caso, lo que significa que vamos a tener que
encontrar un patrón que nos dará nuestra

61
00:03:21,420 --> 00:03:23,350
resultado deseado.

62
00:03:23,350 --> 00:03:30,270
>> Para este ejemplo, ver cómo 5 factorial
implica multiplicar 4 por 3 por 2 por 1

63
00:03:30,270 --> 00:03:33,010
Y esa misma multiplicación
se encuentra aquí, el

64
00:03:33,010 --> 00:03:35,430
definición de 4 factorial.

65
00:03:35,430 --> 00:03:39,810
Así que vemos que 5 factorial es
a sólo 5 veces 4 factorial.

66
00:03:39,810 --> 00:03:43,360
Ahora se aplica este patrón
a 4 factorial, así?

67
00:03:43,360 --> 00:03:44,280
Sí.

68
00:03:44,280 --> 00:03:49,120
Vemos que 4 factorial contiene la
multiplicar 3 veces 2 veces 1, el

69
00:03:49,120 --> 00:03:51,590
propia definición como 3 factorial.

70
00:03:51,590 --> 00:03:56,950
Así factorial 4 es igual a 4 veces 3
factorial, y así sucesivamente y así sucesivamente nuestra

71
00:03:56,950 --> 00:04:02,170
patrón de palos hasta 1 factorial, la cual
por definición es igual a 1.

72
00:04:02,170 --> 00:04:04,950
>> No hay otra positiva
enteros fueron.

73
00:04:04,950 --> 00:04:07,870
Así que tenemos el modelo para
nuestra llamada recursiva.

74
00:04:07,870 --> 00:04:13,260
n factorial es igual a n veces
el factorial de n menos 1.

75
00:04:13,260 --> 00:04:14,370
Y nuestro caso base?

76
00:04:14,370 --> 00:04:17,370
Eso acaba de ser nuestra definición
de 1 factorial.

77
00:04:17,370 --> 00:04:19,995
>> Así que ahora podemos pasar a la escritura
código de la función.

78
00:04:19,995 --> 00:04:24,110
Para el caso base, que tendremos la
condición n es igual a es igual a 1, en los que

79
00:04:24,110 --> 00:04:25,780
le devolveremos 1.

80
00:04:25,780 --> 00:04:29,280
Luego de pasar a la llamada recursiva,
volveremos n veces el

81
00:04:29,280 --> 00:04:32,180
factorial de n menos 1.

82
00:04:32,180 --> 00:04:33,590
>> Ahora vamos a probar esta nuestra.

83
00:04:33,590 --> 00:04:35,900
Probemos factorial 4.

84
00:04:35,900 --> 00:04:39,420
Por nuestra función es igual
a 4 veces factorial (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) es igual a
3 veces factoriales (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) es igual a 2 veces
factorial (1), que devuelve 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) ahora devuelve 2 tiempos 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) ahora puede regresar
3 veces 2, 6.

89
00:04:55,960 --> 00:05:02,490
Y, por último, factorial (4)
devuelve 4 tiempos 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Si usted está encontrando alguna dificultad
con la llamada recursiva, pretender que

91
00:05:06,780 --> 00:05:09,660
la función ya funciona.

92
00:05:09,660 --> 00:05:13,450
Lo que quiero decir con esto es que usted debe
confiar en sus llamadas recursivas para volver

93
00:05:13,450 --> 00:05:15,100
los valores correctos.

94
00:05:15,100 --> 00:05:18,960
Por ejemplo, si yo sé que
factorial (5) es igual a 5 veces

95
00:05:18,960 --> 00:05:24,870
factorial (4), voy a confiar en que
factorial (4) me va a dar 24.

96
00:05:24,870 --> 00:05:28,510
Piense en ello como una variable, si
voluntad, como si ya ha definido

97
00:05:28,510 --> 00:05:30,070
factorial (4).

98
00:05:30,070 --> 00:05:33,850
Así que para cualquier factorial (N), que es
el producto de n y

99
00:05:33,850 --> 00:05:35,360
el factorial anterior.

100
00:05:35,360 --> 00:05:38,130
Y esto factorial anterior
se obtiene llamando al

101
00:05:38,130 --> 00:05:41,330
factorial de n menos 1.

102
00:05:41,330 --> 00:05:45,130
>> Ahora, a ver si se puede implementar un
recursiva funcionar a ti mismo.

103
00:05:45,130 --> 00:05:50,490
Carga tu terminal, o run.cs50.net,
y escribir una función sum

104
00:05:50,490 --> 00:05:54,770
que toma un entero n y devuelve el
suma de todas positiva consecutiva

105
00:05:54,770 --> 00:05:57,490
números enteros de n es 1.

106
00:05:57,490 --> 00:06:01,000
He escrito un vistazo a las sumas de algunos
valores que le ayudarán a nuestra.

107
00:06:01,000 --> 00:06:04,030
En primer lugar, averiguar el
condiciones del caso base.

108
00:06:04,030 --> 00:06:06,170
Entonces, mira suma (5).

109
00:06:06,170 --> 00:06:09,270
¿Se puede expresar en términos
de otra suma?

110
00:06:09,270 --> 00:06:11,290
Ahora, ¿qué pasa con suma (4)?

111
00:06:11,290 --> 00:06:15,630
¿Cómo se puede expresar suma (4)
en términos de otra suma?

112
00:06:15,630 --> 00:06:19,655
>> Una vez que tenga suma (5) y suma (4)
expresado en términos de otras cantidades, consulte

113
00:06:19,655 --> 00:06:22,970
si se puede identificar una
patrón para la suma (n).

114
00:06:22,970 --> 00:06:26,190
Si no, pruebe algunos otros números
y expresar sus sumas en

115
00:06:26,190 --> 00:06:28,410
términos de otros números.

116
00:06:28,410 --> 00:06:31,930
Mediante la identificación de los patrones de discreta
números, usted está bien en su manera de

117
00:06:31,930 --> 00:06:34,320
identificar el patrón para cualquier n.

118
00:06:34,320 --> 00:06:38,040
>> La recursividad es una herramienta muy poderosa,
así que por supuesto no se limita a

119
00:06:38,040 --> 00:06:39,820
funciones matemáticas.

120
00:06:39,820 --> 00:06:44,040
La recursividad puede ser utilizado de manera muy eficaz
cuando se trata de árboles, por ejemplo.

121
00:06:44,040 --> 00:06:47,210
Echa un vistazo a la corta de los árboles durante un
opinión más a fondo, pero por ahora

122
00:06:47,210 --> 00:06:51,140
recordar que los árboles de búsqueda binarios, en
en particular, se componen de nodos, cada uno

123
00:06:51,140 --> 00:06:53,820
con un valor y dos punteros de nodo.

124
00:06:53,820 --> 00:06:57,270
Por lo general, esto está representado por el
nodo padre tiene una apuntando línea

125
00:06:57,270 --> 00:07:01,870
al nodo hijo izquierdo y uno
al nodo hijo derecho.

126
00:07:01,870 --> 00:07:04,510
La estructura de una búsqueda binaria
árbol se presta bien

127
00:07:04,510 --> 00:07:05,940
a una búsqueda recursiva.

128
00:07:05,940 --> 00:07:09,730
La llamada recursiva sea pasa en el
izquierda o derecha en el nodo, pero más

129
00:07:09,730 --> 00:07:10,950
de que en el corto árbol.

130
00:07:10,950 --> 00:07:15,690
>> Digamos que usted quiere realizar una operación en
cada nodo individual en un árbol binario.

131
00:07:15,690 --> 00:07:17,410
¿Cómo podría usted ir sobre eso?

132
00:07:17,410 --> 00:07:20,600
Bueno, se podría escribir un recursivo
la función que realiza la operación

133
00:07:20,600 --> 00:07:24,450
en el nodo padre y hace una recursiva
llamar a la misma función,

134
00:07:24,450 --> 00:07:27,630
que pasa en la izquierda y
nodos secundarios adecuados.

135
00:07:27,630 --> 00:07:31,650
Por ejemplo, esta función, foo, que
cambia el valor de un nodo dado y

136
00:07:31,650 --> 00:07:33,830
todos sus hijos a la 1.

137
00:07:33,830 --> 00:07:37,400
El caso base de un nodo causas nulos
la función para volver, lo que indica

138
00:07:37,400 --> 00:07:41,290
que no hay nodos
dejado en ese sub-árbol.

139
00:07:41,290 --> 00:07:42,620
>> Vamos a caminar a través de él.

140
00:07:42,620 --> 00:07:44,340
El primero de los padres es de 13.

141
00:07:44,340 --> 00:07:47,930
Cambiamos el valor a 1, y luego llamamos
nuestra función en el lado izquierdo, así

142
00:07:47,930 --> 00:07:49,600
como el derecho.

143
00:07:49,600 --> 00:07:53,910
La función, foo, se llama a la izquierda
sub-árbol en primer lugar, por lo que el nodo izquierdo

144
00:07:53,910 --> 00:07:57,730
será reasignado a 1 y Foo
se pidió a los niños de ese nodo,

145
00:07:57,730 --> 00:08:01,900
primero la izquierda y luego la derecha,
y así sucesivamente y así sucesivamente.

146
00:08:01,900 --> 00:08:05,630
Y les digo que las ramas no tienen
tener más hijos por lo que el mismo proceso

147
00:08:05,630 --> 00:08:09,700
continuará por los hijos derecha
hasta los nodos de la totalidad de los árboles son

148
00:08:09,700 --> 00:08:11,430
reasignado a 1.

149
00:08:11,430 --> 00:08:15,390
>> Como puede ver, usted no está limitado
a sólo una llamada recursiva.

150
00:08:15,390 --> 00:08:17,930
Al igual que todos los que conseguirá el trabajo hecho.

151
00:08:17,930 --> 00:08:21,200
¿Qué pasa si usted tenía un árbol donde cada
nodo tuvo tres hijos,

152
00:08:21,200 --> 00:08:23,100
Izquierda, Centro y Derecha?

153
00:08:23,100 --> 00:08:24,886
¿Cómo editar foo?

154
00:08:24,886 --> 00:08:25,860
Bueno, simple.

155
00:08:25,860 --> 00:08:30,250
Sólo tiene que añadir otra llamada recursiva y
pase el puntero del nodo intermedio.

156
00:08:30,250 --> 00:08:34,549
>> La recursividad es muy potente y no
menciona elegante, pero puede ser un

157
00:08:34,549 --> 00:08:38,010
difícil concepto al principio, así que
paciente y tómese su tiempo.

158
00:08:38,010 --> 00:08:39,370
Comience con el caso base.

159
00:08:39,370 --> 00:08:42,650
Por lo general es la más fácil de identificar,
y entonces usted puede trabajar

160
00:08:42,650 --> 00:08:43,830
hacia atrás desde allí.

161
00:08:43,830 --> 00:08:46,190
Usted sabe que necesita para llegar a su
caso base, por lo que el poder

162
00:08:46,190 --> 00:08:47,760
darle algunos consejos.

163
00:08:47,760 --> 00:08:53,120
Trate de expresar un caso específico en
términos de otras causas o en sub-conjuntos.

164
00:08:53,120 --> 00:08:54,700
>> Gracias por ver este corto.

165
00:08:54,700 --> 00:08:58,920
Por lo menos, ahora puede hacerlo
entender chistes como éste.

166
00:08:58,920 --> 00:09:01,250
Mi nombre es Zamyla, y esto es CS50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Tome esta función, hi, un
void función que toma

169
00:09:07,170 --> 00:09:09,212
un int, n, como entrada.

170
00:09:09,212 --> 00:09:11,020
El caso base es lo primero.

171
00:09:11,020 --> 00:09:14,240
Si n es menor que 0, imprimir
"Bye" y el retorno.

172
00:09:14,240 --> 00:09:15,490