Enunciado
Dado um número, calcule o fatorial de forma recursiva.
Entrada
A entrada consiste em um número inteiro positivo X maior que zero.
Saída
Imprima o fatorial de X. Não se esqueça de quebrar uma linha ao finalizar o programa.
| Exemplos de Entrada | Exemplos de Saída |
| 5 | 120 |
| 3 | 6 |
Discutindo o Problema
Entenda que uma função recursiva é aquela que é capaz de chamar a si própria. Para que isso funcione, a cada chamada iremos passar uma versão menor do nosso problema até chegarmos em um caso base.
Vamos aplicar esta ideia no calculo fatorial de um número, para isso devemos antes entender o que é um fatorial. Matematicamente temos que:
De forma prática isso quer dizer que se por exemplo queremos calcular o fatorial de 5, devemos realizar o seguinte calculo:
Temos duas considerações a fazer sobre o cálculo acima, perceba como a cada novo número, temos uma parcela menor do problema, isto é, 5! é igual à 5 * 4!, que é igual à 5 * 4 * 3!, que é igual à 5 * 4 * 3 * 2! que por sua vez é igual à 5 * 4 * 3 * 2 * 1 * 0! e que por fim é igual à 5 * 4 * 3 * 2 * 1 * 1.
Nossa segunda consideração diz respeito ao caso base, perceba como o problema termina quando chegamos ao número 1, logo podemos reescrever nossa fórmula da seguinte forma:
Vamos agora montar a função básica do problema, para isso lembre-se que temos que definir o caso base e descrever as parcelas menores do problema de forma recursiva.
Para identificarmos o caso base iremos utilizar a estrutura condicional “if” de tal forma a identificar o número 1.
Caso o número seja diferente de 1 chamamos novamente nossa função, porém agora com uma parte menor do problema, ou seja, se temos n como primeiro valor, vamos então chamar novamente a função até que tenhamos n-1, n-2, …, 1.
A melhor forma de entender esse processo é quebrando nossa função em diversas outras funções assim como demonstrado abaixo:
Perceba como uma função recursiva nada mais é do que chamar a mesma função n vezes escrevendo a sua estrutura apenas 1 vez. Como resultado em vermelho você pode perceber que estamos realizando nada mais do que o produto de 5*4*3*2*1.
Código Fonte
Java
C/C++
Python
Qualquer dúvida deixe nos comentários abaixo. Até o próximo artigo!
