Desmistificando os algoritmos recursivos

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.