Consider the recursive Fibonacci function, which defines each number as the sum of the two before it. To compute fib(5) it asks for fib(4) and fib(3); each of those asks for smaller values, and the same sub-problems — fib(2), fib(3) — get solved over and over. By fib(40) the function is doing billions of repeated additions and takes seconds; by fib(50) it will not finish in your lifetime.
The waste is the clue. Every call to fib(3) returns the same answer, so recomputing it is pure lost work. Memoization fixes exactly this: the first time you ask for fib(3) you compute it and remember the result; every later call with 3 returns the stored answer instantly. The same problem shows up outside Fibonacci anywhere a function re-derives an answer it already computed — rendering the same chart twice, re-parsing the same input, re-fetching a value that never changed.
flowchart TD F5["fib(5)"] --> F4a["fib(4)"] F5 --> F3a["fib(3)"] F4a --> F3b["fib(3)"] F4a --> F2a["fib(2)"] F3a --> F2b["fib(2)"] F3a --> F1a["fib(1)"] style F5 fill:#3776ab,color:#fff style F3b fill:#b91c1c,color:#fff style F3a fill:#b91c1c,color:#fff style F2a fill:#b91c1c,color:#fff style F2b fill:#b91c1c,color:#fff
How a memoizer works
A memoizer is a small higher-order function — a function that takes a function and returns a new one. The new function behaves exactly like the original but keeps a private cache: a lookup table mapping arguments to results. On each call it checks the cache. If the arguments are already there, it returns the stored value without doing any work. If not, it runs the real function, saves the answer under those arguments, and returns it.
The cache is held in a closure, so it is private to the returned function — no other code can see or tamper with it. That privacy is what makes the cache safe: each memoized function owns its own table, and the outside world only ever sees the same inputs going in and the same answers coming out. Calling the memoized version is indistinguishable from calling the original — it just happens to be faster the second time.
let calls = 0;
function fib(n) {
calls += 1;
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
const result = fib(10);
console.log(result); // 55
console.log(calls); // 177 — fib(3) alone was computed many times
The payoff: exponential becomes linear
With a memoizer wrapped around fib, every distinct input is computed exactly once. fib(10) still needs fib(9) and fib(8), but the moment fib(8) is finished its result is cached, so when fib(9) also needs fib(8) the answer is waiting. A function that did 177 calls to reach fib(10) now does roughly 10. The savings come from never solving the same sub-problem twice.
This is the same trade memory makes everywhere: spend a little storage to save a lot of time. Memoization shines on functions that are expensive and called repeatedly with overlapping arguments — renderers, parsers, recursive algorithms, anything that revisits the same question. Memoizing a function does not change what it returns — only how long the answer takes to arrive.
flowchart TD
C["call memoFn x"] --> Q{"x in cache?"}
Q -->|"yes"| R1["return cached value"]
Q -->|"no"| RUN["run fn x"]
RUN --> STORE["store result at key x"]
STORE --> R2["return result"]
style Q fill:#e0900b,color:#fff
style RUN fill:#1e7f3d,color:#fff
style STORE fill:#3776ab,color:#fff
const cache = {};
function fib(n) {
if (n in cache) return cache[n];
if (n < 2) return n;
const value = fib(n - 1) + fib(n - 2);
cache[n] = value;
return value;
}
console.log(fib(10)); // 55
console.log(fib(20)); // 6765
console.log(cache); // each value stored once
When memoization backfires
Memoization is only correct when the underlying function is pure — same arguments, same answer, every time. Wrap a function that reads the clock, generates a random number, or pulls from a changing source, and the cache will faithfully replay the first answer forever, hiding every update. Stale data from a cache is a particularly nasty bug because the code looks correct.
There is also a quieter trap. The cache keys arguments by value, and JavaScript object keys are strings. A plain object cache works for numbers and strings but collapses distinct object arguments into the same key ([object Object]). Memoizing functions that take objects or arrays needs a Map or a hand-built key — or just skip the cache there. A cache that never expires also grows without bound, so memoizing a function called with millions of distinct inputs will slowly eat memory.
flowchart TD P["pure fn<br/>same args, same result"] --> PM["safe to memoize"] I["impure fn<br/>time or random"] --> IM["memoize returns stale wrong value"] style P fill:#1e7f3d,color:#fff style I fill:#b91c1c,color:#fff style PM fill:#3776ab,color:#fff style IM fill:#b45309,color:#fff
function memo(fn) {
const cache = {};
return function (n) {
if (n in cache) return cache[n];
const result = fn(n);
cache[n] = result;
return result;
};
}
let calls = 0;
const square = memo((n) => {
calls += 1;
return n * n;
});
console.log(square(5)); // 25 (runs fn)
console.log(square(5)); // 25 (cached — fn NOT run again)
console.log(square(5)); // 25 (cached again)
console.log(calls); // 1 — three calls, one real computation
Write memo(fn) that takes a single-argument function and returns a new function with the same behaviour, but which remembers results. The first call with a given argument runs fn and stores the answer; later calls with the same argument return the stored answer without re-running fn. Assume the argument is always a number. (Hint: close over a plain object used as the cache.)
function memo(fn) {
// close over a cache object; key by the argument
}
Declare const cache = {} inside memo, before the return.
Check
n in cachefirst; only call fn and store on a miss.
function memo(fn) {
const cache = {};
return function (n) {
if (n in cache) return cache[n];
const result = fn(n);
cache[n] = result;
return result;
};
}
What does this print? slowSquare records every real computation in count. The memoized version only computes each distinct input once.
let count = 0;
function slowSquare(n) {
count += 1;
return n * n;
}
function memo(fn) {
const cache = {};
return function (x) {
if (x in cache) return cache[x];
cache[x] = fn(x);
return cache[x];
};
}
const fast = memo(slowSquare);
fast(3);
fast(3);
fast(4);
console.log(count);
console.log(fast(3));
fast(3) runs slowSquare once; the second fast(3) is a cache hit.
fast(4) is a new input, so it runs slowSquare a second time — that makes count 2.
Below is a naive exponential fib and the memo helper. Rewrite fib as a memoized function whose recursive calls go through the cache: declare it as const fib = memo(function (n) { ... }), so that inside the body the name fib resolves to the memoized version. That is what makes repeated sub-problems hit the cache instead of being recomputed.
function memo(fn) {
const cache = {};
return function (n) {
if (n in cache) return cache[n];
const result = fn(n);
cache[n] = result;
return result;
};
}
// TODO: replace the naive fib with a memoized one whose recursion
// routes through the cache: const fib = memo(function (n) { ... });
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
Declare
const fib = memo(function (n) {...})so the body'sfibrefers to the memoized version.Arrow functions have no self-name, but a named inner function or the outer const both let the recursion reach the cache.
function memo(fn) {
const cache = {};
return function (n) {
if (n in cache) return cache[n];
const result = fn(n);
cache[n] = result;
return result;
};
}
const fib = memo(function (n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
});
This memo is meant to cache results so each distinct argument runs fn only once. But it uses a fixed key, so a second call with a different argument wrongly returns the first call's cached value. Fix the key so the cache is indexed by the actual argument.
function memo(fn) {
const cache = {};
return function (n) {
if ("last" in cache) return cache["last"]; // wrong key — ignores n
cache["last"] = fn(n);
return cache["last"];
};
}
The cache key must be n, not a fixed string.
Use
n in cachefor the check and cache[n] for both store and return.
function memo(fn) {
const cache = {};
return function (n) {
if (n in cache) return cache[n];
cache[n] = fn(n);
return cache[n];
};
}
Memoization is unsafe for which kind of function?
Memoization assumes the same arguments always yield the same result. A function returning the time or a random number is impure — its output changes between calls — so caching the first answer and replaying it returns a stale, wrong value. Only pure functions are safe to memoize.
Recap
- Memoization caches a function's results keyed by its arguments, so repeated calls with the same input return instantly.
- A memoizer is a higher-order function that wraps
fnand guards a private cache held in a closure. - It turns overlapping work — like naive recursive Fibonacci — from exponential into roughly linear, trading memory for time.
- It is only correct for pure functions; caching an impure function replays a stale, wrong answer.
- Plain-object caches work for number and string arguments; for objects or arrays, reach for a
Mapor a hand-built key.
Next you'll combine small functions into pipelines with composition and pipe — and memoization is one optimisation you will often slot into exactly those pipelines.