Desmistificando os algoritmos recursivos – Os algoritmos recursivos são fundamentais na solução de muitos problemas envolvendo a computação, ainda assim, muitos programadores os veem como algo complexo e de difícil implementação.
Como disse o prof. Siang Wun Song:
Para fazer um procedimento recursivo é preciso ter fé.
Calma! Apesar da fala do prof. Siang, implementar um algoritmo recursivo não é um bicho de sete cabeças. Veremos alguns passos para compreendê-los de vez. o/
Primeiramente devemos entender o que é a recursividade. Uma função recursiva chama a si mesma dentro do próprio escopo. Pode ser uma recursão direta onde uma função A chama a própria função A ou uma recursão indireta onde uma função A chama uma função B que por sua vez chama a função A. Além de chamar a si mesma, a função recursiva deve possuir uma condição de parada que a impedirá de entrar em loop infinito.
Antes de criar uma função recursiva para determinado problema, é preciso saber se ele possui uma estrutura recursiva. Neste caso, devemos verificar se parte do problema possui o mesmo tipo do original, assim podemos dizer que a solução para ele é a recursividade. Para compreender melhor, vamos analisar o caso do somatório onde temos um número natural n >= 0 e queremos descobrir a soma de todos os números de n até 0.
Algoritmo
Antes de criar o algoritmo devemos extrair dois elementos do problema: O caso base que se tornará a condição de parada e o passo recursivo. Vejamos algumas possíveis iterações do problema:
No caso do somatório, é possível identificar que para cada valor de n o último elemento sempre é 0, assim podemos confirmar que este é o caso base.
Analisando um pouco mais as iterações temos que para cada valor de n vamos diminuindo em 1 até que chegue ao valor 0.
Assim, nós temos que o somatório de um número natural n é o próprio n adicionado ao somatório do número antecessor (Somatório de n = n + (n-1) + (n-2) + ... + 0). Logo, o nosso passo recursivo é n + soma(n-1).
Sabemos que o caso base é 0 e o somatório de 0 é ele mesmo, estão essa será a nossa condição de parada. O nosso passo recurso é n + soma(n-1), assim já temos os elementos da nossa função recursiva e podemos criá-la:
int soma(int n){
if(n == 0)
return 0;
return n + soma(n-1);
}
Esta é a implementação em C para resolver o problema de forma recursiva. Para um número natural n informado, a função irá executar até que seja encontrado o caso base e assim retornar o valor do somatório.
Vamos analisar outro problema clássico que pode ser resolvido com recursividade: o fatorial de um número natural n >= 1. O fatorial é bem semelhante ao somatório, porém é feito com multiplicação sucessiva.
Vamos analisar as possíveis iterações:
No exemplo do fatorial, o nosso caso base é 1, portanto, a nossa condição de parada será verificar se o número é 1 e, caso seja, a função deverá retorná-lo. Também é possível definir o nosso passo recursivo: fatorial de n = n x (n - 1) x (n - 2) x ... x 1 logo n! = n x fatorial(n - 1). Por fim, chegamos à seguinte implementação em C:
int fatorial(int n){
if(n == 1)
return 1;
return n * fatorial(n-1);
}
Conclusão
Uma grande vantagem da recursividade é o fato de gerar uma redução no tamanho do algoritmo, permitindo descrevê-lo de forma mais clara e concisa. Porém, todo cuidado é pouco ao se fazer módulos recursivos. Basta seguir estes passos e você não terá grandes problemas. Como disse L. Peter Deutsch:
Iterar é humano, fazer recursão é divino.