Skip to main content
Definition Website Computer and Technology

Memoization

Subject: Computer and Technology noun /ˌmɛm.oʊ.aɪˈzeɪ.ʃən/ 1 definition

  1. Definition (noun)

    Entry #56 · Updated

    Memoization 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_cache or 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.useMemo or 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 as fib(10) are recomputed repeatedly. Adding a hash-map memoization cache stores each fib(n) result on its first evaluation, cutting the execution to 41 unique subproblem calculations and 79 total invocations.