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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: A fin de comprender
recursão, ten que

3
00:00:10,190 --> 00:00:13,820
primeiro entender recursión.

4
00:00:13,820 --> 00:00:17,280
Tendo recursão en programa proxecto significa
que ten auto-referencial

5
00:00:17,280 --> 00:00:18,570
definicións.

6
00:00:18,570 --> 00:00:21,520
Estruturas de datos recursivas, por exemplo,
son estruturas de datos que

7
00:00:21,520 --> 00:00:23,990
inclúense na
súas definicións.

8
00:00:23,990 --> 00:00:27,160
Pero hoxe, imos centrar
en funcións recursivas.

9
00:00:27,160 --> 00:00:31,160
>> Lembre que as funcións de entradas,
argumentos, e voltar un valor como o seu

10
00:00:31,160 --> 00:00:34,480
saída representada polos
Neste diagrama aquí.

11
00:00:34,480 --> 00:00:38,060
Nós imos pensar no cadro como o corpo de
a función, que contén o conxunto de

12
00:00:38,060 --> 00:00:42,340
instrucións que interpretan o
de entrada e proporcionar unha saída.

13
00:00:42,340 --> 00:00:45,660
Dando un ollo ao interior do corpo de
a función podería revelar chamadas a

14
00:00:45,660 --> 00:00:47,430
outras funcións tamén.

15
00:00:47,430 --> 00:00:51,300
Aproveitar esta función simple, foo, que
ten unha única secuencia como entrada e

16
00:00:51,300 --> 00:00:54,630
copias cantas letras
esa secuencia ten.

17
00:00:54,630 --> 00:00:58,490
O strlen función, para a lonxitude da corda,
chámase, cuxa saída está

18
00:00:58,490 --> 00:01:01,890
necesaria para a chamada a printf.

19
00:01:01,890 --> 00:01:05,770
>> Agora, o que fai que unha función recursiva
especial é que se chama.

20
00:01:05,770 --> 00:01:09,610
Podemos representar esta recursiva
chamar con esta frecha laranxa

21
00:01:09,610 --> 00:01:11,360
Looping de volta a si mesmo.

22
00:01:11,360 --> 00:01:15,630
Pero a execución en si de novo só pode
facer outra chamada recursiva, e

23
00:01:15,630 --> 00:01:17,150
outra e outra.

24
00:01:17,150 --> 00:01:19,100
Pero funcións recursivas
non pode ser infinita.

25
00:01:19,100 --> 00:01:23,490
Teñen de acabar de algunha maneira, ou o seu
programa será executado para sempre.

26
00:01:23,490 --> 00:01:27,680
>> Entón, necesitamos atopar unha forma de rompe
fóra das chamadas recursivas.

27
00:01:27,680 --> 00:01:29,900
Chamamos iso de caso base.

28
00:01:29,900 --> 00:01:33,570
Cando a condición de caso base é cumprida,
a función devolve sen facer

29
00:01:33,570 --> 00:01:34,950
outra chamada recursiva.

30
00:01:34,950 --> 00:01:39,610
Tomé esta función, oi, unha función void
que leva un int n como entrada.

31
00:01:39,610 --> 00:01:41,260
O caso base ven en primeiro lugar.

32
00:01:41,260 --> 00:01:46,220
Se n é menor que cero, imprimir e bye
Voltar todos os demais casos, o

33
00:01:46,220 --> 00:01:49,400
función imprimirá ola e executar
a chamada recursiva.

34
00:01:49,400 --> 00:01:53,600
Outra chamada á función con ola
un valor de entrada diminúa.

35
00:01:53,600 --> 00:01:56,790
>> Agora, aínda que imprimir ola, o
función non rematará ata que nós

36
00:01:56,790 --> 00:02:00,370
voltar o seu tipo de retorno,
neste caso, nulo.

37
00:02:00,370 --> 00:02:04,830
Así, para cada n distinto do caso base,
esta función pode voltar ola ola

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

39
00:02:06,890 --> 00:02:10,050
Xa que esta función non é nada, porén, que
non explicitamente tipo de retorno aquí.

40
00:02:10,050 --> 00:02:12,000
Nós imos realizar a función.

41
00:02:12,000 --> 00:02:16,960
Entón, chamando ola (3) imprimirá ola e
realizar ola (2) que executa ola (1) un

42
00:02:16,960 --> 00:02:20,560
que executa ola (0), onde o
condición caso base sexa cumprido.

43
00:02:20,560 --> 00:02:24,100
Entón, oi (0) imprime bye e retorna.

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

45
00:02:24,990 --> 00:02:28,690
Polo tanto, agora que entendemos os principios básicos de
funcións recursivas, que precisan

46
00:02:28,690 --> 00:02:32,730
polo menos unha de base, así como un
chamada recursiva, imos pasar a unha

47
00:02:32,730 --> 00:02:34,120
exemplo máis significativo.

48
00:02:34,120 --> 00:02:37,830
Un que non só devolver
anular non importa o que.

49
00:02:37,830 --> 00:02:41,340
>> Imos dar un ollo ao factorial
operación máis comunmente usado en

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

51
00:02:43,660 --> 00:02:48,120
Factorial de n é o produto de todos os
enteiro positivo inferior

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

53
00:02:49,400 --> 00:02:56,731
Entón cinco factorial é 5 veces 4 veces
3 veces, 2 veces 1 para obter 120.

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

55
00:03:01,400 --> 00:03:04,910
E a mesma regra se aplica
para calquera número enteiro positivo.

56
00:03:04,910 --> 00:03:08,670
>> Entón, como podemos escribir unha recursiva
función que calcula o factorial

57
00:03:08,670 --> 00:03:09,960
dunha serie de?

58
00:03:09,960 --> 00:03:14,700
Ben, imos ter para identificar a
caso base e da chamada recursiva.

59
00:03:14,700 --> 00:03:18,250
A chamada recursiva será o mesmo
para todos os casos, excepto para a base

60
00:03:18,250 --> 00:03:21,420
caso, o que significa que nós imos ter que
atopar un estándar que vai dar o noso

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

62
00:03:23,350 --> 00:03:30,270
>> Para este exemplo, vexa como factorial 5
consiste en multiplicar 4 por 3 por 2 por 1

63
00:03:30,270 --> 00:03:33,010
E esa mesma multiplicación
se atopa aquí, o

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

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

66
00:03:39,810 --> 00:03:43,360
Agora é que este estándar é aplicable
a 4 factorial ben?

67
00:03:43,360 --> 00:03:44,280
Si

68
00:03:44,280 --> 00:03:49,120
Vemos que 4 factorial contén o
multiplicación 3 veces, 2 veces 1, o

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

70
00:03:51,590 --> 00:03:56,950
Entón, 4 factorial é igual a catro veces tres
factorial, e así por diante e así por diante a nosa

71
00:03:56,950 --> 00:04:02,170
estándar varas ata o 1 de factorial, que
por definición, é igual a 1.

72
00:04:02,170 --> 00:04:04,950
>> Non hai outro positivo
enteiros esquerda.

73
00:04:04,950 --> 00:04:07,870
Polo tanto, temos o estándar para
nosa chamada recursiva.

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

75
00:04:13,260 --> 00:04:14,370
E o noso caso base?

76
00:04:14,370 --> 00:04:17,370
Isto vai ser só a nosa definición
dun factorial.

77
00:04:17,370 --> 00:04:19,995
>> Entón agora podemos pasar á escritura
código para a función.

78
00:04:19,995 --> 00:04:24,110
Para o caso base, teremos a
condición n é igual a igual a 1, onde

79
00:04:24,110 --> 00:04:25,780
imos voltar 1.

80
00:04:25,780 --> 00:04:29,280
Despois de pasar á chamada recursiva,
imos voltar n veces o

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

82
00:04:32,180 --> 00:04:33,590
>> Agora imos probar este noso.

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

84
00:04:35,900 --> 00:04:39,420
Pola nosa función é igual
a 4 veces factorial (3).

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

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

87
00:04:48,700 --> 00:04:52,490
Factorial (2) agora regresa 2 veces 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) agora pode volver
3 veces 2, 6.

89
00:04:55,960 --> 00:05:02,490
E, finalmente, factorial (4)
retorna 4 veces 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Se está atopando algunha dificultade
coa chamada recursiva, finxir que

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

92
00:05:09,660 --> 00:05:13,450
O que quero dicir con isto é que ten que
confiar nos seus chamadas recursivas para volver

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

94
00:05:15,100 --> 00:05:18,960
Por exemplo, se eu sei que
factorial (5) é igual a 5 veces

95
00:05:18,960 --> 00:05:24,870
factorial (4), eu vou confiar que
factorial (4) me vai dar 24.

96
00:05:24,870 --> 00:05:28,510
Pense nisso como unha variable, se
vontade, como se xa definido

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

98
00:05:30,070 --> 00:05:33,850
Así, para calquera factorial (n), é
o produto de n e

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

100
00:05:35,360 --> 00:05:38,130
E iso factorial anterior
obtense chamando

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

102
00:05:41,330 --> 00:05:45,130
>> Agora, vexa se pode aplicar un
recursiva funcionar só.

103
00:05:45,130 --> 00:05:50,490
Prema o seu terminal, ou run.cs50.net,
e escribir unha función suma

104
00:05:50,490 --> 00:05:54,770
que leva un enteiro n e devolve o
suma de todos os positivos consecutivo

105
00:05:54,770 --> 00:05:57,490
enteiros de 1 a n.

106
00:05:57,490 --> 00:06:01,000
Escribín as sumas dalgúns
valores para axudar a nosa.

107
00:06:01,000 --> 00:06:04,030
En primeiro lugar, descubrir a
condición caso base.

108
00:06:04,030 --> 00:06:06,170
Entón, mire para suma (5).

109
00:06:06,170 --> 00:06:09,270
Pode expresalo en termos
doutra suma?

110
00:06:09,270 --> 00:06:11,290
Agora, que tal suma (4)?

111
00:06:11,290 --> 00:06:15,630
Como pode expresar suma (4)
en termos doutra suma?

112
00:06:15,630 --> 00:06:19,655
>> Despois de suma (5) e suma (4)
expresada en termos doutras cantidades, consulte

113
00:06:19,655 --> 00:06:22,970
se pode identificar un
estándar para a suma (n).

114
00:06:22,970 --> 00:06:26,190
Se non, proba algúns outros números
e expresar as súas sumas en

115
00:06:26,190 --> 00:06:28,410
termos de números.

116
00:06:28,410 --> 00:06:31,930
Ao identificar patróns para discreto
números, está ben na súa forma de

117
00:06:31,930 --> 00:06:34,320
a identificación do estándar para calquera n.

118
00:06:34,320 --> 00:06:38,040
>> A recursão é unha ferramenta moi poderosa,
entón é claro que non está limitado a

119
00:06:38,040 --> 00:06:39,820
funcións matemáticas.

120
00:06:39,820 --> 00:06:44,040
A recursión se pode usar de forma moi eficaz
cando se trata de árbores, por exemplo.

121
00:06:44,040 --> 00:06:47,210
Escribe o curta en árbores para un
máis profunda revisión, pero por agora

122
00:06:47,210 --> 00:06:51,140
lembrar que as árbores de busca binária, en
en particular, son constituídos por nós, cada

123
00:06:51,140 --> 00:06:53,820
cun valor e dous punteiros do nodo.

124
00:06:53,820 --> 00:06:57,270
Normalmente, este é representado pola
nodo pai ter unha liña que apunta

125
00:06:57,270 --> 00:07:01,870
ao nodo fillo esquerdo e un
ao nodo fillo dereito.

126
00:07:01,870 --> 00:07:04,510
A estrutura dunha busca binaria
árbore presta-se ben

127
00:07:04,510 --> 00:07:05,940
para unha investigación recursiva.

128
00:07:05,940 --> 00:07:09,730
A chamada recursiva ou pasa no
esquerda ou o no dereito, pero máis

129
00:07:09,730 --> 00:07:10,950
de que, a curto árbore.

130
00:07:10,950 --> 00:07:15,690
>> Digamos que queira realizar unha operación en
cada nó único nunha árbore binaria.

131
00:07:15,690 --> 00:07:17,410
Como pode ir sobre iso?

132
00:07:17,410 --> 00:07:20,600
Ben, vostede podería escribir un recursiva
función que executa a operación

133
00:07:20,600 --> 00:07:24,450
no nodo pai e fai unha recursiva
chamar a mesma función,

134
00:07:24,450 --> 00:07:27,630
pasando á esquerda e
nós fillos dereita.

135
00:07:27,630 --> 00:07:31,650
Por exemplo, esta función, foo, que
modifica o valor dun determinado nó e

136
00:07:31,650 --> 00:07:33,830
todos os seus fillos a 1.

137
00:07:33,830 --> 00:07:37,400
O caso base dun nulo causas nodo
a función de retorno, indicando

138
00:07:37,400 --> 00:07:41,290
que non hai ningún nodo
esquerda en que a sub-árbore.

139
00:07:41,290 --> 00:07:42,620
>> Imos atravesalo-la.

140
00:07:42,620 --> 00:07:44,340
O primeiro pai é 13.

141
00:07:44,340 --> 00:07:47,930
Imos cambiar o valor a 1, e logo chamar
a nosa función na esquerda ben

142
00:07:47,930 --> 00:07:49,600
como o dereito.

143
00:07:49,600 --> 00:07:53,910
A función, foo, chámase á esquerda
sub-árbore en primeiro lugar, de xeito que o nodo esquerdo

144
00:07:53,910 --> 00:07:57,730
será trasladado a 1 e foo vontade
ser chamados fillos dese nó,

145
00:07:57,730 --> 00:08:01,900
primeiro á esquerda e despois á dereita,
e así por diante e así por diante.

146
00:08:01,900 --> 00:08:05,630
E dicirlles que as sucursais non teñen
calquera máis nenos para que o mesmo proceso

147
00:08:05,630 --> 00:08:09,700
seguirá para os nenos certas
ata nós de toda árbore son

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

149
00:08:11,430 --> 00:08:15,390
>> Como podes ver, non está limitado
para só unha chamada recursiva.

150
00:08:15,390 --> 00:08:17,930
Así como moitos como vai comezar o traballo feito.

151
00:08:17,930 --> 00:08:21,200
E se tivese unha árbore onde cada
nó tivo tres fillos,

152
00:08:21,200 --> 00:08:23,100
Esquerda, medio e dereita?

153
00:08:23,100 --> 00:08:24,886
Como editar foo?

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

155
00:08:25,860 --> 00:08:30,250
Tan só engadir outra chamada recursiva e
pasar o punteiro do nodo central.

156
00:08:30,250 --> 00:08:34,549
>> A recursão é moi poderoso e non
mencionar elegante, pero pode ser un

157
00:08:34,549 --> 00:08:38,010
concepto difícil ao principio, polo que non
paciente e tomar o seu tempo.

158
00:08:38,010 --> 00:08:39,370
Comeza o caso base.

159
00:08:39,370 --> 00:08:42,650
Xeralmente é o máis fácil de identificar,
e logo, pode traballar

160
00:08:42,650 --> 00:08:43,830
atrás a partir de aí.

161
00:08:43,830 --> 00:08:46,190
Vostede sabe que precisa para chegar ao seu
caso base, de xeito que o poder

162
00:08:46,190 --> 00:08:47,760
darlle algunhas suxestións.

163
00:08:47,760 --> 00:08:53,120
Probe expresar un caso concreto en
termos de outros casos, ou en sub-conxuntos.

164
00:08:53,120 --> 00:08:54,700
>> Grazas por asistir a este curta.

165
00:08:54,700 --> 00:08:58,920
Polo menos, agora pode
comprender bromas como esta.

166
00:08:58,920 --> 00:09:01,250
O meu nome é Zamyla, e este é CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Tomé esta función, oi, un
función void que leva

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

170
00:09:09,212 --> 00:09:11,020
O caso base ven en primeiro lugar.

171
00:09:11,020 --> 00:09:14,240
Se n é menor que 0, impresión
"Bye" e retorno.

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