Memoization

Definição

Memoization é uma técnica de otimização que armazena os resultados de chamadas anteriores de uma função para reaproveitá-los sempre que os mesmos argumentos forem usados novamente.

Ela é útil quando a função é chamada várias vezes com os mesmos valores — assim, o resultado já conhecido pode ser reutilizado.

Por que usar

• Evita fazer o mesmo cálculo várias vezes;
• Deixa funções recursivas muito mais rápidas;
• É fácil de implementar com dicionários (em Python, por exemplo).

Diferença para Programação Dinâmica

As duas ideias são parecidas, mas:

• Memoization usa uma abordagem de cima para baixo (top-down), com recursão;
• Programação Dinâmica geralmente usa uma abordagem de baixo para cima (bottom-up), preenchendo uma tabela.

Exemplo prático (Python) — Fibonacci com memoization

def fibonacci(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
    return cache[n]

print(fibonacci(8))  # Saída: 21

Saída

21

Relacionados

• Programação Dinâmica
• Backtracking
• Branch and Bound