Recursão em Python: caso base, exemplos e erros

Um algoritmo recursivo é aquele que resolve um problema chamando a si mesmo com uma versão menor do mesmo problema, até chegar a um caso tão simples que a resposta é imediata. Esse caso simples é o caso base; a chamada a si mesmo é o passo recursivo. Sem caso base, a função nunca termina.

Recursão aparece em cálculos matemáticos, percorrimento de pastas, árvores de dados, algoritmos de ordenação e muitos problemas de busca. Abaixo você vê como funciona, exemplos em Python, a diferença para soluções iterativas e os erros mais comuns.

Os dois elementos de todo algoritmo recursivo

Caso base: a condição de parada, em que a função devolve um resultado sem se chamar de novo.
Passo recursivo: a função se chama com uma entrada menor, que se aproxima do caso base.

Se a entrada não diminui a cada chamada, a recursão nunca alcança o caso base. É por isso que a pergunta central ao escrever uma função recursiva é: “em que sentido este problema está ficando menor?”.

Exemplo clássico: fatorial

O fatorial de n (n!) é o produto de todos os inteiros de 1 até n. Ele tem uma definição naturalmente recursiva: n! = n × (n − 1)!, com 0! = 1.

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

print(fatorial(5))  # 120

O que acontece na memória

Cada chamada fica empilhada na pilha de execução (call stack) até o caso base ser atingido. Depois, os resultados “voltam” multiplicando: fatorial(1) devolve 1, fatorial(2) devolve 2, fatorial(3) devolve 6, e assim por diante até 120.

Recursão em estruturas de dados

Onde a recursão realmente brilha é em estruturas que contêm versões menores de si mesmas, como árvores e pastas. Uma pasta pode ter arquivos e outras pastas, que por sua vez têm arquivos e pastas.

import os

def contar_arquivos(caminho):
    total = 0
    for item in os.listdir(caminho):
        completo = os.path.join(caminho, item)
        if os.path.isdir(completo):
            total += contar_arquivos(completo)
        else:
            total += 1
    return total

Aqui o caso base está implícito: uma pasta sem subpastas termina o laço sem novas chamadas.

Estruturas em árvore também aparecem em redes distribuídas; se quiser ver um exemplo fora da sala de aula, o texto sobre o que é um nó de blockchain mostra como dados são organizados e verificados em rede.

Recursão versus iteração

Todo algoritmo recursivo pode ser reescrito com laços (for, while) e, às vezes, uma pilha explícita. A escolha depende de clareza e desempenho.

def fatorial_iterativo(n):
    resultado = 1
    for i in range(2, n + 1):
        resultado *= i
    return resultado

Aspecto	Recursivo	Iterativo
Legibilidade	Natural para árvores e divisão de problemas	Natural para repetições simples
Uso de memória	Cresce com a profundidade da pilha	Geralmente constante
Risco	Estouro de pilha em entradas grandes	Laço infinito se a condição falhar
Exemplos típicos	Árvores, merge sort, quicksort, backtracking	Somas, contagens, varreduras de listas

Armadilhas comuns e como evitar

Esquecer o caso base

Gera chamadas infinitas até estourar a pilha. Em Python, o erro é RecursionError: maximum recursion depth exceeded.

Recalcular a mesma coisa várias vezes

A versão ingênua de Fibonacci recalcula valores repetidamente e fica exponencialmente lenta. A solução é memorização (guardar resultados já calculados):

from functools import lru_cache

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

print(fib(50))  # 12586269025

Profundidade grande demais

Linguagens como Python limitam a profundidade da pilha. Para entradas muito grandes, uma versão iterativa costuma ser mais segura.

Onde a recursão é usada na prática

Divisão e conquista: merge sort, quicksort e busca binária dividem o problema ao meio.
Árvores: DOM de páginas web, árvores de decisão, sistemas de arquivos.
Backtracking: sudoku, labirintos e combinações.
Grafos: busca em profundidade (DFS).
Parsers: análise de expressões e linguagens.

Muitos desses algoritmos são peças de sistemas maiores, inclusive em modelos de aprendizado de máquina, como as árvores de decisão; veja o panorama em o que é inteligência artificial.

Pensando de forma recursiva: um método

Escrever recursão fica mais fácil quando você segue sempre as mesmas perguntas:

Qual é a menor entrada possível e qual a resposta dela? Esse é o caso base.
Se eu já tivesse a resposta para uma entrada um pouco menor, como usaria isso para resolver a atual?
A entrada da chamada recursiva realmente diminui em direção ao caso base?
Existem cálculos repetidos que valem ser guardados?

Veja o método aplicado à soma dos elementos de uma lista. A menor lista é a vazia, cuja soma é zero. Para uma lista maior, a soma é o primeiro elemento mais a soma do resto:

def soma(lista):
    if not lista:
        return 0
    return lista[0] + soma(lista[1:])

print(soma([3, 5, 2]))  # 10

Outro exemplo clássico é a busca binária, que divide uma lista ordenada ao meio a cada passo:

def busca(lista, alvo, ini, fim):
    if ini > fim:
        return -1
    meio = (ini + fim) // 2
    if lista[meio] == alvo:
        return meio
    if lista[meio] < alvo:
        return busca(lista, alvo, meio + 1, fim)
    return busca(lista, alvo, ini, meio - 1)

Com a prática, esse raciocínio passa a ser automático.

Uma boa forma de treinar é pegar problemas pequenos que você já resolveu com laços, como inverter uma string, contar dígitos de um número ou calcular a potência de um número, e reescrevê-los de forma recursiva. Depois, compare as duas versões: legibilidade, uso de memória e comportamento com entradas grandes. Esse exercício mostra na prática quando a recursão ajuda e quando atrapalha.

Perguntas frequentes

Recursão é mais lenta que laço?

Muitas vezes um pouco, por causa do custo de cada chamada de função. Na maioria dos casos a diferença é pequena, e a clareza do código pesa mais.

Toda recursão pode virar iteração?

Sim. Algumas conversões são simples; outras exigem uma pilha explícita para imitar o comportamento da pilha de chamadas.

O que é recursão de cauda?

É quando a chamada recursiva é a última operação da função. Algumas linguagens otimizam esse caso para não crescer a pilha; Python não faz essa otimização.

Como depurar uma função recursiva?

Teste primeiro o caso base, depois entradas pequenas, e imprima os argumentos de cada chamada para ver a sequência.

Recursão cai em entrevistas de programação?

Com frequência, especialmente em problemas de árvores, combinações e divisão e conquista.

Qual linguagem é melhor para aprender recursão?

Qualquer linguagem com funções serve. Python é uma boa escolha pela sintaxe simples, e linguagens funcionais, como Haskell, usam recursão como forma principal de repetição.

O que levar dessa leitura

Um algoritmo recursivo resolve um problema reduzindo-o a versões menores de si mesmo até um caso base. Defina bem a condição de parada, garanta que a entrada diminua, use memorização quando houver repetição e prefira iteração quando a profundidade puder ser muito grande.