Memoization

Memoization retains a completed function result under a memoization key and returns that result when an equivalent request recurs. For a terminating pure function, repeated evaluation can therefore become lookup rather than repeated work. The benefit is especially striking with recursion and overlapping subproblems: a large tree of calls can refer to a small Directed acyclic graph of distinct answers. The memoization cache contract determines whether reuse is correct; the memoization cache lifetime determines whether an answer is still present when wanted.

Memoization records computed answers, whereas a memory cache retains data from computer memory. A CPU cache hit does not by itself prevent a program from evaluating the same function again. Spreadsheet dependency evaluation adds an explicit mechanism for invalidating affected cached cell values after inputs change; a general memoization table does not discover such changes automatically.

A documented early motivation was to let programs improve their efficiency during execution through rote learning: the abstract of a 1968 paper explicitly proposes such a programming language facility.^[ref]