Memoization
Memoization is an optimization technique that caches the results of expensive function calls so that when the same inputs occur again, the cached result is returned instead of recomputing it.
Definition
Memoization is an optimization technique that caches the results of expensive function calls so that when the same inputs occur again, the cached result is returned instead of recomputing it.
Overview
Memoization is one of the simplest and most effective performance optimizations available to programmers because it targets a very common source of wasted work: calling a pure function with the same arguments repeatedly. The technique wraps a function so that, on each call, it first checks a cache (often implemented with a hash table) keyed by the function's arguments. If a cached result exists, it's returned immediately; otherwise the function runs normally and its result is stored before being returned. Memoization is most closely associated with dynamic programming, where it's used to eliminate redundant recursive calls in problems with overlapping subproblems — the textbook example being naive recursive Fibonacci, which without memoization performs exponential redundant work, and with memoization drops to linear time. But memoization applies more broadly than classic DP problems: web frameworks memoize expensive component renders, build tools memoize compilation steps for unchanged files, and API layers memoize responses to identical requests. The technique only works correctly for pure functions — functions whose output depends solely on their input and that have no side effects — because caching a result implicitly assumes the function will always return the same output for the same input. Applying memoization to an impure function (one that depends on external state or mutates data) can introduce subtle, hard-to-diagnose bugs. Memoization trades memory for speed, so it's most valuable when a function is called repeatedly with a limited set of distinct inputs and each call is expensive relative to a cache lookup; understanding Big O Notation helps clarify exactly how much time complexity is being saved in a given scenario.
Key Concepts
- Caches function results keyed by input arguments, usually via a hash table
- Only correct for pure, side-effect-free functions
- Core technique behind top-down dynamic programming
- Trades memory usage for reduced computation time
- Commonly built into language/library utilities (e.g., React's useMemo, Python's functools.lru_cache)
- Dramatically reduces redundant recursive calls in problems like Fibonacci
- Cache can be scoped per call, per session, or persisted across runs