Memoization

Memoization is a software optimization technique that speeds up programs by storing the results of expensive function calls and returning the cached value when the same inputs occur again. The term was coined by AI researcher Donald Michie in a 1968 Nature paper, where he proposed that machines could become more efficient by remembering the outputs of computations they had performed before. The word derives from the Latin memorandum (to be remembered), commonly shortened to memo, and is distinct from memorization. Mechanically, a memoized function maintains a lookup table — usually a hash table — keyed on the arguments it has already seen. On each call the wrapper checks whether the argument tuple is present: a hit returns the stored result immediately, a miss falls through to the original computation and writes the result back into the table. Because the cache equates equal inputs with equal outputs, the underlying function must be a Pure function — deterministic and free of side effects. Memoizing an impure function (one that reads from a database, depends on the clock, or mutates global state) silently introduces bugs. The canonical example is the recursive Fibonacci definition. Naive recursion recomputes the same subexpressions exponentially, giving running time O(2^n); memoizing the function so that fib(k) is evaluated at most once collapses the cost to O(n) time and O(n) space. This trade — more memory for less time — is the essence of the technique, and it underlies the top-down formulation of Dynamic programming, where overlapping subproblems are solved once and reused. The same idea powers recursive descent parsers (where it is called packrat parsing), compiler optimizations on referentially transparent expressions, and tabling in logic programming systems such as Prolog. Most modern languages ship memoization as a library decorator or higher-order function. Python's functools module provides @lru_cache and @cache, which wrap a function with a bounded or unbounded dictionary. Common Lisp and Scheme have idiomatic memoize wrappers, Perl ships the Memoize module, and Clojure exposes memoize in its core library. JavaScript, Ruby, and Haskell offer comparable patterns. Memoization is a specialised form of Cache (computing), but the two are not interchangeable. A general cache stores arbitrary data from any source — network responses, disk reads, rendered HTML — and carries its own invalidation policy. Memoization specifically caches function outputs and relies on the referential transparency of the function for correctness. When that precondition holds, memoization is one of the cheapest performance wins available; when it does not, the cache becomes a source of stale or wrong answers.