Nesta aula, vamos mergulhar no conceito de recursão, uma das técnicas mais elegantes e poderosas da programação. A recursão permite que uma função chame a si mesma para resolver um problema, decompondo‑o em versões menores do mesmo problema. Ao final, você será capaz de identificar problemas recursivos, implementar funções recursivas e evitar as armadilhas comuns.

O que é recursão?

Recursão é um método onde a solução de um problema depende da solução de instâncias menores do mesmo problema. Formalmente, uma função é dita recursiva se, durante sua execução, ela faz uma chamada a si mesma. Esse conceito aparece tanto na matemática (definições recursivas de sequências, fractais) quanto na computação (algoritmos de busca, ordenação, processamento de árvores).

Um exemplo cotidiano: abrir uma caixa que pode conter outra caixa, e assim sucessivamente, até encontrar um objeto. O processo de abrir cada caixa é semelhante ao passo recursivo, e a condição de parada é encontrar o objeto desejado (caso base).

Componentes de uma função recursiva

Toda função recursiva deve conter dois elementos essenciais:

  • Caso base: condição que interrompe a recursão. Sem ele, a função ficaria se chamando infinitamente, resultando em um estouro de pilha.
  • Passo recursivo: momento em que a função chama a si mesma com parâmetros modificados, de modo que a cada chamada o problema se aproxime do caso base.

Por exemplo, no cálculo do fatorial, o caso base é n == 0 e o passo recursivo é n * fatorial(n-1).

Exemplos práticos

Fatorial

O fatorial de um número natural n (n!) é definido como o produto de todos os inteiros de 1 a n. A definição recursiva é:

def fatorial(n):
    if n == 0:          # caso base
        return 1
    return n * fatorial(n - 1)  # passo recursivo

Sequência de Fibonacci

Na sequência de Fibonacci, cada termo (a partir do terceiro) é a soma dos dois anteriores. A implementação recursiva direta reflete exatamente essa definição:

def fibonacci(n):
    if n <= 1:          # casos base: fib(0)=0, fib(1)=1
        return n
    return fibonacci(n-1) + fibonacci(n-2)>

Busca binária recursiva

A busca binária em um array ordenado reduz o espaço de busca pela metade a cada iteração. Sua versão recursiva é bastante elegante:

def busca_binaria(arr, alvo, esquerda, direita):
    if esquerda > direita:          # elemento não encontrado
        return -1
    meio = (esquerda + direita) // 2
    if arr[meio] == alvo:
        return meio
    elif arr[meio] < alvo:
        return busca_binaria(arr, alvo, meio+1, direita)
    else:
        return busca_binaria(arr, alvo, esquerda, meio-1)>

Torre de Hanói

O clássico problema da Torre de Hanói ilustra perfeitamente o poder da recursão. Para mover n discos de uma haste para outra usando uma haste auxiliar, 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)

Como a pilha de chamadas funciona?

Quando um programa executa uma função recursiva, cada chamada empilha um stack frame (quadro) na pilha de chamadas (call stack). Esse quadro contém as variáveis locais, o endereço de retorno e outros dados daquela chamada. Quando o caso base é atingido, as chamadas começam a retornar, desempilhando os quadros.

Se a recursão for muito profunda (por exemplo, tentar calcular fatorial(10000) sem otimização), a pilha pode estourar, gerando o famoso erro stack overflow. Cada linguagem tem um limite para o tamanho da pilha; em Python, por exemplo, existe um limite de 1000 quadros por padrão (ajustável via sys.setrecursionlimit).

Recursão vs Iteração

Tanto recursão quanto iteração são capazes de expressar computações repetitivas. A iteração utiliza laços (for, while) e não consome pilha de chamadas, sendo geralmente mais eficiente em termos de memória e velocidade. A recursão, por sua vez, oferece um código mais próximo da definição matemática do problema, sendo mais legível quando o problema tem estrutura recursiva natural (árvores, grafos, backtracking).

Na prática, a escolha depende do contexto: se a profundidade esperada for pequena e a legibilidade for prioridade, recursão é uma ótima pedida; se o desempenho for crítico ou a profundidade puder ser grande, a versão iterativa pode ser mais adequada.

Recursão de cauda (tail recursion)

Dizemos que uma função recursiva é de cauda (tail recursive) quando a chamada recursiva é a última operação realizada pela função, ou seja, não há nenhuma computação pendente após o retorno da chamada. Por exemplo, a versão a seguir do fatorial é de cauda:

def fatorial_tail(n, acumulador=1):
    if n == 0:
        return acumulador
    return fatorial_tail(n-1, n * acumulador)

Em linguagens que implementam Tail Call Optimization (TCO) (como Scheme, Lua e algumas implementações de JavaScript), a recursão de cauda é executada sem crescimento da pilha, essencialmente transformando‑a em iteração. Infelizmente, Python e muitas outras linguagens comuns não realizam essa otimização, então o acúmulo de pilha ainda ocorre.

Pontos‑chave sobre recursão

  • Recursão é uma técnica onde uma função chama a si mesma.
  • Toda função recursiva precisa de um ou mais casos base para terminar.
  • O passo recursivo deve modificar os argumentos, aproximando‑se do caso base a cada chamada.
  • A pilha de chamadas pode estourar se a profundidade da recursão for muito grande.
  • Recursão de cauda permite otimização em linguagens que suportam TCO, evitando o crescimento da pilha.
  • Muitos problemas (caminhos em labirintos, permutações, ordenação por mergesort/quicksort, travessia de árvores) são mais facilmente resolvidos com recursão.
  • É possível converter qualquer função recursiva em iterativa (usando uma pilha explícita, se necessário), mas o código pode se tornar mais complexo.

Perguntas frequentes

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

Iteração repete um bloco de código usando laços (for, while). Recursão resolve um problema chamando a si mesma. A iteração costuma ser mais eficiente em memória, enquanto a recursão pode ser mais expressiva e mais curta, especialmente para problemas com estrutura recursiva natural.

Quando devo usar recursão?

Use recursão quando o problema puder ser decomposto em subproblemas menores e semelhantes ao original, e a solução recursiva for mais clara que a iterativa. Exemplos típicos incluem: percorrer árvores (diretórios, DOM, estruturas sintáticas), algoritmos de ordenação (mergesort, quicksort), problemas de backtracking (N‑rainhas, labirintos) e cálculos matemáticos definidos recursivamente (fatorial, Fibonacci, MDC, torre de Hanói).

O que é stack overflow (estouro de pilha) em recursão?

O estouro de pilha ocorre quando a profundidade da recursão excede o limite da pilha de chamadas. Cada chamada recursiva consome um quadro na pilha; se o número de chamadas for muito alto, a memória reservada para a pilha se esgota e o programa lança um erro. Os limites variam conforme a linguagem e configuração do ambiente.

Como evitar o estouro de pilha em funções recursivas?

Você pode: (1) aumentar o limite da pilha se a linguagem permitir (ex.: sys.setrecursionlimit em Python); (2) reescrever a função usando recursão de cauda (se a linguagem oferecer TCO); (3) converter a função recursiva para uma versão iterativa; (4) usar uma abordagem com pilha explícita controlada manualmente. A melhor estratégia depende do cenário e da linguagem utilizada.

Posso sempre substituir recursão por iteração?

Sim, toda função recursiva pode ser transformada em uma função iterativa, embora em alguns casos seja necessário manter uma pilha explícita para simular o comportamento recursivo. A versão iterativa tende a ser mais eficiente, mas pode ser mais longa e difícil de entender.

Confira outros artigos do blog: Posts e Tags para explorar mais conteúdos sobre computação.