Recorrências

Uma relação de recorrência define um termo de uma sequência a partir dos anteriores. Em computação, ela é a forma natural de expressar o custo de um algoritmo recursivo — e resolvê-la é obter a complexidade em forma fechada.

Definição e exemplos

$$T(n) = 2T(n/2) + n, \qquad T(1) = 1$$

Lê-se: para resolver um problema de tamanho $n$, resolvem-se dois subproblemas de tamanho $n/2$ e gasta-se $n$ de trabalho para combinar. É exatamente o merge sort.

Outros exemplos:

Recorrência	Origem
$T(n) = T(n-1) + 1$	Busca linear
$T(n) = T(n/2) + 1$	Busca binária
$T(n) = 2T(n/2) + n$	Merge sort
$T(n) = T(n-1) + n$	Seleção / bubble sort
$T(n) = 2T(n-1) + 1$	Torre de Hanói
$F(n) = F(n-1) + F(n-2)$	Fibonacci

Método da substituição

Chute a forma da solução e prove por indução.

Para $T(n) = 2T(n/2) + n$, chute $T(n) \le c,n \log_2 n$:

$$T(n) \le 2\left(c \frac{n}{2}\log_2 \frac{n}{2}\right) + n = c,n(\log_2 n - 1) + n = c,n\log_2 n - c,n + n$$

O resultado é $\le c,n\log_2 n$ desde que $c \ge 1$. A indução fecha, logo $T(n) = O(n \log n)$.

O método é rigoroso, mas exige adivinhar a resposta antes. Serve bem para confirmar um palpite obtido por outro método.

Árvore de recursão

Desenhe os níveis e some o trabalho de cada um. Para $T(n) = 2T(n/2) + n$:

Nível	Subproblemas	Tamanho	Trabalho no nível
$0$	$1$	$n$	$n$
$1$	$2$	$n/2$	$n$
$2$	$4$	$n/4$	$n$
$\vdots$
$\log_2 n$	$n$	$1$	$n$

Cada nível custa $n$ e há $\log_2 n + 1$ níveis, logo $T(n) = \Theta(n \log n)$.

A árvore de recursão é o método mais útil na prática porque mostra onde o custo está. Três padrões aparecem: custo igual em todos os níveis (o total é o custo do nível vezes a altura), custo dominado pela raiz (progressão geométrica decrescente) ou dominado pelas folhas (geométrica crescente).

Teorema mestre

Para recorrências da forma

$$T(n) = a,T(n/b) + f(n), \qquad a \ge 1,; b > 1$$

compare $f(n)$ com $n^{\log_b a}$:

Caso	Condição	Resultado
1	$f(n) = O(n^{\log_b a - \varepsilon})$	$T(n) = \Theta(n^{\log_b a})$
2	$f(n) = \Theta(n^{\log_b a})$	$T(n) = \Theta(n^{\log_b a} \log n)$
3	$f(n) = \Omega(n^{\log_b a + \varepsilon})$ e regularidade	$T(n) = \Theta(f(n))$

A intuição: $n^{\log_b a}$ é o custo das folhas. O caso 1 é quando as folhas dominam, o 3 é quando a raiz domina, o 2 é o equilíbrio.

Aplicações diretas:

• Merge sort: $a=2, b=2, f(n)=n$. Como $n^{\log_2 2} = n$, caso 2 → $\Theta(n \log n)$.
• Busca binária: $a=1, b=2, f(n)=1$. Como $n^{\log_2 1} = n^0 = 1$, caso 2 → $\Theta(\log n)$.
• Multiplicação de Strassen: $a=7, b=2, f(n)=n^2$. Como $n^{\log_2 7} \approx n^{2{,}81}$ domina $n^2$, caso 1 → $\Theta(n^{\log_2 7})$.

O teorema não cobre todos os casos. Ele falha quando $f(n)$ fica entre dois casos — por exemplo $T(n) = 2T(n/2) + n \log n$, que exige árvore de recursão e dá $\Theta(n \log^2 n)$.

Recorrências lineares homogêneas

Para $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, monte a equação característica $x^2 = c_1 x + c_2$. Se as raízes $r_1 \ne r_2$ são distintas, a solução geral é

$$a_n = \alpha r_1^n + \beta r_2^n$$

com $\alpha, \beta$ determinados pelas condições iniciais.

Para Fibonacci, $x^2 = x + 1$ tem raízes $\varphi = \frac{1+\sqrt5}{2}$ e $\psi = \frac{1-\sqrt5}{2}$, e sai a fórmula de Binet:

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt5}$$

Como $|\psi| < 1$, o segundo termo desaparece rapidamente e $F_n \approx \varphi^n/\sqrt5$. O crescimento exponencial explica por que a implementação recursiva ingênua de Fibonacci é inviável: ela faz $\Theta(\varphi^n)$ chamadas.

# ingênua: T(n) = T(n-1) + T(n-2) + 1  →  exponencial
def fib_lenta(n):
    return n if n < 2 else fib_lenta(n-1) + fib_lenta(n-2)

# programação dinâmica: T(n) = Θ(n)
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

A diferença entre as duas é exatamente a diferença entre resolver a recorrência do custo e não resolvê-la.

Exemplo trabalhado: Torre de Hanói

$T(n) = 2T(n-1) + 1$ com $T(1) = 1$. Expandindo:

$$T(n) = 2T(n-1)+1 = 4T(n-2)+2+1 = 8T(n-3)+4+2+1 = \cdots$$

$$T(n) = 2^{n-1}T(1) + \sum_{i=0}^{n-2} 2^i = 2^{n-1} + 2^{n-1} - 1 = 2^n - 1$$

Confirmando por indução: base $T(1) = 2^1 - 1 = 1$; passo $T(k+1) = 2(2^k - 1) + 1 = 2^{k+1} - 1$. $\blacksquare$

Erros comuns

• Aplicar o teorema mestre fora das hipóteses, especialmente com $a$ ou $b$ variáveis ou $f$ não polinomial.
• Ignorar o caso base ao resolver por expansão; ele determina a constante.
• Confundir $T(n/2)$ com $T(n-1)$. O primeiro dá altura logarítmica; o segundo, linear.
• Esquecer a condição de regularidade no caso 3 do teorema mestre.
• Escrever a recorrência errada. Antes de resolver, confirme quantas chamadas recursivas há e qual o custo fora delas.

Leituras recomendadas

• Cormen et al., capítulo 4 — tratamento completo de recorrências, incluindo a prova do teorema mestre e o método de substituição.
• Graham, Knuth e Patashnik, capítulos 1 e 7 — recorrências e funções geradoras, a ferramenta que resolve os casos que os métodos elementares não alcançam.
• Knuth, TAOCP volume 1, seção 1.2 — análise matemática de recorrências com muito rigor.

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058. Ronald L. Graham and Donald E. Knuth and Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 9780134389967. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley. Página oficial.

Referências

1. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.
2. Ronald L. Graham; Donald E. Knuth; Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley.
3. Donald E. Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.