Algoritmos recursivos

Definição

Os algoritmos recursivos fundamentam-se no conceito matemático da recursividade, que é definida como a execução de um processo ou procedimento de maneira repetitiva.

Se você ainda não sabe o que é recursividade, clique aqui e acesse o artigo onde te explicamos detalhadamente sobre o assunto.

Da maneira mais simplificada possível, um algoritmo recursivo é um algoritmo que possui em seu corpo uma função recursiva, uma função que possui uma chamada a si própria. Veja no código abaixo o exemplo de uma função recursiva denominada func(). Observe que na linha 4 existe uma chamada de função bem suspeita. Trata-se de uma chamada para a própria função func().

1.public void func(int n) {
2.    if(n==0) return;
3.    func(n-1);
4.}

Apesar de não parecer algo muito significativo (e até sem muito sentido à primeira vista), esse mecanismo de chamada recursiva é útil e muito poderoso para resolver diversos problemas computacionais.

Portanto, sempre que vir um algoritmo que possui em sua estrutura chamadas de funções para si próprias, saberá que se trata de um algoritmo recursivo.

Estrutura de um algoritmo recursivo

O grande problema das funções recursivas está em seu fluxo de execução infinito. Como a função chama a si própria, ela acaba criando um ciclo de chamadas sem fim. Observe na imagem abaixo a ilustração desse problema.

Por este motivo, as funções recursivas possuem uma estrutura composta por elementos que permitem controlar o momento em que essas chamadas recursivas são interrompidas. Esses elementos são:

• Caso base – um condicional que permite definir quando a função irá parar de chamar a si própria.
• Passo recursivo – código do algoritmo que contém a(s) chamada(s) recursiva(s).

Para entender essa estrutura, vamos visualizar um algoritmo que calcula o somatório dos n primeiros números naturais. Por exemplo: se for informado o valor 6, o algoritmo deve dar como resposta o valor 21, pois 6+5+4+3+2+1 = 21.

Veja abaixo a implementação recursiva do algoritmo. A variável n (linha 1) recebe o valor cujo somatório será calculado. Observe nas linhas 2 e 3 que o caso base é definido por um condicional, que impõe uma condição de parada para as chamadas recursivas. O resto do conteúdo da função (linha 4) é o passo recursivo.

1.public int sum(int n) {
2.    if(n==1) // caso base
3.            return 1;
4.    return n + sum(n-1); // passo recursivo
5.}

Algoritmo recursivo versus algoritmo iterativo

Para todo algoritmo recursivo existe um algoritmo correspondente iterativo (não recursivo) que consegue resolver o mesmo problema. O termo iterativo se refere àqueles algoritmos que utilizam estruturas de repetição. Ex.: “for”, “while”, “do-while”.

Para visualizar a diferença entre as implementações recursiva e iterativa, vamos analisar o algoritmo que calcula o Fatorial. Este algoritmo calcula o produto dos n primeiros números naturais positivos. Por exemplo: se for informado o valor 5, o algoritmo deve dar como resposta o valor 120, pois 5×4×3×2×1 = 120.

Veja abaixo a diferença entre as implementações recursiva e iterativa do algoritmo que calcula o Fatorial de um número n informado.

1.public int fat(int n) {
2.    if(n==1) // caso base
3.            return 1;
4.    return n * fat(n-1); // passo recursivo
5.}

1.public int fat(int n) {
2.    int fat = n;
3.    for(int i = 1; i < n; i++) {
4.            fat = fat*i;
5.    }
6.    return fat;
7.}

É possível perceber que a principal vantagem dos algoritmos recursivos sobre os iterativos é a clareza e legibilidade do algoritmo gerado. Não que os iterativos sejam bagunçados, mas, devido à sua própria natureza e estrutura padronizada, os algoritmos recursivos acabam fornecendo um maior nível de elegância para expressar soluções.

Vejamos outro exemplo. Desta vez com algoritmo que calcula o n-ésimo termo da sequência de Fibonacci.

Se você ainda não sabe o que é a sequência de Fibonacci, clique aqui e acesse o artigo sobre recursividade. Ele tem uma sessão que fala sobre essa sequência.

Observe no código abaixo como a implementação iterativa de Fibonacci é bem grande, mas perceba que a versão recursiva se mantém simples e enxuta.

1.public int fib(int n) {
2.    if(n==1 || n==2) // caso base
3.            return 1;
4.    return fib(n-1) + fib(n-2); // passo recursivo
5.}

1.public static int fib(int n){
2.    int F = 0; // atual
3.    int ant = 0; // anterior
4.    for (int i = 1; i <= n; i++) {
5.        if (i == 1) {
6.            F = 1;
7.            ant = 0;
8.        } else {
9.            F += ant;
10.            ant = F - ant;
11.        }
12.    }
13.    return F;
14.}

O alto consumo de memória dos algoritmos recursivos

Apesar dessa vantagem estética, os algoritmos recursivos possuem uma ENORME desvantagem (em relação aos iterativos) no quesito “uso de recursos computacionais”.

Pelo fato de cada chamada recursiva criar uma nova instância da função, o consumo de memória computacional pode ser devastador. Uma verdadeira bomba relógio, se não for usado com bastante cautela.

A imagem abaixo ilustra o que acontece nas chamadas recursivas para o algoritmo que calcula o somatório dos n primeiros números naturais (visto na seção anterior). Neste exemplo estamos ilustrando o cálculo do somatório dos 3 primeiros números. Observe que cada nova chamada cria uma nova instancia da função e, consequentemente, novas variáveis alocadas na memória do computador. Ou seja, a quantidade de memória alocada é o triplo!

1.public int sum(int 3) {
2.    if(3==1)
3.        return 1;
4.    return n + sum(2);
5.}

1.public int sum(int 2) {
2.    if(2==1)
3.        return 1;
4.    return n + sum(1);
5.}

1.public int sum(int 1) {
2.    if(1==1)
3.        return 1;
4.    return n + sum(0);
5.}

Desta forma, a quantidade de memória consumida pela execução de um algoritmo recursivo é diretamente proporcional à quantidade de repetições. Se no algoritmo ilustrado acima quiséssemos calcular o somatório dos 1000 primeiros números naturais, seriam 1000 chamadas recursivas e 1000 vezes a mais de memória consumida.

A execução de um algoritmo recursivo

Outra grande dificuldade que você pode ter com os algoritmos recursivos é compreender como eles são executados de fato. Por exemplo: acompanhar a sua execução em um teste de mesa.

A despeito da sua elegância e simplicidade sintática, os algoritmos recursivos guardam grande complexidade na maneira como são executados, pois criam uma estrutura hierárquica durante a sua execução (uma árvore de chamadas recursivas), e essa é a principal característica que dificulta a sua correta compreensão.

Para compreender como isso ocorre na prática, vamos observar a execução ilustrada do algoritmo recursivo genérico, um algoritmo inútil que apenas faz chamas recursivas sem nenhum objetivo prático. Observe no código abaixo:

1.public void func(int n) {
2.    if(n==0)
3.            return;
4.    func(n-1);
5.}

Vamos simular a execução desse algoritmo para um valor n=3. Observe na ilustração abaixo que a execução cria uma estrutura em forma hierárquica. Cria uma árvore de chamadas recursivas definida em 4 níveis, representando em cada um deles uma chamada recursiva subsequente.

Observe na imagem acima que o valor n=3 é submetido à função func() (nível 0). A partir desse ponto, o valor de n (inicialmente igual a 3) vai sendo decrementado a cada nova chamada recursiva, até que o caso base onde n=0 (nível 3) seja alcançado.

Após alcançar o caso base, as chamadas recursivas vão sendo retornadas para as chamadas anteriores, realizando um processo chamado desempilhamento.

Múltiplas chamadas recursivas

Outro fator que impacta a complexidade de um algoritmo recursivo é a quantidade de chamadas recursivas existentes no passo recursivo. Observe no código abaixo um algoritmo genérico que possui 2 chamadas recursivas (linhas 4 e 5).

1.public void func(int n) {
2.    if(n==0) // caso base
3.        return;
4.    func(n-1); // passo recursivo
5.    func(n-1); // passo recursivo
6.}

Vamos simular a execução desse algoritmo para um valor n=3. Observe na ilustração abaixo que a execução cria uma estrutura hierárquica em formato de árvore. Perceba que cada nó da árvore gera outros 2 nós. Isto acontece porque as duas chamadas recursivas (linhas 4 e 5 do código acima) dão origem a dois fluxos de chamadas recursivas distintos. Como se fossem duas novas dimensões originadas de uma mesma chamada.

Essas observações nos mostram duas propriedades muito importantes dos algoritmos recursivos:

1. a quantidade de filhos gerados a partir de cada um dos nós da árvore de chamadas recursivas é igual à quantidade de chamadas recursivas existentes no passo recursivo do algoritmo.
2. a quantidade de nós em toda a árvore é igual à quantidade total de chamadas da função recursiva.

Agora a sua vez de demonstrar o seu conhecimento!

Exercício 1

Desenhe a árvore de chamadas recursivas para o algoritmo recursivo abaixo (considere o n=2):

1.public void func(int n) {
2.    System.out.println("nova chamada");
3.    if(n==0)
4.        return;
5.    func(n-1);
6.    func(n-1);
7.    func(n-1);
8.}

Exercício 2

Desenhe a árvore de chamadas recursivas para o algoritmo recursivo abaixo (considere o n=3):

1.public void func(int n) {
2.    System.out.println("nova chamada");
3.    if(n<=0)
4.        return;
5.    func(n-1);
6.    func(n-2);
7.    func(n-3);
8.}