= Memoization
{wiki}
<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.<“Memo” Functions and Machine Learning by Donald Michie>[Donald Michie, “Memo” Functions and Machine Learning, Nature 218, pp. 19–22 (1968), abstract: programming-language rote learning motivated by efficiency during execution]{ref}
Back to article page
