Memoization

Explanation

Memoization is top-down dynamic programming: you take a recursive function with overlapping subproblems and add a cache (a hash map from input to result). Before computing, check if the result is already cached. If yes, return the cached value. If no, compute it, store it in the cache, and return it. This ensures each unique input is computed at most once. The classic example is Fibonacci: fibNaive(40) makes over 300 million recursive calls because fib(38) is computed 2 times, fib(37) is computed 3 times, fib(36) is computed 5 times, etc. With memoization, each fib(n) is computed exactly once, reducing the call count from O(2^n) to O(n). Memoization works whenever: (1) the function is pure (same inputs always produce same output — no side effects or random state), (2) the inputs are hashable (can be used as dictionary keys), and (3) the function has overlapping subproblems. It trades O(n) (or O(n²) for 2D inputs) space for dramatic time savings. In JavaScript, the manual pattern is: const memo = {}; if (memo[n] !== undefined) return memo[n]; return memo[n] = compute(n);. Many utility libraries (lodash's memoize, React's useMemo, Redux's createSelector) provide general-purpose memoization. React's memo() and useMemo() apply the same concept to component re-rendering: skip re-rendering if props haven't changed.

Code Example

// Memoization: transforming exponential to linear

// Without memoization: O(2^n)
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// With memoization: O(n)
function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n); // cache hit
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);                 // cache the result
  return result;
}

// Generic memoize wrapper
function memoize(fn) {
  const cache = new Map();
  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

const memoFib = memoize(n => n <= 1 ? n : memoFib(n-1) + memoFib(n-2));

console.log(fib(50));     // 12586269025 — instant
console.log(fibSlow(40)); // 102334155  — takes ~1 second

Why It Matters for Engineers

Memoization is the simplest, most high-leverage optimization available for recursive algorithms. Adding a single cache can turn an exponentially slow function into a polynomial one. In production React applications, useMemo and React.memo prevent unnecessary re-renders, directly impacting user-perceived performance. In data pipelines, memoizing expensive database queries or API calls reduces latency and cost. Understanding memoization also builds the intuition for bottom-up DP: the table in tabulation is just a pre-filled memo cache. Once you understand why memoization works (each unique subproblem is solved once), the bottom-up approach is just the same idea without recursion overhead.