Recursão e Recorrências¶

A recursão resolve um problema usando soluções para instâncias menores do mesmo problema. Um design recursivo válido precisa de casos base e progresso em direção a eles.

A pilha de chamadas¶

static long factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must be non-negative");
    }
    return n < 2 ? 1L : Math.multiplyExact(n, factorial(n - 1));
}

A definição matemática é clara, mas Java não garante eliminação de chamada em cauda. O método usa Θ(n) quadros de pilha e transborda long para n relativamente pequeno; correção matemática não remove limites de máquina.

Recorrências¶

Uma recorrência relaciona o custo para tamanho n a custos menores.

Recorrência	Resultado típico	Exemplo
`T(n) = T(n - 1) + Θ(1)`	`Θ(n)`	Recursão linear
`T(n) = T(n/2) + Θ(1)`	`Θ(log n)`	Busca binária
`T(n) = 2T(n/2) + Θ(n)`	`Θ(n log n)`	Merge sort
`T(n) = T(n - 1) + Θ(n)`	`Θ(n²)`	Particionamento mal balanceado

Intuição de árvore de recursão¶

Para merge sort, cada nível realiza Θ(n) total de trabalho de fusão. Existem Θ(log n) níveis, portanto o total é Θ(n log n).

O Teorema Mestre aplica-se a recorrências da forma T(n) = aT(n/b) + f(n) sob suas condições declaradas de regularidade. Não lida diretamente com T(n - 1) ou tamanhos de subproblemas desiguais arbitrários.

Memoização¶

Recursão fibonacciana ingênua repete subproblemas e leva tempo exponencial. Memoização armazena resultados, reduzindo o trabalho a Θ(n) tempo e Θ(n) espaço. A programação dinâmica bottom-up pode remover a recursão preservando a mesma estrutura de dependência. O guia dedicado de memoização explica a correção das chaves, o ciclo de vida, a concorrência e a distinção em relação a um cache de aplicação.

Exercícios¶

Desenhar a árvore de recursão para T(n) = 3T(n/2) + Θ(n).
Converter factorial recursivo a método iterativo.
Identificar caso base e medida de progresso em busca binária recursiva.