What is memoization and how do you implement it?

Question

Accepted Answer

**Memoization** caches a function's results keyed by its arguments, so repeated calls with the same inputs return the cached result instantly instead of recomputing. It trades **memory for speed** and only works for **pure** functions (same input → same output, no side effects).

## A generic memoize wrapper

```js
function memoize(fn) {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args); // build a cache key from the arguments
    if (cache.has(key)) {
      return cache.get(key);          // cache hit — skip the work
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowSquare = n => { /* expensive */ return n * n; };
const fastSquare = memoize(slowSquare);
fastSquare(4); // computes → 16
fastSquare(4); // cached → 16 instantly
```

## A classic win: recursive Fibonacci

```js
const fib = memoize(n => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// turns exponential O(2^n) into roughly O(n) by caching subproblems
```

## Trade-offs and caveats

- **Cache key strategy**: `JSON.stringify` fails for functions, and key order matters for objects. For object arguments, a `WeakMap` (keyed by reference) avoids memory leaks.
- **Unbounded growth**: the cache never shrinks — use an **LRU** cache for long-running processes.
- Only memoize when recomputation is genuinely expensive and inputs repeat.

## Why it matters

Memoization is everywhere: React's `useMemo`/`React.memo`, Reselect selectors, dynamic programming.

The concept (cache pure results by input) is the same; the art is choosing the key and bounding the cache.