Recursão explicada de vez: como funciona e quando usar em programação

Recursão é um dos conceitos que mais confunde iniciantes em programação — e um dos mais elegantes quando bem compreendido. Uma função recursiva é uma função que chama a si mesma para resolver uma versão menor do mesmo problema. O poder da recursão está em expressar soluções naturalmente para problemas que têm estrutura recursiva (onde a solução do todo depende da solução de partes menores do mesmo tipo). Árvores, grafos, divisão e conquista, backtracking — todos esses temas fundamentais da ciência da computação usam recursão extensivamente.

Anatomia de uma função recursiva

Toda função recursiva correta tem dois componentes obrigatórios:

1. Caso base: a condição de parada — o caso trivial que pode ser resolvido sem chamada recursiva. Sem caso base, a recursão não para e causa “stack overflow”.
2. Caso recursivo: a chamada à própria função com um problema menor (mais próximo do caso base).

def fatorial(n):
    # Caso base: fatorial de 0 ou 1 é 1
    if n <= 1:
        return 1
    # Caso recursivo: n! = n * (n-1)!
    return n * fatorial(n - 1)

print(fatorial(5))  # 5 * 4 * 3 * 2 * 1 = 120

Visualizando as chamadas: fatorial(5) → 5 * fatorial(4) → 5 * 4 * fatorial(3) → 5 * 4 * 3 * fatorial(2) → 5 * 4 * 3 * 2 * fatorial(1) → 5 * 4 * 3 * 2 * 1 = 120.

Fibonacci: recursão ingênua vs dinâmica

# Versão ingênua — O(2^n): MUITO lenta para n > 40
def fibonacci_lento(n):
    if n <= 1:
        return n
    return fibonacci_lento(n - 1) + fibonacci_lento(n - 2)

# Versão com memoização — O(n): usa cache dos resultados já calculados
from functools import lru_cache

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

print(fibonacci(50))   # Instantâneo
print(fibonacci(100))  # Ainda instantâneo

A versão ingênua do Fibonacci recalcula os mesmos valores inúmeras vezes — fibonacci(5) chama fibonacci(3) duas vezes, fibonacci(2) três vezes. Com memoização (cache de resultados já calculados), cada valor é calculado apenas uma vez.

Percorrendo uma árvore de diretórios com recursão

Problemas com estrutura hierárquica se resolvem naturalmente com recursão:

import os

def listar_arquivos(caminho, nivel=0):
    indent = "  " * nivel
    print(f"{indent}{os.path.basename(caminho)}/")

    if os.path.isdir(caminho):
        for item in os.listdir(caminho):
            caminho_item = os.path.join(caminho, item)
            if os.path.isdir(caminho_item):
                listar_arquivos(caminho_item, nivel + 1)  # Recursão para subpastas
            else:
                print(f"{indent}  {item}")

listar_arquivos("./meu_projeto")

Quando usar (e quando não usar) recursão

Use recursão quando: o problema tem estrutura naturalmente recursiva (árvores, grafos, divisão e conquista), a solução recursiva é significativamente mais clara que a iterativa, e a profundidade de recursão é limitada e conhecida. Evite recursão quando: a profundidade pode ser muito grande (risco de stack overflow — o limite padrão do Python é 1000 chamadas), performance é crítica (chamadas de função têm overhead maior que loops), ou uma solução iterativa é igualmente clara. Para Fibonacci, um simples loop iterativo é mais eficiente que qualquer versão recursiva. A regra prática: use recursão quando ela torna o código mais claro e correto; use iteração quando performance ou profundidade ilimitada são requisitos.