Memoization
Memoization caches a pure function results keyed by its arguments, converting repeated computation into lookups — invalidation is unnecessary because identical inputs always yield identical outputs.
Definition
Memoization wraps a function with a cache mapping argument tuples to results. For pure functions — same inputs, same output, no side effects — the cache never goes stale and correctness is unconditional. Scope is per-process by default; distributed memoization becomes a read-through cache with its own coherence questions.
Context and scope
Applied to recursive computations, expensive derivations in compilers and renderers, React-family component memoization, and API response derivation layers.
Common misconceptions
- Memoization is caching with a fancy name — caching tolerates staleness and eviction by design; memoization of pure functions is exact and permanent in correctness terms
- Any function can be memoized — impure functions — random, time-dependent, side-effecting — produce wrong results from the cache
- Memoization always pays off — argument serialization, cache growth, and collision handling can cost more than the computation for cheap functions
Anti-patterns
- Memoizing functions reading mutable state or clocks and returning yesterday answer
- Using non-hashable or unstable arguments — object identity, floating point edge cases — and missing cache hits or colliding
- Unbounded memo tables on high-arity arguments and leaking memory invisibly
Related concepts
Related examples
Authoritative source
What it is
If a function is pure, its history is a lookup table. Memoization materializes that table as the function runs: first call computes, later calls read. The recursion-heavy algorithms — Fibonacci, parsing, tree edit distance — collapse from exponential to linear.
How it works
The wrapper computes a cache key from arguments — identity, structural hash, or serialization — and returns the cached value on hit. Weak-keyed maps let entries evaporate with their arguments, avoiding leaks. Language-level variants include lru_cache decorators with bounded size and compiler memo tables keyed structurally.
When to use it
Pure expensive computations with repeated argument sets: recursive solvers, derived data selectors, pure component render outputs. Do not memoize impure or I/O-bound functions without redesigning them into pure cores plus effectful shells.
Pitfalls
Key semantics decide everything: object-identity keys miss on structurally equal inputs; serialized keys of unstable key order miss perpetually. Bounded caches need an eviction policy, which reintroduces misses — measured benefit should include the miss path. Memoized exceptions and errors need explicit policy: caching a failure is usually wrong.