Memoização: anotar para não recalcular

A ideia de anotar o que já foi feito

Imagine somar uma coluna comprida de números várias vezes ao longo do dia. Da primeira vez você soma tudo com cuidado; das próximas, se você anotou o total num canto do papel, é só ler a anotação. Memoização é exatamente isso, dentro do programa. A função ganha uma tabela ao lado, o cache, e passa a seguir um ritual novo: antes de calcular qualquer coisa, ela olha a tabela para ver se aquela resposta já está anotada. Se estiver, devolve na hora, sem trabalho. Se não estiver, calcula uma única vez, escreve o resultado na tabela e só então devolve. Nunca a mesma conta é feita duas vezes.

No Fibonacci, a chave da tabela é o número n e o valor é o fib de n já calculado. Da primeira vez que a função precisa de fib de 3, ela calcula e anota. Quando outro galho pedir fib de 3, a resposta já vai estar lá, pronta para ser lida. O galho que antes se abria numa subárvore inteira de recálculo agora encosta na tabela e volta na mesma hora. A árvore de recursão, que era gorda de repetições, murcha: cada valor é calculado uma vez só, e o resto é consulta.

O cache em ação

No pseudocódigo, o cache costuma ser um dicionário ou uma lista que sobrevive entre as chamadas. A função ganha duas linhas no começo e uma no fim. No começo: se o valor de n já está na tabela, retorne o que está lá. No fim: antes de retornar o resultado calculado, guarde-o na tabela sob a chave n. Só isso. A estrutura recursiva continua igual, o caso base continua igual, a soma dos dois anteriores continua igual. A diferença é que agora a função lembra. Repare que a lógica do cálculo não mudou; a gente só ensinou a função a não repetir trabalho.

tabela <- {}   // cache: chave n, valor fib(n)

funcao fib(n)
  se n <= 1 entao
    retorne n
  fim
  se tabela tem a chave n entao
    retorne tabela[n]   // resposta pronta, sem recalcular
  fim
  resultado <- fib(n - 1) + fib(n - 2)
  tabela[n] <- resultado   // anota antes de devolver
  retorne resultado
fim

Duas linhas extras (consultar e anotar) transformam o desempenho, sem mudar a lógica do cálculo.

O preço da memória

Não existe almoço grátis, e a memoização cobra o preço dela em memória. A tabela precisa guardar um resultado para cada entrada diferente que aparecer. No Fibonacci, isso é pouca coisa: uma entrada por número até n. Mas em problemas com muitas combinações de entrada, a tabela pode crescer bastante, e aí você troca um problema de tempo por um de espaço. Na prática, quase sempre vale a pena, porque tempo costuma ser o recurso mais escasso e a repetição costuma ser gigante. Ainda assim, é bom ter consciência de que o cache mora em algum lugar e ocupa espaço.