O que é Recursividade ?

Recursividade é a definição de um método que chama a si mesmo.

• Ele tem o poder de substituir um ou mais laços na programação.

• Algoritmos simples recursivos podem ser substituídos facilmente por algoritmos simples iterativos (com laços) .

Existem problemas mais complexos em que a solução é inerente recursiva, como o QuickSort, onde a solução iterativa é bastante difícil de ser encontrada.

• Abaixo, um exemplo de duas funções que calcula o fatorial de um número. A primeira é iterativa e a segunda é recursiva:

Função interativa (em Java):

public int fatorial(int num){
int resultado = 1;
for(int i = 1; i <= num; i++){
resultado = resultado * i;
}
return resultado;
}

Função recursiva (em Java):

public int fatorial(int num){
if(num <= 1){
return 1;
}else{
return num*fatorial(num – 1);
}
}
}

A função fatorial() recursiva funciona da seguinte maneira:

1. suponha que é chamado fatorial(4)
2. num = 4
3. Como 4 é maior que 1, irá para o else. O valor de retorno será 4 * fatorial(4-1)
4. Ou seja, há outra chamada da função, só que agora fatorial(3).
5. Ele só pode calcular a multiplicação após calcular o fatorial(3)
6. Na chamada fatorial(3), será o mesmo processo. Irá retornar 3*fatorial(3-1)
7. Na chamada fatorial(2), será o mesmo processo. Irá retornar 2*fatorial(2-1)
8. Na chamada fatorial(1), ele entrará no IF, e retornará 1.
9. Portanto, pode-se voltar a quem chamou ele, e realizar a multiplicação: 2*fatorial(2-1) → 2*1 → 2
10. Portanto, pode-se voltar a quem chamou ele, e realizar a multiplicação: 3*fatorial(3-1) → 3*2 → 6
11. Portanto, pode-se voltar a quem chamou ele, e realizar a multiplicação: 4*fatorial(4-1) → 4*6 → 24
12. Assim, ele determina a resposta de fatorial(4.

Agradecimento ao professor Herlon Cortez pelo fornecimento do material do post.