Introdução

Nesta aula, vamos mergulhar no conceito de recursão, uma técnica fundamental na ciência da computação. Uma função recursiva é aquela que, durante sua execução, chama a si mesma para resolver uma versão menor do problema original. A recursão aparece em diversos contextos: algoritmos de ordenação (como quicksort e mergesort), percorrimento de árvores, cálculo de sequências matemáticas e resolução de problemas como as Torres de Hanói.

Para que uma recursão seja finita, é necessário definir um ou mais casos base (condições de parada) e um caso recursivo que reduz o problema em direção ao caso base. Sem o caso base, a recursão se tornaria infinita e levaria a um estouro de pilha.

Como Funciona a Recursão

Quando uma função é chamada recursivamente, o sistema operacional aloca um novo quadro na pilha de chamadas (call stack) para cada chamada. Esse quadro contém as variáveis locais, o endereço de retorno e outros dados de contexto. Ao atingir o caso base, as chamadas começam a retornar, um quadro por vez, até que a chamada original seja concluída.

É importante entender que cada chamada recursiva tem seu próprio conjunto de variáveis, independentes das demais. Isso permite que a recursão resolva subproblemas de forma isolada.

Exemplos Clássicos

Fatorial

O fatorial de um número n (n!) é definido como n × (n-1)!, com 0! = 1. Em Python:

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

A complexidade de tempo é O(n) e a complexidade de espaço (pilha) também O(n).

Fibonacci

A sequência de Fibonacci é definida por F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n ≥ 2.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Essa implementação ingênua tem complexidade exponencial O(2^n), sendo ineficiente para n grandes. Podemos melhorá-la com memoização (programação dinâmica) para obter O(n).

Recursão vs Iteração

Todo algoritmo recursivo pode ser implementado de forma iterativa usando pilhas explícitas. A escolha entre recursão e iteração depende do problema e da legibilidade. Problemas com estrutura naturalmente recursiva (como árvores, expressões matemáticas e algoritmos de divisão e conquista) são mais claros quando escritos recursivamente. Porém, a recursão pode consumir mais memória e ser mais lenta devido ao overhead de chamadas de função. Em linguagens que não otimizam recursão de cauda, a profundidade da recursão é limitada pelo tamanho da pilha.

Recursão de Cauda

Dizemos que uma função é recursiva de cauda (tail recursive) quando a chamada recursiva é a última operação executada pela função, e seu resultado é retornado diretamente. Nesse caso, algumas linguagens conseguem reutilizar o mesmo quadro de pilha (otimização de chamada de cauda), evitando o crescimento da pilha. Python não faz essa otimização, mas o conceito é importante para entender como algumas linguagens funcionais lidam com recursão.

Análise de Complexidade

Para analisar algoritmos recursivos, usamos recorrências. Por exemplo, para o fatorial: T(n) = T(n-1) + O(1), que resolve para O(n). Para Fibonacci ingênuo: T(n) = T(n-1) + T(n-2) + O(1), cuja solução é O(2^n). Já o mergesort tem recorrência T(n) = 2T(n/2) + O(n), resultando em O(n log n). O estudo de recorrências é essencial para entender o desempenho de algoritmos recursivos.

Torres de Hanói

O problema das Torres de Hanói consiste em mover n discos de uma haste origem para uma haste destino, usando uma haste auxiliar, com a restrição de que um disco maior nunca pode ficar sobre um menor. A solução recursiva é:

def hanoi(n, origem, destino, auxiliar):
    if n == 1:
        print(f"Mova o disco 1 de {origem} para {destino}")
    else:
        hanoi(n-1, origem, auxiliar, destino)
        print(f"Mova o disco {n} de {origem} para {destino}")
        hanoi(n-1, auxiliar, destino, origem)

O número de movimentos é 2^n - 1, ou seja, complexidade O(2^n).

Resumo

  • Recursão é uma técnica onde uma função chama a si mesma para resolver subproblemas.
  • Deve conter um ou mais casos base para terminar.
  • A pilha de chamadas armazena o contexto de cada chamada recursiva.
  • Recursão pode ser menos eficiente que iteração em termos de memória e tempo, mas oferece clareza.
  • Recursão de cauda permite otimização em linguagens que suportam.
  • A análise de complexidade envolve recorrências matemáticas.

Perguntas Frequentes

O que é recursão?

Recursão é um método onde a solução de um problema depende de soluções de instâncias menores do mesmo problema, geralmente através de uma função que chama a si mesma.

Quais são os componentes essenciais de uma função recursiva?

Uma função recursiva precisa de um ou mais casos base (condições de parada) e um caso recursivo que reduz o problema em direção ao caso base.

Recursão é sempre mais lenta que iteração?

Nem sempre. Em muitos problemas, a recursão é tão eficiente quanto a iteração quando bem implementada, especialmente com técnicas como memoização. Porém, devido ao overhead de chamadas de função e ao uso da pilha, a iteração pode ser mais rápida em linguagens imperativas.

O que é estouro de pilha (stack overflow)?

O estouro de pilha ocorre quando a pilha de chamadas excede seu limite máximo, geralmente devido a recursão muito profunda ou recursão infinita. Isso causa o travamento do programa.

Como evitar recursão excessiva?

Pode-se usar iteração, memoização, aumentar o limite de recursão (se a linguagem permitir) ou otimizar com recursão de cauda quando suportado.