Memoization
Subject: Computer and Technology noun /ˌmɛm.oʊ.aɪˈzeɪ.ʃən/ 1 definition
- dynamic-programming
- algorithm-optimization
- functional-programming
- computer-science
-
Definition (noun)
Entry #56 · UpdatedMemoization is an optimization technique in computer programming that caches the return values of deterministic function calls keyed by their input arguments so subsequent invocations with identical inputs return the stored result directly instead of recomputing it. It trades additional memory space for reduced execution time, transforming exponential-time recursive algorithms with overlapping subproblems into linear- or polynomial-time computations. Because memoization assumes a function's output depends solely on its inputs, it applies strictly to pure, referentially transparent functions without side effects, distinguishing it from general-purpose data caching across mutable state or external I/O boundaries.
Common Forms
Decorator and Wrapper Memoization: Intercepts calls to a pure function using a higher-order wrapper (such as Python's
@functools.lru_cacheor JavaScript memoize utilities) to look up and store outputs by argument signature transparently.Top-Down Dynamic Programming: Records solutions to recursive subproblems in an explicit lookup table or array as branches execute, eliminating redundant subtree evaluations without rewriting the algorithm into a bottom-up loop.
Bounded and Eviction-Based Memoization: Constrains cache memory growth with capacity limits and eviction policies—such as Least Recently Used (LRU), First-In First-Out (FIFO), or weak references—to prevent unbounded heap consumption in long-running services.
UI and Selector Memoization: Compares current input arguments or dependency references against the last invocation (as in
React.useMemoor state selectors) to skip expensive recomputations and re-renders when inputs remain unchanged.
Example
A naive recursive calculation of the 40th Fibonacci number (
fib(40)) triggers 331,160,281 function calls because overlapping subproblems such asfib(10)are recomputed repeatedly. Adding a hash-map memoization cache stores eachfib(n)result on its first evaluation, cutting the execution to 41 unique subproblem calculations and 79 total invocations.