Algoritmos Recursivos

Em computação, a recursão é um método de solução de problemas onde versões menores do mesmo problema são solucionadas e os resultados combinados para encontrar a solução do problema original. Esta abordagem pode ser aplicada a diversos tipos de problemas.

A maioria das linguagens de programação suporta recursão, permitindo que uma função ou método invoque a si mesmo. Algumas linguagens de programação funcional não definem nenhuma construção iterativa, baseando-se exclusivamente em chamadas recursivas.

Definição de funções recursivas

Suponha uma situação onde você não possui o operador de soma ($+$), e deve implementar a operação de soma de dois elementos, inteiros, e positivos (ou seja, dois números naturais, ou $i \in \mathbb{N}$ e $j \in \mathbb{N}$), utilizando apenas as operações $succ(n)$, que retorna o sucessor de $n$, ou seja o próximo elemento ou número, e $pred(n)$, que retorna o elemento ou número anterior. Podemos definir a função de soma de dois números $i$ e $j$, inteiros e positivos como:

$$ sum(i,j) = \begin{cases} i & \text{se j = 0,} \\ sum(succ(i),pred(j)) & \text{caso contrário}\end{cases} $$

A execução dessa função para os valores $i = 5$ e $j = 3$, seria então:

$$\begin{align*} sum(5,3) =\, & sum(succ(5), pred(3)) \\ =\, & sum(succ(6), pred(2)) \\ =\, & sum(succ(7), pred(1)) \\ =\, & sum(8, 0) \\ =\, & 8 \end{align*}$$

Uma função recursiva é divida em duas partes, um ou mais casos base, onde o problema é trivialmente solucionável (sem recorrer à recursão), e o processo de recursão, que deve dividir o problema maior em problemas menores de forma que ao executar repetidas vezes a recursão, em algum momento, um dos casos base será atingido.

Note que a função de soma é definida em termos dela mesma, porém, existe uma situação, onde a função não exige a recursão, o caso base, e toda recursão leva, em direção à esse caso base (ou a recursão jamais terminaria).

Veja agora, a definição do fatorial de um número:

O fatorial ($n!$) de um número natural $n$, onde $n \in \mathbb{N}^*$, é dado pela multiplicação de todos os números inteiros, positivos, menores que $n$. Por definição, o fatorial de $0$ ($0!$) é igual a $1$.

Logo, o fatorial de $6$ ($6!$), é o equivalente a:

$$\begin{align*} & 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\ & 6! = 720 \end{align*}$$

Se calcularmos o fatorial de 5 ($5!$), veremos que:

$$\begin{align*} & 5! = 5 \times 5 \times 4 \times 3 \times 2 \times 1 \\ & 5! = 120 \end{align*}$$

Podemos ver, claramente, que:

$$\begin{align*} & 6! = 6 \times 5! \\ & 5! = 5 \times 4! \\ & 4! = 4 \times 3! \\ & (\ldots) \end{align*}$$

Sabendo disso, criamos uma definição recursiva para o fatorial de um número:

$$ fatorial(n) = \begin{cases} 1 & \text{se n = 0} \\ n \times fatorial(n) & \text{se n > 0} \end{cases} $$

Partindo dessa definição recursiva, podemos mostrar a execução da recursão por definição:

$$\begin{align*} fatorial(5) & = 5 \times fatorial(4) \\ & = 5 \times 4 \times fatorial(4) \\ & = 5 \times 4 \times 3 \times fatorial(4) \\ & = 5 \times 4 \times 3 \times 2 \times fatorial(4) \\ & = 5 \times 4 \times 3 \times 2 \times 1 \times fatorial(0) \\ & = 5 \times 4 \times 3 \times 2 \times 1 \times 1 \\ & = 120 \end{align*}$$

A execução da função recursiva do fatorial mostra a redução do problema em intâncias mais simples, até que uma instância do problema seja trivialmente solucionável.

A implementação de um algoritmo recursivo requer suporte da linguagem de programação utilizada, no entanto, quando este suporte existe a implementação é simples, como se pode ver nos exemplos em Python (Algoritmo 1) e Java (Algorimo 2). Note que nas duas implementações não foi tratado o caso do argumento possuir um valor negativo.

Fatorial recursivo em Python

def fatorial(n):
    if n == 0: return 1
    return n * fatorial(n - 1)

Fatorial recursivo em Java

class RecursiveAlgorithms {
    public static double fatorial(int n) {
        if (n == 0) return 1
        return n * fatorial(n - 1)
    }
}

Cálculo do Mínimo Divisor Comum

O mínimo divisor comum (gcd, do inglês Greatest Common Divisor) de dois ou mais inteiros, maiores que zero, é o maior numero inteiro positivo capaz de realizar a divisão inteira dos números sem deixar "resto".

Um método eficiente para calcular o gcd é o algoritmo de Euclides, que pode ser definido, recursivamente, como:

$$ gcd(m,n) = \begin{cases} m & \text{se n = 0}, \\ gcd(n, m \% n) & \text{caso contrario.} \end{cases}$$

O Algoritmo 3, mostra uma implementação recursiva do mesmo algoritmo, cuja implementação é anda mais sucinta que a implementação iterativa (Algoritmo 4).

Algoritmo recursivo para obter o Mínimo Denominador Comum

def gcd(a, b):
    return gcd(b, a % b) if b != 0 else abs(a)

Algoritmo iterativo para obter o Mínimo Denominador Comum

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

N-ésimo número de Fibonacci

Os números de Fibonacci são números que aparecem em uma seqüência descrita pelo matemático italiano Leonardo de Pisa, também conhecido como Fibonacci, e aparecem constantemente na matemática e na natureza.

É possível calcular qualquer número $n$ da seqüência a partira da equação:

$$ fibonacci(n) = \begin{cases} 0 & \text{se n = 0}, \\ 1 & \text{se n = 1}, \\ fibonacci(n - 1) + fibonacci(n - 2) & \text{caso contrario.}, \end{cases}$$

A implementação do algoritmo recursivo é direta, como mostra o Algoritmo 5:

Algoritmo de Fibonacci recursivo.

public static double fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

Na linguaem Python, podemos implementar como lambda (Algoritmo 6):

Algoritmo de Fibonacci recursivo, em uma linha.

fibo = lambda n: 0 if n == 0 else 1 if n == 1 else fibo(n-1)+fibo(n-2)

O problema desta implementação é que para cada recursão, são realizadas duas chamadas à função, e os resultados intermediários não sã reproveitados, e por esse motivo, para números maiores, o algoritmo executa um número muito grande de operações (na ordem de $O(c^N)$).

A versão iterativa (Algoritmo 7) é bem mais eficiente ($O(N)$), e mostra, também, como os algoritmos recursivos podem ser mais simples de ler.

Algoritmo de Fibonacci iterativo.

public static double fibonacci(int n) {
    double f1 = 1, f2 = 0;
    while (n > 0) {
        double t = f1 + f2;
        f1 = f2;
        f2 = t;
        n--;
    }
    return f2;
}

Técnicas como memoization podem ser empregadas para melhorar o tempo de execução da versão recursiva.

Custo da Recursão

Linguagens imperativas normalmente não oferecem otimizações para a execução de chamadas recursivas, o que podem levar ao problema mostrado na implementação recursiva do cálculo dos números de Fibonacci, ou a um maior uso de memória devido ao consumo de dados da pilha, devido ao acúmulo de chamadas recursivas de funções.

Linguagens funcionais permitem uma melhor otimização deste processo, apresentando, em alguns casos, a recursão como úncia forma de iteração, não possuindo construções de repetição como for ou while.

Embora possa parecer que os algoritmos recursivos são menos eficientes, e nunca devem ser utilizados, isto não é verdade, e em diversos casos, estes algoritmos são mais adequados que suas versões iterativas, independentemente da linguagem em que são implementados.