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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: A fim de compreender
recursão, você deve

3
00:00:10,190 --> 00:00:13,820
primeiro entender recursão.

4
00:00:13,820 --> 00:00:17,280
Tendo recursão em programa projeto significa
que você tem auto-referencial

5
00:00:17,280 --> 00:00:18,570
definições.

6
00:00:18,570 --> 00:00:21,520
Estruturas de dados recursivas, por exemplo,
são estruturas de dados que

7
00:00:21,520 --> 00:00:23,990
incluem-se na
suas definições.

8
00:00:23,990 --> 00:00:27,160
Mas hoje, vamos focar
em funções recursiva.

9
00:00:27,160 --> 00:00:31,160
>> Lembre-se que as funções de ter entradas,
argumentos, e retornar um valor como o seu

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

11
00:00:34,480 --> 00:00:38,060
Nós vamos pensar na caixa como o corpo de
a função, contendo o conjunto de

12
00:00:38,060 --> 00:00:42,340
instruções que interpretam o
de entrada e fornecer uma saída.

13
00:00:42,340 --> 00:00:45,660
Dando uma olhada no interior do corpo de
a função poderia revelar chamadas para

14
00:00:45,660 --> 00:00:47,430
outras funções também.

15
00:00:47,430 --> 00:00:51,300
Aproveite esta função simples, foo, que
tem uma única seqüência como entrada e

16
00:00:51,300 --> 00:00:54,630
cópias quantas letras
essa seqüência tem.

17
00:00:54,630 --> 00:00:58,490
O strlen função, para o comprimento da corda,
é chamado, cuja saída está

18
00:00:58,490 --> 00:01:01,890
necessária para a chamada para printf.

19
00:01:01,890 --> 00:01:05,770
>> Agora, o que faz com que uma função recursiva
especial é que ele se chama.

20
00:01:05,770 --> 00:01:09,610
Podemos representar esta recursiva
chamar com esta seta laranja

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

22
00:01:11,360 --> 00:01:15,630
Mas a execução em si novamente só irá
fazer 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
Mas funções recursivas
não pode ser infinita.

25
00:01:19,100 --> 00:01:23,490
Eles têm de acabar de alguma forma, ou o seu
programa será executado para sempre.

26
00:01:23,490 --> 00:01:27,680
>> Então, precisamos encontrar uma maneira de quebrar
fora das chamadas recursivas.

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

28
00:01:29,900 --> 00:01:33,570
Quando a condição de caso base é cumprida,
a função retorna sem fazer

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

30
00:01:34,950 --> 00:01:39,610
Tome esta função, oi, uma função void
que leva um int n como entrada.

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

32
00:01:41,260 --> 00:01:46,220
Se n é menor que zero, imprimir e bye
voltar Para todos os outros casos, o

33
00:01:46,220 --> 00:01:49,400
função irá imprimir oi e executar
a chamada recursiva.

34
00:01:49,400 --> 00:01:53,600
Outra chamada para a função com oi
um valor de entrada diminua.

35
00:01:53,600 --> 00:01:56,790
>> Agora, mesmo que imprimir oi, o
função não terminará até que nós

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

37
00:02:00,370 --> 00:02:04,830
Assim, para cada n diferente do caso base,
esta função irá retornar oi oi

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

39
00:02:06,890 --> 00:02:10,050
Uma vez que esta função não é nada, porém, que
não explicitamente tipo de retorno aqui.

40
00:02:10,050 --> 00:02:12,000
Nós vamos executar a função.

41
00:02:12,000 --> 00:02:16,960
Então, chamando oi (3) irá imprimir oi e
executar oi (2) que executa oi (1) um

42
00:02:16,960 --> 00:02:20,560
que executa oi (0), onde o
condição caso base seja cumprido.

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

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

45
00:02:24,990 --> 00:02:28,690
Portanto, agora que entendemos os princípios básicos de
funções recursivas, que eles precisam

46
00:02:28,690 --> 00:02:32,730
pelo menos uma de base, assim como um
chamada recursiva, vamos passar para uma

47
00:02:32,730 --> 00:02:34,120
exemplo mais significativo.

48
00:02:34,120 --> 00:02:37,830
Um que não apenas retornar
anular não importa o que.

49
00:02:37,830 --> 00:02:41,340
>> Vamos dar uma olhada no fatorial
operação mais comumente usado em

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 todas as
inteiro 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ão cinco fatorial é 5 vezes 4 vezes
3 vezes 2 vezes 1 para se obter 120.

54
00:02:56,731 --> 00:03:01,400
Quatro fatorial é 4 vezes 3 vezes
2 vezes 1 para dar 24.

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

56
00:03:04,910 --> 00:03:08,670
>> Então, como podemos escrever uma recursiva
função que calcula o fatorial

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

58
00:03:09,960 --> 00:03:14,700
Bem, vamos precisar 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, exceto para a base

60
00:03:18,250 --> 00:03:21,420
caso, o que significa que nós vamos ter que
encontrar um padrão que vai nos dar o nosso

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

62
00:03:23,350 --> 00:03:30,270
>> Para este exemplo, veja como fatorial 5
consiste em multiplicar 4 por 3 por 2 por 1

63
00:03:30,270 --> 00:03:33,010
E essa mesma multiplicação
se encontra aqui, o

64
00:03:33,010 --> 00:03:35,430
definição de 4 fatorial.

65
00:03:35,430 --> 00:03:39,810
Assim, vemos que 5 fatorial é
apenas 5 vezes 4 fatorial.

66
00:03:39,810 --> 00:03:43,360
Agora é que este padrão se aplica
a 4 factorial bem?

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

68
00:03:44,280 --> 00:03:49,120
Vemos que 4 fatorial contém o
multiplicação 3 vezes 2 vezes 1, o

69
00:03:49,120 --> 00:03:51,590
mesma definição como 3 fatorial.

70
00:03:51,590 --> 00:03:56,950
Então, 4 fatorial é igual a quatro vezes três
fatorial, e assim por diante e assim por diante a nossa

71
00:03:56,950 --> 00:04:02,170
padrão varas até 1 de fatorial, que
por definição, é igual a 1.

72
00:04:02,170 --> 00:04:04,950
>> Não há outro positivo
inteiros esquerda.

73
00:04:04,950 --> 00:04:07,870
Portanto, temos o padrão para
nossa chamada recursiva.

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

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

76
00:04:14,370 --> 00:04:17,370
Isso vai ser apenas a nossa definição
de um fatorial.

77
00:04:17,370 --> 00:04:19,995
>> Então agora podemos passar para a escrita
código para a função.

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

79
00:04:24,110 --> 00:04:25,780
vamos retornar 1.

80
00:04:25,780 --> 00:04:29,280
Depois de passar para a chamada recursiva,
vamos voltar n vezes o

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

82
00:04:32,180 --> 00:04:33,590
>> Agora vamos testar este nosso.

83
00:04:33,590 --> 00:04:35,900
Vamos tentar fatorial 4.

84
00:04:35,900 --> 00:04:39,420
Por nossa função é igual
a 4 vezes fatorial (3).

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

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

87
00:04:48,700 --> 00:04:52,490
Fatorial (2) agora retorna 2 vezes 1, 2.

88
00:04:52,490 --> 00:04:55,960
Fatorial (3) agora pode retornar
3 vezes 2, 6.

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

90
00:05:02,490 --> 00:05:06,780
>> Se você está encontrando alguma dificuldade
com a chamada recursiva, fingir que

91
00:05:06,780 --> 00:05:09,660
a função já funciona.

92
00:05:09,660 --> 00:05:13,450
O que quero dizer com isso é que você deve
confiar em seus chamadas recursivas para voltar

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

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

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

96
00:05:24,870 --> 00:05:28,510
Pense nisso como uma variável, se você
vontade, como se você já definido

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

98
00:05:30,070 --> 00:05:33,850
Assim, para qualquer fatorial (n), é
o produto de n e

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

100
00:05:35,360 --> 00:05:38,130
E isso fatorial anterior
é obtida chamando

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

102
00:05:41,330 --> 00:05:45,130
>> Agora, veja se você pode implementar um
recursiva funcionar sozinho.

103
00:05:45,130 --> 00:05:50,490
Carregue o seu terminal, ou run.cs50.net,
e escrever uma função soma

104
00:05:50,490 --> 00:05:54,770
que leva um inteiro n e retorna o
soma de todos os positivo consecutivo

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

106
00:05:57,490 --> 00:06:01,000
Eu escrevi as somas de alguns
valores para ajudá-lo a nossa.

107
00:06:01,000 --> 00:06:04,030
Em primeiro lugar, descobrir a
condição caso base.

108
00:06:04,030 --> 00:06:06,170
Então, olhe para soma (5).

109
00:06:06,170 --> 00:06:09,270
Você pode expressá-lo em termos
de outra soma?

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

111
00:06:11,290 --> 00:06:15,630
Como você pode expressar soma (4)
em termos de outra soma?

112
00:06:15,630 --> 00:06:19,655
>> Depois de ter soma (5) e soma (4)
expressa em termos de outras quantias, consulte

113
00:06:19,655 --> 00:06:22,970
se você pode identificar um
padrão para a soma (n).

114
00:06:22,970 --> 00:06:26,190
Se não, tente alguns outros números
e expressar suas somas em

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

116
00:06:28,410 --> 00:06:31,930
Ao identificar padrões para discreto
números, você está bem em sua maneira de

117
00:06:31,930 --> 00:06:34,320
a identificação do padrão para qualquer n.

118
00:06:34,320 --> 00:06:38,040
>> A recursão é uma ferramenta muito poderosa,
então é claro que ele não está limitado a

119
00:06:38,040 --> 00:06:39,820
funções matemáticas.

120
00:06:39,820 --> 00:06:44,040
A recursão pode ser usado de forma muito eficaz
quando se trata de árvores, por exemplo.

121
00:06:44,040 --> 00:06:47,210
Confira o curta em árvores para um
mais profunda revisão, mas por agora

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

123
00:06:51,140 --> 00:06:53,820
com um valor e dois ponteiros do nó.

124
00:06:53,820 --> 00:06:57,270
Normalmente, este é representado pela
nó pai ter uma linha que aponta

125
00:06:57,270 --> 00:07:01,870
para o nó filho esquerdo e um
para o nó filho direito.

126
00:07:01,870 --> 00:07:04,510
A estrutura de uma pesquisa binária
árvore presta-se bem

127
00:07:04,510 --> 00:07:05,940
para uma pesquisa recursiva.

128
00:07:05,940 --> 00:07:09,730
A chamada recursiva ou passa no
esquerda ou o nó direito, mas mais

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

130
00:07:10,950 --> 00:07:15,690
>> Digamos que você queira executar uma operação em
cada nó único em uma árvore binária.

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

132
00:07:17,410 --> 00:07:20,600
Bem, você poderia escrever um recursiva
função que executa a operação

133
00:07:20,600 --> 00:07:24,450
no nó pai e faz uma recursiva
ligar para a mesma função,

134
00:07:24,450 --> 00:07:27,630
passando a esquerda e
nós filhos direita.

135
00:07:27,630 --> 00:07:31,650
Por exemplo, esta função, foo, que
altera o valor de um determinado nó e

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

137
00:07:33,830 --> 00:07:37,400
O caso base de um nulo causas nó
a função de retorno, indicando

138
00:07:37,400 --> 00:07:41,290
que não há nenhum nó
esquerda em que a sub-árvore.

139
00:07:41,290 --> 00:07:42,620
>> Vamos atravessá-la.

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

141
00:07:44,340 --> 00:07:47,930
Vamos mudar o valor para 1, e em seguida, chamar
a nossa função na esquerda bem

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

143
00:07:49,600 --> 00:07:53,910
A função, foo, é chamado à esquerda
sub-árvore em primeiro lugar, de modo que o nó esquerdo

144
00:07:53,910 --> 00:07:57,730
será transferido para 1 e foo vontade
ser chamados filhos desse nó,

145
00:07:57,730 --> 00:08:01,900
primeiro à esquerda e depois à direita,
e assim por diante e assim por diante.

146
00:08:01,900 --> 00:08:05,630
E dizer-lhes que as sucursais não têm
qualquer mais crianças para que o mesmo processo

147
00:08:05,630 --> 00:08:09,700
continuará para as crianças certas
até nós de toda a árvore são

148
00:08:09,700 --> 00:08:11,430
transferido para 1.

149
00:08:11,430 --> 00:08:15,390
>> Como você pode ver, você não está limitado
para apenas uma chamada recursiva.

150
00:08:15,390 --> 00:08:17,930
Assim como muitos como vai começar o trabalho feito.

151
00:08:17,930 --> 00:08:21,200
E se você tivesse uma árvore onde cada
nó teve três filhos,

152
00:08:21,200 --> 00:08:23,100
Esquerda, meio e direita?

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

154
00:08:24,886 --> 00:08:25,860
Bem, simples.

155
00:08:25,860 --> 00:08:30,250
Basta adicionar outra chamada recursiva e
passar o ponteiro do nó central.

156
00:08:30,250 --> 00:08:34,549
>> A recursão é muito poderoso e não
mencionar elegante, mas pode ser um

157
00:08:34,549 --> 00:08:38,010
conceito difícil no início, por isso não
paciente e tomar o seu tempo.

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

159
00:08:39,370 --> 00:08:42,650
Geralmente é o mais fácil de identificar,
e, em seguida, você pode trabalhar

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

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

162
00:08:46,190 --> 00:08:47,760
dar-lhe algumas sugestões.

163
00:08:47,760 --> 00:08:53,120
Tente expressar um caso específico em
termos de outros casos, ou em sub-conjuntos.

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

165
00:08:54,700 --> 00:08:58,920
Pelo menos, agora você pode
entender piadas como esta.

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

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

168
00:09:04,306 --> 00:09:07,170
>> Tome esta função, oi, um
função void que leva

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

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

171
00:09:11,020 --> 00:09:14,240
Se n for menor do que 0, impressão
"Bye" e retorno.

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