Fibonacci

Categoria: Dynamic Programming

O problema

fib(n) = fib(n-1) + fib(n-2) é uma definição de uma linha — e, traduzida literalmente para código recursivo, é uma armadilha. Calcular fib(n-1) e fib(n-2) eventualmente exige fib(n-2), fib(n-3) e assim por diante, até o fim — e a recursão ingênua recalcula do zero cada um desses subproblemas compartilhados, toda vez que é necessário. O número de chamadas redundantes cresce exponencialmente com n.

A solução

Perceba que fib(k) só tem um valor possível para um dado k — resolva uma vez e reutilize essa resposta em todo lugar onde for necessária, em vez de recalculá-la. A memoização faz isso de cima para baixo: mantém um cache e, antes de recursar, verifica se esse n já foi resolvido. A tabulação faz a mesma coisa de baixo para cima: constrói fib(0), fib(1), fib(2), ..., fib(n) em um loop simples, de forma que nada é calculado antes que suas dependências existam. Ambas reduzem o custo de exponencial para O(n) — a memoização recusando-se a refazer trabalho, a tabulação nunca sendo solicitada a fazê-lo. A tabulação vai um passo além aqui: como cada fib(k) só precisa dos dois valores anteriores, não há necessidade de manter uma tabela (nem um mapa de memoização, nem uma pilha de recursão) — duas variáveis bastam.

flowchart TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3b -.->|"same subproblem as F3a - naive recursion solves it again"| F3a

Exemplo clássico

classic/Fibonacci implementa as três abordagens lado a lado, especificamente para que o benchmark abaixo possa medir a mesma afirmação de três formas diferentes na mesma máquina. Usa long e rejeita n > 90 para permanecer dentro do intervalo de long em vez de estourar silenciosamente. FibonacciTest cobre valores base conhecidos, que as versões memoizada e tabulada concordam com a ingênua em uma faixa de entradas, que ambas concordam entre si no limite de estouro n=90, e as proteções contra n negativo e contra o limite de estouro.

Exemplo aplicado: contagem de rotas de pagamento entre bancos correspondentes

applied/PaymentRouteCounter conta as rotas distintas de exatamente k saltos entre bancos correspondentes, de uma conta a outra através de uma rede de liquidação — a mesma forma de subproblemas sobrepostos dos números de Fibonacci deste módulo, aplicada a uma pergunta real em vez de uma abstrata. Sem memoização, contar rotas que passam por um nó por onde passam múltiplos caminhos parciais recalcula do zero, toda vez que é alcançado, a contagem completa de saltos restantes daquele nó — exponencial no orçamento de saltos, exatamente pela mesma razão que o fib(n) ingênuo é. Memoizar em (nó atual, saltos restantes) reduz isso a um trabalho proporcional a tamanho da rede × orçamento de saltos. PaymentRouteCounterTest cobre a contagem de múltiplas rotas para o mesmo destino, o limite de zero saltos (só conta quando origem é igual a destino), uma contagem de saltos inalcançável, a concordância entre as versões ingênua e memoizada na mesma rede, uma rede cíclica (provando que a memoização não entra em loop infinito em ciclos) e as proteções contra argumentos nulos/negativos.

Benchmark

./gradlew :dynamic-programming:fibonacci:jmh

Execução real nesta máquina (JMH 1.37, JDK 26.0.2, 2 iterações de warmup + 3 de medição, 1 fork). n permanece deliberadamente pequeno — a Fibonacci ingênua em n=35 já leva dezenas de milissegundos por chamada, e qualquer valor maior tornaria este benchmark impraticavelmente lento, o que é, em si, parte do ponto:

Em n=35, a versão ingênua é ~78,289x mais lenta que a memoizada e ~6,057,544x mais lenta que a tabulada — para exatamente a mesma resposta. O próprio crescimento da versão ingênua confirma diretamente a forma exponencial: ir de n=30 para n=35 (mais 5 passos) custa aproximadamente 10.7x mais tempo, batendo de perto com o próprio fator de crescimento por passo da razão áurea (φ ≈ 1.618, e 1.618^5 ≈ 11.1) — a própria taxa de crescimento de forma fechada de Fibonacci, aparecendo diretamente no tempo de execução do algoritmo ingênuo. Já as versões memoizada e tabulada mal se movem na mesma faixa — ambas lineares, com o crescimento quase nulo e imensurável da tabulada refletindo que ela nunca paga o custo de um HashMap ou de uma pilha de recursão.

Quando não usar

• Recursão ingênua especificamente: nunca, além de valores trivialmente pequenos de n — o benchmark acima é o argumento inteiro. Não há cenário em que recalcular o mesmo subproblema um número exponencial de vezes seja a escolha de engenharia correta, uma vez que memoização ou tabulação não custam nada extra para escrever.
• Precisa da sequência real de valores, não apenas de fib(n)? A tabulação já produz cada valor intermediário ao longo do caminho — mantenha o array completo em vez de reduzir a duas variáveis, se toda a sequência (não apenas o último termo) for necessária.
• Os subproblemas não se sobrepõem de fato para sua recorrência específica? Então a memoização não tem nada a economizar — é a sobreposição, não a recursão em si, que a recursão ingênua desperdiça.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :dynamic-programming:fibonacci:jacocoTestReport

Relatório em dynamic-programming/fibonacci/build/reports/jacoco/test/html/index.html.

Leitura complementar

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3ª/4ª ed., Capítulo 15, "Dynamic Programming" — o tratamento formal de subproblemas sobrepostos e subestrutura ótima que o benchmark deste módulo demonstra empiricamente.
• Skiena — The Algorithm Design Manual, seção sobre Programação Dinâmica — descreve a memoização como "recursão mais um cache", exatamente o modelo mental que o método memoized deste módulo implementa ao pé da letra.

Testes unitários

package com.algorithms.dynamicprogramming.fibonacci.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class FibonacciTest {

    @Test
    void naiveComputesKnownValues() {
        assertThat(Fibonacci.naive(0)).isZero();
        assertThat(Fibonacci.naive(1)).isEqualTo(1);
        assertThat(Fibonacci.naive(10)).isEqualTo(55);
    }

    @Test
    void memoizedMatchesNaiveForTheSameInputs() {
        for (int n = 0; n <= 20; n++) {
            assertThat(Fibonacci.memoized(n)).isEqualTo(Fibonacci.naive(n));
        }
    }

    @Test
    void tabulatedMatchesNaiveForTheSameInputs() {
        for (int n = 0; n <= 20; n++) {
            assertThat(Fibonacci.tabulated(n)).isEqualTo(Fibonacci.naive(n));
        }
    }

    @Test
    void allThreeAgreeAtTheOverflowBoundary() {
        assertThat(Fibonacci.tabulated(90)).isEqualTo(Fibonacci.memoized(90));
        assertThat(Fibonacci.tabulated(90)).isEqualTo(2880067194370816120L);
    }

    @Test
    void rejectsANegativeN() {
        assertThatThrownBy(() -> Fibonacci.naive(-1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.memoized(-1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.tabulated(-1)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsAnNThatWouldOverflowALong() {
        assertThatThrownBy(() -> Fibonacci.naive(91)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.memoized(91)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> Fibonacci.tabulated(91)).isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.dynamicprogramming.fibonacci.applied;

import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Map;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class PaymentRouteCounterTest {

    private static final Map<String, List<String>> NETWORK = Map.of(
            "A", List.of("B", "C"),
            "B", List.of("D"),
            "C", List.of("D"),
            "D", List.of()
    );

    @Test
    void countsBothTwoHopRoutesFromAToD() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "D", 2)).isEqualTo(2);
    }

    @Test
    void zeroHopsOnlyCountsWhenSourceEqualsDestination() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "A", 0)).isEqualTo(1);
        assertThat(counter.countRoutesMemoized("A", "D", 0)).isZero();
    }

    @Test
    void noRouteExistsForAnUnreachableHopCount() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesMemoized("A", "D", 5)).isZero();
    }

    @Test
    void naiveAndMemoizedAgreeOnTheSameNetwork() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesNaive("A", "D", 2))
                .isEqualTo(counter.countRoutesMemoized("A", "D", 2));
    }

    @Test
    void naiveCountsZeroWhenTheHopBudgetLandsOnTheWrongNode() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThat(counter.countRoutesNaive("A", "D", 1)).isZero();
    }

    @Test
    void handlesACycleInTheNetworkWithoutInfiniteRecursion() {
        Map<String, List<String>> cyclic = Map.of(
                "X", List.of("Y"),
                "Y", List.of("X")
        );
        PaymentRouteCounter counter = new PaymentRouteCounter(cyclic);

        assertThat(counter.countRoutesMemoized("X", "X", 4)).isEqualTo(1);
    }

    @Test
    void rejectsANullNetwork() {
        assertThatThrownBy(() -> new PaymentRouteCounter(null)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsNullFromOrTo() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThatThrownBy(() -> counter.countRoutesMemoized(null, "D", 1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> counter.countRoutesMemoized("A", null, 1)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsNegativeHops() {
        PaymentRouteCounter counter = new PaymentRouteCounter(NETWORK);

        assertThatThrownBy(() -> counter.countRoutesMemoized("A", "D", -1)).isInstanceOf(IllegalArgumentException.class);
    }
}

Ver relatório completo de cobertura JaCoCo →