A recursão é um dos conceitos mais centrais da ciência da computação e aparece em praticamente todas as áreas: algoritmos, estruturas de dados, inteligência artificial, análise combinatória e até mesmo na definição de linguagens formais. A ideia é simples: um problema é resolvido dividindo‑o em subproblemas menores da mesma natureza, até que se atinja um caso trivial que pode ser resolvido diretamente. Neste artigo, vamos estudar os fundamentos da recursão, explorar exemplos clássicos, compará‑la com a iteração e discutir cuidados importantes para escrever funções recursivas eficientes e seguras.

O que é recursão?

Uma função é dita recursiva quando ela chama a si mesma durante sua execução. Para que a recursão termine, é obrigatório existir pelo menos um caso base – uma condição que interrompe as chamadas – e um passo recursivo, onde a função é chamada novamente com argumentos modificados, tipicamente menores. A cada chamada, um novo registro (stack frame) é criado na pilha de chamadas (call stack) para armazenar variáveis locais e o ponto de retorno. Quando o caso base é atingido, as chamadas começam a retornar, desempilhando os frames.

Um exemplo didático é a contagem regressiva:

def contagem(n):
    if n == 0:
        print("Fogo!")
    else:
        print(n)
        contagem(n-1)

A função contagem imprime os números de n até 1 e depois "Fogo!". O caso base é n == 0; o passo recursivo é a chamada com n‑1. Cada chamada empilha um frame na memória; se n for muito grande, a pilha pode estourar (stack overflow).

Outro exemplo fundamental é o cálculo do fatorial, já clássico:

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

Aqui, o caso base é n <= 1 e o passo recursivo multiplica n pelo fatorial de n‑1.

Exemplos clássicos de recursão

Sequência de Fibonacci

A sequência de Fibonacci é definida como: F(0) = 0, F(1) = 1 e F(n) = F(n‑1) + F(n‑2) para n ≥ 2. A implementação recursiva direta é:

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

Embora elegante, essa versão tem complexidade exponencial O(2n) porque recalcula os mesmos valores muitas vezes. Para n = 40, o número de chamadas já é enorme. Por isso, o Fibonacci ingênuo é um alerta: recursão sem otimização pode ser inviável.

Torre de Hanói

O problema da Torre de Hanói consiste em mover uma pilha de discos de um pino para outro, usando um pino auxiliar, com a restrição de que um disco maior nunca pode ficar sobre um menor. A solução recursiva é intuitiva:

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 necessários é 2n‑1, e a recursão fornece uma descrição clara do processo.

Percurso em árvores binárias

Árvores binárias são estruturas naturalmente recursivas. Os percursos em pré‑ordem, em‑ordem e pós‑ordem são facilmente implementados com recursão:

def preorder(no):
    if no:
        print(no.valor)
        preorder(no.esquerda)
        preorder(no.direita)

Sem recursão, seria necessário usar uma pilha explícita, tornando o código mais complexo.

Busca binária

O algoritmo de busca binária também pode ser escrito recursivamente:

def busca_binaria(lista, alvo, esquerda, direita):
    if esquerda > direita:
        return -1
    meio = (esquerda + direita) // 2
    if lista[meio] == alvo:
        return meio
    if lista[meio] < alvo:
        return busca_binaria(lista, alvo, meio+1, direita)
    else:
        return busca_binaria(lista, alvo, esquerda, meio-1)

Embora a versão iterativa seja mais comum, a recursão deixa explícita a divisão do problema ao meio.

Recursão vs Iteração

Tanto recursão quanto iteração são capazes de resolver os mesmos problemas, mas cada abordagem tem vantagens e desvantagens.

  • Eficiência de memória: a recursão consome memória adicional com cada chamada (pilha). A iteração usa apenas variáveis locais, sendo mais econômica.
  • Clareza: para problemas inerentemente recursivos (árvores, expressões matemáticas, algoritmos de divisão e conquista), a recursão produz código mais curto e próximo da definição matemática.
  • Desempenho: a recursão ingênua (ex.: Fibonacci) pode ser exponencial, enquanto a iteração resolve em tempo linear. No entanto, com técnicas como memoização ou recursão de cauda otimizada, a recursão pode se equiparar à iteração.
  • Limite prático: a profundidade da recursão é limitada pelo tamanho da pilha (tipicamente ~1000 frames em Python). Já um laço pode rodar bilhões de iterações sem problemas.

Em geral, quando a solução iterativa é simples (laço for/while), prefira iteração. Quando o problema é naturalmente recursivo e a profundidade esperada é pequena, a recursão é uma excelente escolha.

Cuidados com recursão

Estouro de pilha (stack overflow)

Cada chamada recursiva consome espaço na pilha. Se a profundidade da recursão exceder o limite (em Python, o padrão é 1000), ocorre RecursionError. É possível aumentar o limite com sys.setrecursionlimit(), mas isso não evita o consumo de memória e pode levar a um crash. A melhor solução é reescrever a função de forma iterativa ou usar recursão de cauda (quando a linguagem otimiza).

Complexidade exponencial e memoização

O exemplo ingênuo de Fibonacci recalcula os mesmos valores repetidas vezes. Uma técnica clássica de otimização é a memoização: armazenar resultados já calculados em um cache. Em Python, pode‑se usar o decorador functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Com memoização, a complexidade passa a ser O(n) – cada valor é calculado apenas uma vez. Equivalentemente, pode‑se implementar uma versão iterativa.

Recursão de cauda (tail recursion)

Diz‑se que uma recursão é de cauda quando a chamada recursiva é a última operação da função, e seu resultado é retornado diretamente. Alguns compiladores (como os de linguagens funcionais) otimizam a recursão de cauda transformando‑a em iteração, reutilizando o mesmo frame da pilha. Infelizmente, Python não otimiza recursão de cauda, mas é importante conhecer o conceito para outras linguagens.

# Exemplo de função de cauda (em Python, não otimizada)
def fatorial_tail(n, acumulador=1):
    if n <= 1:
        return acumulador
    return fatorial_tail(n-1, n * acumulador)

Evitando efeitos colaterais

Funções recursivas devem, idealmente, ser puras – sem modificar variáveis globais ou causar efeitos colaterais. Isso facilita o raciocínio e a otimização.

Aplicações práticas da recursão

A recursão é a base de diversos algoritmos e estruturas:

  • Algoritmos de divisão e conquista: mergesort, quicksort, busca binária, multiplicação de Karatsuba.
  • Percursos em árvores e grafos: árvores binárias, BFS/DFS (usando recursão para DFS), triedos.
  • Backtracking: problemas como N‑Rainhas, labirintos, geração de permutações/combinações.
  • Expressões matemáticas: avaliação de expressões (árvore sintática), análise gramatical (descida recursiva).
  • Programação funcional: linguagens como Haskell, Scheme e Elixir usam recursão (muitas vezes com otimização de cauda) como principal mecanismo de controle de fluxo.

Dominar a recursão é essencial para qualquer pessoa que se aprofunde em ciência da computação.

Pontos principais

  • Sempre definir pelo menos um caso base.
  • Garantir que a cada chamada o problema se reduza (em direção ao caso base).
  • Analisar a complexidade de tempo e espaço; considerar memoização se houver recomputação.
  • Prever a profundidade máxima para evitar estouro de pilha.
  • Preferir iteração quando a profundidade for grande ou quando a linguagem não otimizar recursão de cauda.
  • Usar recursão quando o código ficar mais claro e a profundidade for gerenciável.

Perguntas frequentes

1. Qual a diferença entre recursão e iteração?

Recursão resolve um problema chamando a si mesma, enquanto iteração usa laços (for, while). Ambos podem ser equivalentes, mas recursão tende a ser mais intuitiva para problemas com estrutura hierárquica ou auto‑semelhante, enquanto iteração geralmente é mais eficiente em termos de memória e velocidade para problemas lineares.

2. O que é caso base?

É a condição que interrompe a recursão. Sem ele, a função se chamaria infinitamente, causando estouro de pilha. Todo bom projeto recursivo começa pela definição do(s) caso(s) base.

3. O que é recursão de cauda?

É um tipo especial de recursão onde a chamada recursiva é a última operação da função. Em linguagens que otimizam tail calls, a execução é convertida em iteração, evitando o crescimento da pilha. Python não faz essa otimização, mas o conceito ainda é útil para escrever código mais enxuto.

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

Nem sempre. Com otimizações como memoização ou recursão de cauda, a recursão pode ser tão rápida quanto a iteração. No entanto, a recursão ingênua pode ser drasticamente mais lenta (ex.: Fibonacci sem memoização). Para a maioria dos casos do dia a dia, a iteração leva vantagem em desempenho bruto, mas a recursão ganha em clareza.

5. Como evitar estouro de pilha em Python?

Primeiro, avalie se a profundidade da recursão pode ser grande. Se sim, reescreva a função iterativamente ou use uma pilha explícita. É possível aumentar o limite com sys.setrecursionlimit(), mas isso não elimina o consumo de memória e pode tornar o programa instável. A abordagem correta é escolher a ferramenta adequada: iteração para casos lineares, recursão apenas quando a profundidade for segura.