Na aula anterior nós construímos uma função recursiva para calcular o fatorial de um número digitado pelo usuário. Contudo, talvez tenha ficado aquela dúvida, mas afinal, como funciona a recursão para calcular o fatorial de um número?
Esta aula tem o objetivo de responder esta pergunta e deixar claro como funciona a recursão para calcular o fatorial de um número.
Imagine que foi digitado o valor 4 para n. Vamos simular passo a passo como será calculado o fatorial de 4 com nossa função recursiva.
Como 4 é diferente de 0 e 1 será então executado o else com a chamada recursiva. O computador precisa saber para onde ele deve retornar quando a chamada recursiva que será feita terminar. Assim, ele salva o valor de todas as variáveis e da chamada recursiva em uma pilha de recursão. É como se o computador tirasse uma fotografia daquele momento. Dessa forma, quando a chamada recursiva finalizar e retornar algum valor, o computador sabe o que fazer com aquele valor.
Dessa forma, nossa pilha de recursão, até então vazia, ficará assim:
pilha: 4 * fatorial(3)
Uma fez empilhado os dados, o computador vai então resolver a chamada recursiva para n = 3. Como 3 é diferente de 0 e 1, novamente vai para o else com uma nova chamada recursiva. Nossa pilha de recursão fica assim:
pilha: 3 * fatorial(2)
pilha: 4 * fatorial(3)
Com os dados novamente empilhado, o computador vai agora resolver a chamada com o valor 2. Como 2 é diferente de 0 e 1, novamente será executado o else e uma nova chamada recursiva.
pilha: 2 * fatorial(1)
pilha: 3 * fatorial(2)
pilha: 4 * fatorial(3)
Perceba que nossa pilha possui 3 níveis e agora foi feito uma chamada recursiva com o valor 1. Quando o computador vai resolver essa chamada recursiva, o teste realizado no if é verdadeiro e dentro do if não há nenhuma chamada recursiva, apenas o retorno do valor 1.
Quando esse valor é retornado ele é retornado exatamente para a última chamada recursiva, ou seja, para o topo da nossa pilha de recursão, que possui os dados da última chamada recursiva realizada.
pilha: 2 * fatorial(1)
pilha: 3 * fatorial(2)
pilha: 4 * fatorial(3)
Agora, como o computador já sabe o resultado da chamada fatorial(1), ele então pode fazer a multiplicação com o valor de n naquele momento, que é 2. Assim temos:
resultado parcial: 2 * 1 = 2
pilha: 3 * fatorial(2)
pilha: 4 * fatorial(3)
Novamente, como o computador já sabe o resultado da chamada fatorial(2), ele então pode fazer a multiplicação com o valor de n naquele momento, que é 3. Assim temos:
resultado parcial: 2 * 3 = 6
pilha: 4 * fatorial(3)
Percebe que nossa pilha está diminuindo de tamanho. Como o computador já sabe o resultado da chamada fatorial(3), ele então pode fazer a multiplicação com o valor de n naquele momento, que é 4. Assim temos:
resultado parcial: 6 * 4 = 24
pilha:
Perceba que agora nossa pilha de recursão está vazia. Isso significa que já temos o resultado do fatorial de n. O que acontece então com o resultado 24? Ele é retornado para o local onde foi feita a chamada à função fatorial, que provavelmente foi na função main.
