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.