Book 01 · Programming FundamentalsPage 36 of 56

Memoization

Pronunciation: mem-oh-ih-ZAY-shun

Updated September 30, 20262 min read

In short

Memoization is an optimization technique that stores the results of function calls and returns the saved result when the same inputs occur again.

What is memoization?

Memoization is a way to speed up a function by remembering its answers. The first time the function runs with a particular set of arguments, it computes the result and saves it in a lookup table, often a hash map keyed by those arguments. The next time it is called with the same arguments, it returns the saved result immediately instead of doing the work again.

It only works correctly for pure functions, meaning functions that always return the same output for the same input and have no side effects, such as writing to a database. The classic example is the recursive Fibonacci function: without memoization it makes an exponential number of calls, recomputing the same values over and over, while with memoization each value is computed once and the running time drops to linear, or O(n). Memoization is the top-down form of dynamic programming.

It's like writing the answer to a hard math problem on a sticky note, so the next time someone asks you simply read the note. Memoization is built into many tools, such as Python's functools.cache decorator and React's useMemo hook and memo function, which skip recalculating values or re-rendering components when their inputs haven't changed.

Memoization is a specific kind of caching. Caching is the broad idea of storing any expensive result for reuse, often shared between servers and expired over time, while memoization caches the return values of one function, usually in memory inside a single process. The trade-off is memory: storing every result can grow without limit, so many memoized functions keep only the most recent entries.

Key takeaways

Memoization saves a function's results and reuses them for repeated inputs.
It is safe only for pure functions with no side effects.
It can turn exponential recursive algorithms, like naive Fibonacci, into linear ones.
It trades extra memory for less computation.
Memoization is a narrow form of caching that applies to function calls.

Example

A hand-written memoize helper in JavaScriptjavascript

function memoize(fn) {
  const cache = new Map();
  return (n) => {
    if (cache.has(n)) return cache.get(n); // reuse a saved result
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

const fib = memoize((n) => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
console.log(fib(50)); // 12586269025, with each fib(n) computed only once
// Without memoization, fib(50) would take about 40 billion calls

Readers ask

What is the difference between memoization and caching?

Memoization is a specific type of caching that stores a function's return values keyed by its arguments, usually in memory. Caching is the broader idea and also covers HTTP responses, database queries, and files, often with expiry times and shared storage.

What is the difference between memoization and dynamic programming?

Dynamic programming solves a problem by combining the solutions to overlapping subproblems. Memoization is the top-down way to do it, adding a cache to a recursive function, while tabulation is the bottom-up way that fills in a table step by step.

When should you not use memoization?

Avoid it for functions with side effects or results that depend on changing data, such as the current time, and for functions that are cheap or rarely called with the same inputs. In those cases the extra memory and lookups cost more than they save.