Um assunto simples, porém complexo:
Mais afinal, o que é recursão?
Em programação, a maneira mais simples de explicar o que é recursão é dizer que ela é um método de programação no qual um função chama a si mesma.
A chamada de um método para ele mesmo, é igual a chamada de qualquer outro método, exemplo de método recursivo que calcula o fatorial n!:
O fatorial de um número é dado pela multiplicação de seus antecessores, ou seja, se n é igual 3, então seu fatorial será 3 * 2 * 1. O fatorial de 0! (zero) é igual a 1.
int fat(int num){
int fato;
if (num == 1)
return (1);
else
fato = num * fat (num-1);
return fato;
}
Em qualquer algorítimo recursivo, devemos nos atentar a necessidade de um ponto de parada, ou seja, uma condição aonde a recursão irá parar de se chamar.
No exemplo acima, essa condição é quando o fatorial for igual a 0 (Zero), na fórmula (desenho acima): Retorne 1 Se N for igual a 0
#include <stdio.h>
#include <stdlib.h>
int fat(int num){
int fato;
if (num == 1)
return (1);
else
fato = num * fat (num-1);
return fato;
}
int main(void){
int numero;
printf("\nEntre com um numero positivo.");
scanf("%u", &numero);
printf("O fatorial de %u vale %u.\n", numero, fat(numero));
}
Chamando o método fatorial(3), queremos calcular 3 * 2 * 1.
-> 3 * fatorial(2) retorna (6)
-> -> 2 * fatorial(1) retorna (2)
-> -> -> 1 * fatorial(0) retorna (1)
Explicando o fluxo do programa:
1) O método fatorial recebe o valor de x igual a 3, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 3 multiplicado por fatorial(2), neste ponto estamos fazendo uma chamada recursiva.
2) O método fatorial recebe o valor de x igual a 2, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 2 multiplicado por fatorial(1).
3) O método fatorial recebe o valor de x igual a 1, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 1 multiplicado por fatorial(0).
4) O método fatorial recebe o valor de x igual a 0 (zero), verifica se x é igual a 0 (zero), então para a execução do método e retorna o valor 1.
5) Volta para o método fatorial(1) na linha 26 e faz a multiplicação de x que vale 1 pelo resultado do fatorial(0) que é 1, ou seja 1 * 1 e retorna o valor 1.
6) Volta para o método fatorial(2) na linha 26 e faz a multiplicação de x que vale 2 pelo resultado do fatorial(1) que é 1, ou seja 2 * 1 e retorna o valor 2.
7) Volta para o método fatorial(3) na linha 26 e faz a multiplicação de x que vale 3 pelo resultado do fatorial(2) que é 2, ou seja 3 * 2 e retorna o valor 6.
Volta para o método que chamou o fatorial(3), neste caso o método main na linha 7, guarda o resultado do fatorial(3) que é 6, dentro da variável resp, e imprime o resultado da variável resp na linha 8.
Idéias e mais informações: Blog do Rafael Sakurai, Vale a visita, observem o exemplo de colocar valores em ordem crescente.
Mais links:
Um outro Slide ilustrativo sobre Recursividade:
