Memoization

O que é

Memoization é guardar o resultado de uma computação para não recalcular a mesma coisa depois.

Se a entrada se repete, a resposta já está pronta.

Quando usar

Ela aparece muito quando:

• a função é pura
• o cálculo é caro
• as mesmas entradas voltam várias vezes

Recursão com subproblema repetido é um caso clássico.

Erro comum

O erro clássico é chamar qualquer cache de memoization.

O nome faz mais sentido quando você guarda resultado a partir da entrada de uma função ou subproblema.

Pergunta melhor

Antes de aplicar, vale perguntar:

1. a mesma entrada volta mesmo?
2. o custo de guardar compensa o custo de recalcular?
3. a resposta depende só da entrada ou também de estado externo?