Recursão em Python

Recursão é uma técnica em que uma função chama a si mesma para resolver um problema, dividindo-o em subproblemas menores e idênticos. Cada chamada trabalha com uma versão mais simples do problema original até atingir um caso trivial — o caso base — que pode ser resolvido diretamente.

Este capítulo aborda:

• Como a recursão funciona e como é a pilha de chamadas
• Caso base e caso recursivo
• Problemas recursivos clássicos: fatorial, Fibonacci, potência, achatamento
• Recursão vs iteração — quando escolher cada uma
• O limite de recursão do Python e como contorná-lo
• Memoização com functools.lru_cache

Como a Recursão Funciona

Quando uma função chama a si mesma, o Python empilha um novo frame de pilha na pilha de chamadas a cada invocação. Cada frame mantém suas próprias variáveis locais. Quando o caso base é atingido, os frames começam a retornar em ordem inversa — o último a entrar é o primeiro a sair — até que a chamada original receba sua resposta final.

Uma função recursiva válida sempre tem duas partes:

Sem um caso base (ou com um que nunca é atingido), a função chama a si mesma indefinidamente e o Python lança um RecursionError.

Um Exemplo Simples: Contagem Regressiva

A função a seguir faz uma contagem regressiva de n até zero e então imprime "Go!". É fácil de acompanhar porque cada chamada reduz n em um até que n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Saída:

5
4
3
2
1
Go!

Rastreamento da pilha de chamadas:

1. countdown(5) imprime 5, chama countdown(4)
2. countdown(4) imprime 4, chama countdown(3)
3. … e assim por diante …
4. countdown(0) imprime "Go!" e retorna — o desenrolamento começa

Fatorial

O fatorial de n (escrito n!) é o produto de todos os inteiros positivos até n. É definido recursivamente como:

• 0! = 1 (caso base)
• n! = n × (n − 1)! (caso recursivo)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) se expande assim antes de qualquer valor ser retornado:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Em seguida, as multiplicações acontecem no caminho de volta: 1 → 2 → 6 → 24 → 120.

Sequência de Fibonacci

A sequência de Fibonacci é definida assim: cada número é a soma dos dois anteriores — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Isso é correto, mas lento para valores grandes de n — fibonacci(40) faz milhões de chamadas redundantes. Veja Memoização abaixo para a solução.

Soma de uma Lista

A recursão funciona naturalmente em listas: processe o primeiro elemento e depois recurse sobre o restante.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] cria uma nova lista sem o primeiro elemento, tornando o problema um item menor a cada vez.

Elevando um Número a uma Potência

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Achatamento de uma Lista Aninhada

Alguns problemas são inerentemente recursivos — possuem a mesma estrutura em todos os níveis. Achatar uma lista com aninhamento arbitrário é um deles.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

print(flatten([1, [2, 3], [4, [5, 6]], 7]))
# [1, 2, 3, 4, 5, 6, 7]

Isso é difícil de escrever de forma limpa apenas com iteração, pois a profundidade do aninhamento é desconhecida.

Recursão vs Iteração

A maioria dos algoritmos recursivos pode ser reescrita como laços iterativos, e vice-versa.

Fatorial iterativo

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

print(factorial_iterative(5))   # 120

Diretriz: escolha recursão quando o problema se decompõe naturalmente em subproblemas menores e idênticos e a profundidade é modesta. Escolha iteração quando precisar de alto desempenho ou quando a profundidade puder ser grande.

Limite de Recursão do Python

O Python limita a pilha de chamadas a 1 000 frames por padrão para evitar que um estouro de pilha derrube o processo.

import sys
print(sys.getrecursionlimit())   # 1000

Se sua função ultrapassar esse limite, você verá:

RecursionError: maximum recursion depth exceeded

Você pode aumentar o limite com sys.setrecursionlimit(n), mas faça isso com cautela — uma pilha muito profunda pode esgotar a memória do sistema. Para recursão genuinamente profunda, reescreva o algoritmo de forma iterativa ou use geradores Python para simular uma pilha manualmente.

Memoização

A recursão ingênua de Fibonacci é exponencialmente lenta porque resolve os mesmos subproblemas repetidamente. Memoização armazena em cache o resultado de cada chamada única para que seja computado apenas uma vez.

Cache manual com dicionário

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Usando functools.lru_cache

A biblioteca padrão fornece um decorator que cuida do cache automaticamente:

from functools import lru_cache

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

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache transforma um algoritmo que seria exponencial em tempo linear sem nenhum código extra dentro do corpo da função. É a abordagem idiomática em Python para memoizar funções recursivas puras.

Busca Binária (Recursiva)

A busca binária é um algoritmo clássico de divisão e conquista: compare o alvo com o elemento do meio e recurse na metade esquerda ou direita.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Armadilhas Comuns

Caso base ausente

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Sempre se pergunte: "Qual é a entrada mais simples que essa função deve tratar sem chamar a si mesma?"

Recursão infinita por caso base incorreto

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Argumento padrão mutável como memo

Usar memo={} como parâmetro padrão é conveniente, mas compartilha estado entre todas as chamadas de nível superior. Em código de produção, passe o cache explicitamente ou use @lru_cache.

Quando Usar Recursão

Recursão é uma solução natural para:

• Percurso em árvores e grafos — listagens de diretórios, percurso de DOM, árvores de decisão
• Algoritmos de divisão e conquista — merge sort, quicksort, busca binária
• Definições matemáticas — fatorial, Fibonacci, combinatória
• Backtracking — resolução de labirintos, Sudoku, geração de permutações
• Estruturas de dados aninhadas — análise de JSON/XML, achatamento de listas aninhadas

Para laços sequenciais simples ou grandes profundidades, prefira laços for ou laços while.

Capítulos Relacionados

• Funções Python — os blocos de construção sobre os quais a recursão é baseada
• Escopo em Python — entendendo como as variáveis locais funcionam em cada frame
• Laços While em Python — a alternativa iterativa
• Geradores Python — alternativas eficientes em memória para sequências
• Iteradores Python — o protocolo de iteração subjacente ao modelo de laços do Python
• Python Try Except — tratando RecursionError de forma elegante

Prática