1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Se você já viu
o vídeo em recursão,

3
00:00:07,670 --> 00:00:10,170
todo o processo pode ter
parecia um pouco mágico.

4
00:00:10,170 --> 00:00:10,930
Como funciona?

5
00:00:10,930 --> 00:00:15,010
Como as funções de saber que eles
precisamos esperar e esperar por um outro valor

6
00:00:15,010 --> 00:00:19,150
para retornar de uma função diferente
chamar a fim de obter o resultado que queremos?

7
00:00:19,150 --> 00:00:22,550
>> Bem, a razão é porque isso funciona
de algo conhecido como a pilha de chamadas.

8
00:00:22,550 --> 00:00:26,360
Quando você chamar uma função, o
sistema deixa de lado o espaço na memória

9
00:00:26,360 --> 00:00:28,120
para essa função para fazer seu trabalho.

10
00:00:28,120 --> 00:00:31,720
E nós chamamos esses blocos de memória que
estão sendo retiradas para cada função

11
00:00:31,720 --> 00:00:35,670
chamar um quadro de pilha ou uma moldura função.

12
00:00:35,670 --> 00:00:38,290
E como você poderia esperar,
estes quadros de pilha

13
00:00:38,290 --> 00:00:41,000
vivem na parte pilha de memória.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Mais do que uma função de quadro de pilha
podem existir em memória num dado momento.

16
00:00:47,540 --> 00:00:51,240
Se principal chama um movimento função,
e chama movimento direção,

17
00:00:51,240 --> 00:00:54,460
todas as três funções têm quadros abertos.

18
00:00:54,460 --> 00:00:57,350
Mas eles não têm quadros ativos.

19
00:00:57,350 --> 00:00:59,410
Estes quadros são dispostas numa pilha.

20
00:00:59,410 --> 00:01:01,820
E o quadro do
mais recentemente chamado

21
00:01:01,820 --> 00:01:04,390
função é sempre no topo da pilha.

22
00:01:04,390 --> 00:01:07,150
E isso é sempre o quadro ativo.

23
00:01:07,150 --> 00:01:10,420
Só há realmente sempre uma
função que é ativo em um tempo.

24
00:01:10,420 --> 00:01:12,420
É um no topo da pilha.

25
00:01:12,420 --> 00:01:17,620
>> Quando uma função chama outra
função, ele pressiona tipo de pausa.

26
00:01:17,620 --> 00:01:20,590
É uma espécie de está em espera, esperando.

27
00:01:20,590 --> 00:01:24,050
E um outro quadro de pilha é empurrado
para a pilha em cima dela.

28
00:01:24,050 --> 00:01:26,150
E isso se torna o quadro ativo.

29
00:01:26,150 --> 00:01:28,600
E o quadro imediatamente
abaixo dele necessita de esperar

30
00:01:28,600 --> 00:01:33,560
até que seja novamente o quadro ativo
antes que ele possa retomar o seu trabalho.

31
00:01:33,560 --> 00:01:35,870
Quando uma função é
completo e ele é feito,

32
00:01:35,870 --> 00:01:37,720
seu quadro é retirado da pilha.

33
00:01:37,720 --> 00:01:38,950
Essa é a terminologia.

34
00:01:38,950 --> 00:01:41,110
E o quadro imediatamente
abaixo dele, como acabei de dizer,

35
00:01:41,110 --> 00:01:42,880
torna-se o novo quadro ativo.

36
00:01:42,880 --> 00:01:45,960
>> E se ele chama outra função,
ele vai parar novamente.

37
00:01:45,960 --> 00:01:49,290
Pilha quadro que nova função será
ser empurrada para o topo da pilha.

38
00:01:49,290 --> 00:01:50,650
Ele vai fazer o seu trabalho.

39
00:01:50,650 --> 00:01:52,100
Ele pode aparecer de volta fora.

40
00:01:52,100 --> 00:01:55,630
E a outra função
abaixo dele pode retomar novamente.

41
00:01:55,630 --> 00:02:00,080
>> Então, vamos passar por isso de novo, olhando
com a idéia da função fatorial

42
00:02:00,080 --> 00:02:03,070
que definido na
vídeo recursão para ver

43
00:02:03,070 --> 00:02:07,770
exatamente como a magia por trás disso
processo recursivo está ocorrendo.

44
00:02:07,770 --> 00:02:09,870
Portanto, este é todo o nosso arquivo, certo?

45
00:02:09,870 --> 00:02:14,000
Nós definimos dois
funções no principal e fato.

46
00:02:14,000 --> 00:02:15,980
E, como seria de esperar,
qualquer programa C vai

47
00:02:15,980 --> 00:02:18,470
para começar na primeira linha do principal.

48
00:02:18,470 --> 00:02:21,660
>> Então, criamos um novo quadro de pilha para o principal.

49
00:02:21,660 --> 00:02:23,320
E está indo para começar a corrida.

50
00:02:23,320 --> 00:02:25,270
Principais chamadas printf.

51
00:02:25,270 --> 00:02:29,390
E printf vai
imprimir fatorial de 5.

52
00:02:29,390 --> 00:02:31,440
Bem, ele não sabe
o fatorial de 5 é,

53
00:02:31,440 --> 00:02:35,620
e por isso esta chamada já é
dependendo de uma outra chamada de função.

54
00:02:35,620 --> 00:02:37,270
Assim principal vai parar aí.

55
00:02:37,270 --> 00:02:39,103
Eu vou deixar o seu
seta para a direita lá, cor

56
00:02:39,103 --> 00:02:41,360
que a mesma cor que o
empilhar quadro à direita,

57
00:02:41,360 --> 00:02:47,720
para indicar que o principal vai congelar
aqui enquanto fatorial de 5 é chamado.

58
00:02:47,720 --> 00:02:49,300
>> Então fatorial de 5 é chamado.

59
00:02:49,300 --> 00:02:53,160
E ele vai começar no
início da função fatorial.

60
00:02:53,160 --> 00:02:55,440
Ele faz a pergunta que eu estou igual a 1?

61
00:02:55,440 --> 00:02:56,810
5 é igual a 1?

62
00:02:56,810 --> 00:02:57,410
Bem não.

63
00:02:57,410 --> 00:03:01,110
Então, ele vai descer para
a outra parte, o retorno n vezes

64
00:03:01,110 --> 00:03:02,990
fatorial de n menos 1.

65
00:03:02,990 --> 00:03:03,490
Bem ok.

66
00:03:03,490 --> 00:03:07,070
>> Então, agora, fatorial de 5 é
dependendo outra chamada

67
00:03:07,070 --> 00:03:09,740
a fatorial, passando
em 4 como o parâmetro.

68
00:03:09,740 --> 00:03:14,210
E assim o fatorial de
5 quadro, que moldura vermelha,

69
00:03:14,210 --> 00:03:17,160
vai congelar ali
em que a linha eu indiquei

70
00:03:17,160 --> 00:03:21,914
e esperar por fatorial de 4 para terminar
o que ele precisa fazer para que, em seguida,

71
00:03:21,914 --> 00:03:23,330
pode se tornar o quadro ativo novamente.

72
00:03:23,330 --> 00:03:26,890
>> Então fatorial de 4 começa em
o início da factorial.

73
00:03:26,890 --> 00:03:28,556
4 é igual a 1?

74
00:03:28,556 --> 00:03:30,180
Não, por isso vai fazer a mesma coisa.

75
00:03:30,180 --> 00:03:31,590
Vai descer o ramo mais.

76
00:03:31,590 --> 00:03:33,240
Vai chegar a essa linha de código.

77
00:03:33,240 --> 00:03:35,710
OK, eu vou devolver quatro vezes.

78
00:03:35,710 --> 00:03:41,270
Oh, fatorial de 3-- tão fatorial
4 depende fatorial de 3 de acabamento.

79
00:03:41,270 --> 00:03:43,055
>> E por isso precisa chamar fatorial 3.

80
00:03:43,055 --> 00:03:45,180
E isso vai passar por
o mesmo processo mais uma vez.

81
00:03:45,180 --> 00:03:48,200
Ele começa a passar, fica aqui.

82
00:03:48,200 --> 00:03:50,980
Fatorial de 3 depende
em factorial de 1.

83
00:03:50,980 --> 00:03:53,750
Então fatorial de 2 começa, fica aqui.

84
00:03:53,750 --> 00:03:56,310
Depende factorial de 1.

85
00:03:56,310 --> 00:03:57,430
Fatorial de 1 começa.

86
00:03:57,430 --> 00:03:57,650
>> ESTÁ BEM.

87
00:03:57,650 --> 00:03:59,775
Então, agora, estamos chegando
em algum lugar interessante, certo?

88
00:03:59,775 --> 00:04:02,190
Então agora, 1 é igual a 1.

89
00:04:02,190 --> 00:04:05,130
E assim voltamos 1.

90
00:04:05,130 --> 00:04:06,770
Neste momento, estamos a voltar.

91
00:04:06,770 --> 00:04:07,880
A função é feito.

92
00:04:07,880 --> 00:04:11,140
É um comportamento é-- há
nada mais para ele fazer,

93
00:04:11,140 --> 00:04:17,006
e assim o quadro de pilha para
fatorial de 1 aparece fora.

94
00:04:17,006 --> 00:04:17,589
Está pronto.

95
00:04:17,589 --> 00:04:19,480
Voltou 1.

96
00:04:19,480 --> 00:04:23,370
E agora, fatorial de 2, que
foi a trama imediatamente abaixo dela

97
00:04:23,370 --> 00:04:26,160
na pilha, se torna o quadro ativo.

98
00:04:26,160 --> 00:04:29,030
>> E ele pode pegar
exatamente de onde parou.

99
00:04:29,030 --> 00:04:32,240
Ele está esperando por um fatorial
de 1 para terminar o seu trabalho.

100
00:04:32,240 --> 00:04:33,610
Ele já terminou.

101
00:04:33,610 --> 00:04:35,510
E então aqui estamos.

102
00:04:35,510 --> 00:04:38,080
>> Factorial de 1 devolvido um valor de 1.

103
00:04:38,080 --> 00:04:42,430
Então fatorial de 2 lata
digamos voltar 2 vezes 1.

104
00:04:42,430 --> 00:04:43,680
O seu trabalho já está feito.

105
00:04:43,680 --> 00:04:49,110
É devolvido 2 a fatorial
de 3, que estava esperando por ele.

106
00:04:49,110 --> 00:04:53,370
Fatorial de 3 agora é quadro superior,
a moldura activa na pilha.

107
00:04:53,370 --> 00:04:58,617
E assim se diz, OK, bem, eu vou
para retornar 3 vezes 2, que é 6.

108
00:04:58,617 --> 00:05:00,700
E eu vou dar que
valor de volta para fatorial

109
00:05:00,700 --> 00:05:03,430
de 4, que tem sido esperando por mim.

110
00:05:03,430 --> 00:05:04,500
Terminei.

111
00:05:04,500 --> 00:05:09,410
Fatorial de 3 aparece fora da pilha, e
fatorial de 4 é agora o quadro ativo.

112
00:05:09,410 --> 00:05:13,510
>> 4 diz: OK, eu vou voltar 4 vezes
o fatorial de 3, que tinha seis anos.

113
00:05:13,510 --> 00:05:15,980
Isso era de valor que
factorial de 3 devolvido.

114
00:05:15,980 --> 00:05:19,010
E assim é 4 vezes 6 24.

115
00:05:19,010 --> 00:05:20,990
E eu vou passar
que volta à fatorial

116
00:05:20,990 --> 00:05:23,160
de 5, que tem sido esperando por mim.

117
00:05:23,160 --> 00:05:25,270
Fatorial de 5 é agora o quadro ativo.

118
00:05:25,270 --> 00:05:30,700
Vai voltar 5 vezes
fatorial de 4-- 5 vezes 24, ou 120--

119
00:05:30,700 --> 00:05:32,722
e dar esse valor
de volta à principal, que tem

120
00:05:32,722 --> 00:05:35,680
estava esperando com muita paciência para uma
longo período de tempo na parte inferior da pilha.

121
00:05:35,680 --> 00:05:36,640
>> É onde tudo começou.

122
00:05:36,640 --> 00:05:37,670
Ele fez esta chamada.

123
00:05:37,670 --> 00:05:39,400
Vários quadros assumiu no topo.

124
00:05:39,400 --> 00:05:41,890
É agora de volta ao topo da pilha.

125
00:05:41,890 --> 00:05:43,450
É o quadro ativo.

126
00:05:43,450 --> 00:05:47,810
Assim principal adquiriu-se o valor 120
de volta de fatorial de 5.

127
00:05:47,810 --> 00:05:50,750
Ele está esperando para
imprimir esse valor.

128
00:05:50,750 --> 00:05:51,657
E então ele é feito.

129
00:05:51,657 --> 00:05:53,240
Não há é mais linhas de código em principal.

130
00:05:53,240 --> 00:05:56,800
Então quadro da principal aparece fora
a pilha, e estamos a fazer.

131
00:05:56,800 --> 00:05:58,992
>> E é assim que funciona a recursividade.

132
00:05:58,992 --> 00:06:00,200
Isso é como quadros de pilha funciona.

133
00:06:00,200 --> 00:06:03,120
Essas chamadas de função
que aconteceu anteriormente

134
00:06:03,120 --> 00:06:06,620
são apenas em pausa, esperando
para as chamadas subseqüentes

135
00:06:06,620 --> 00:06:12,050
para terminar, para que possam tornar-se o ativo
enquadrar e terminar o que eles precisam fazer.

136
00:06:12,050 --> 00:06:13,060
>> Eu sou Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Este é CS50.

138
00:06:14,880 --> 00:06:16,580