Recursão e divisão e conquista

Bonecas russas e espelhos opostos

Recursão é como abrir uma Matryoshka (boneca russa): dentro de cada boneca há uma boneca menor, até chegar à menor de todas. Para abrir a grande, você abre a do meio, que abre a próxima, e assim por diante. O caso base é a menor boneca — a que não tem mais nada dentro.

A estratégia de dividir e conquistar vai além: divide o problema em partes independentes, resolve cada parte recursivamente, e depois combina os resultados. Merge sort divide a lista ao meio, ordena cada metade recursivamente, e combina — resultando em O(n log n), muito melhor que O(n²).

A árvore de recursão do fib(4)

Avance passo a passo e veja como as chamadas se empilham e os resultados se propagam de volta. Note quantas vezes fib(2) e fib(1) são recalculados.

Caso base, passo recursivo e memoização

# Toda recursão precisa de dois elementos:
# 1. Caso base: condição de parada (sem ela → stack overflow)
# 2. Passo recursivo: chama a si mesmo com entrada MENOR

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

# fatorial(4):
# → 4 * fatorial(3)
# → 4 * (3 * fatorial(2))
# → 4 * (3 * (2 * fatorial(1)))
# → 4 * (3 * (2 * 1)) = 24

def fibonacci(n):
    if n <= 1: return n             # casos base: fib(0)=0, fib(1)=1
    return fibonacci(n-1) + fibonacci(n-2)  # O(2ⁿ) — muito lento!

# Fibonacci com memoização — O(n)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)  # agora O(n) — cada subproblema calculado 1×

Dividir e conquistar: Merge Sort

# Merge sort: divide e conquista clássico
# T(n) = 2 T(n/2) + O(n)  →  O(n log n)

def merge_sort(lista):
    if len(lista) <= 1:       # caso base: lista de 0 ou 1 elemento
        return lista

    meio = len(lista) // 2
    esq  = merge_sort(lista[:meio])    # divide
    dir_ = merge_sort(lista[meio:])    # divide
    return merge(esq, dir_)            # conquista (combina)

def merge(a, b):                       # O(n) — combina dois arrays ordenados
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: result.append(a[i]); i += 1
        else:            result.append(b[j]); j += 1
    return result + a[i:] + b[j:]

# Outros exemplos de dividir e conquistar:
# - Quicksort: pivô separa, ordena cada metade recursivamente
# - Binary search: divide ao meio a cada chamada
# - Algoritmo de Karatsuba: multiplicação de grandes números O(n^1.58)

Da recursão ingênua à eficiente

Mini projeto: implemente fibonacci recursivo ingênuo e meça o tempo para n=30, 35, 40. Adicione @lru_cache e meça de novo. Plote o número de chamadas de função (adicione um contador global) com e sem memoização. Calcule o ratio para ver a diferença exponencial.

Projeto principal: implemente o algoritmo de Karatsuba para multiplicar dois números grandes (como strings de dígitos). Ele multiplica n×n dígitos em O(n^1.585) em vez de O(n²). Compare com a multiplicação ingênua para números de 100, 500 e 1000 dígitos. Python usa Karatsuba internamente para inteiros grandes — você está re-implementando algo que a linguagem já faz!

Desafio extra: implemente o problema das Torres de Hanói recursivamente. Para n discos, prove que são necessários exatamente 2ⁿ-1 movimentos. Implemente também a versão iterativa usando uma pilha explícita para simular a pilha de chamadas — isso mostra que toda recursão pode ser convertida em iteração com uma pilha.

Teste sua intuição

Onde você encontra isso