DOUG LLOYD: Se você já viu o vídeo em recursão,
todo o processo pode ter parecia um pouco mágico.
Como funciona?
Como as funções de saber que eles precisamos esperar e esperar por um outro valor
para retornar de uma função diferente chamar a fim de obter o resultado que queremos?
>> Bem, a razão é porque isso funciona de algo conhecido como a pilha de chamadas.
Quando você chamar uma função, o sistema deixa de lado o espaço na memória
para essa função para fazer seu trabalho.
E nós chamamos esses blocos de memória que estão sendo retiradas para cada função
chamar um quadro de pilha ou uma moldura função.
E como você poderia esperar, estes quadros de pilha
vivem na parte pilha de memória.
>> Mais do que uma função de quadro de pilha podem existir em memória num dado momento.
Se principal chama um movimento função, e chama movimento direção,
todas as três funções têm quadros abertos.
Mas eles não têm quadros ativos.
Estes quadros são dispostas numa pilha.
E o quadro do mais recentemente chamado
função é sempre no topo da pilha.
E isso é sempre o quadro ativo.
Só há realmente sempre uma função que é ativo em um tempo.
É um no topo da pilha.
>> Quando uma função chama outra função, ele pressiona tipo de pausa.
É uma espécie de está em espera, esperando.
E um outro quadro de pilha é empurrado para a pilha em cima dela.
E isso se torna o quadro ativo.
E o quadro imediatamente abaixo dele necessita de esperar
até que seja novamente o quadro ativo antes que ele possa retomar o seu trabalho.
Quando uma função é completo e ele é feito,
seu quadro é retirado da pilha.
Essa é a terminologia.
E o quadro imediatamente abaixo dele, como acabei de dizer,
torna-se o novo quadro ativo.
>> E se ele chama outra função, ele vai parar novamente.
Pilha quadro que nova função será ser empurrada para o topo da pilha.
Ele vai fazer o seu trabalho.
Ele pode aparecer de volta fora.
E a outra função abaixo dele pode retomar novamente.
>> Então, vamos passar por isso de novo, olhando com a idéia da função fatorial
que definido na vídeo recursão para ver
exatamente como a magia por trás disso processo recursivo está ocorrendo.
Portanto, este é todo o nosso arquivo, certo?
Nós definimos dois funções no principal e fato.
E, como seria de esperar, qualquer programa C vai
para começar na primeira linha do principal.
>> Então, criamos um novo quadro de pilha para o principal.
E está indo para começar a corrida.
Principais chamadas printf.
E printf vai imprimir fatorial de 5.
Bem, ele não sabe o fatorial de 5 é,
e por isso esta chamada já é dependendo de uma outra chamada de função.
Assim principal vai parar aí.
Eu vou deixar o seu seta para a direita lá, cor
que a mesma cor que o empilhar quadro à direita,
para indicar que o principal vai congelar aqui enquanto fatorial de 5 é chamado.
>> Então fatorial de 5 é chamado.
E ele vai começar no início da função fatorial.
Ele faz a pergunta que eu estou igual a 1?
5 é igual a 1?
Bem não.
Então, ele vai descer para a outra parte, o retorno n vezes
fatorial de n menos 1.
Bem ok.
>> Então, agora, fatorial de 5 é dependendo outra chamada
a fatorial, passando em 4 como o parâmetro.
E assim o fatorial de 5 quadro, que moldura vermelha,
vai congelar ali em que a linha eu indiquei
e esperar por fatorial de 4 para terminar o que ele precisa fazer para que, em seguida,
pode se tornar o quadro ativo novamente.
>> Então fatorial de 4 começa em o início da factorial.
4 é igual a 1?
Não, por isso vai fazer a mesma coisa.
Vai descer o ramo mais.
Vai chegar a essa linha de código.
OK, eu vou devolver quatro vezes.
Oh, fatorial de 3-- tão fatorial 4 depende fatorial de 3 de acabamento.
>> E por isso precisa chamar fatorial 3.
E isso vai passar por o mesmo processo mais uma vez.
Ele começa a passar, fica aqui.
Fatorial de 3 depende em factorial de 1.
Então fatorial de 2 começa, fica aqui.
Depende factorial de 1.
Fatorial de 1 começa.
>> ESTÁ BEM.
Então, agora, estamos chegando em algum lugar interessante, certo?
Então agora, 1 é igual a 1.
E assim voltamos 1.
Neste momento, estamos a voltar.
A função é feito.
É um comportamento é-- há nada mais para ele fazer,
e assim o quadro de pilha para fatorial de 1 aparece fora.
Está pronto.
Voltou 1.
E agora, fatorial de 2, que foi a trama imediatamente abaixo dela
na pilha, se torna o quadro ativo.
>> E ele pode pegar exatamente de onde parou.
Ele está esperando por um fatorial de 1 para terminar o seu trabalho.
Ele já terminou.
E então aqui estamos.
>> Factorial de 1 devolvido um valor de 1.
Então fatorial de 2 lata digamos voltar 2 vezes 1.
O seu trabalho já está feito.
É devolvido 2 a fatorial de 3, que estava esperando por ele.
Fatorial de 3 agora é quadro superior, a moldura activa na pilha.
E assim se diz, OK, bem, eu vou para retornar 3 vezes 2, que é 6.
E eu vou dar que valor de volta para fatorial
de 4, que tem sido esperando por mim.
Terminei.
Fatorial de 3 aparece fora da pilha, e fatorial de 4 é agora o quadro ativo.
>> 4 diz: OK, eu vou voltar 4 vezes o fatorial de 3, que tinha seis anos.
Isso era de valor que factorial de 3 devolvido.
E assim é 4 vezes 6 24.
E eu vou passar que volta à fatorial
de 5, que tem sido esperando por mim.
Fatorial de 5 é agora o quadro ativo.
Vai voltar 5 vezes fatorial de 4-- 5 vezes 24, ou 120--
e dar esse valor de volta à principal, que tem
estava esperando com muita paciência para uma longo período de tempo na parte inferior da pilha.
>> É onde tudo começou.
Ele fez esta chamada.
Vários quadros assumiu no topo.
É agora de volta ao topo da pilha.
É o quadro ativo.
Assim principal adquiriu-se o valor 120 de volta de fatorial de 5.
Ele está esperando para imprimir esse valor.
E então ele é feito.
Não há é mais linhas de código em principal.
Então quadro da principal aparece fora a pilha, e estamos a fazer.
>> E é assim que funciona a recursividade.
Isso é como quadros de pilha funciona.
Essas chamadas de função que aconteceu anteriormente
são apenas em pausa, esperando para as chamadas subseqüentes
para terminar, para que possam tornar-se o ativo enquadrar e terminar o que eles precisam fazer.
>> Eu sou Doug Lloyd.
Este é CS50.