Memoization Explained Visually: When Remembering Changes the Curve

Memoization means remembering a function result so the same question does not need to be solved again. The technique looks small, but it can remove thousands or millions of repeated calls when different paths reach the same states.

The condition matters: the same input must mean the same output. If the result depends on the clock, network, changing permissions, or mutable global state, storing arguments and answers is not enough.

Memoization does not mean “save everything.” It means recognizing when an answer is still the same.

01. Memoization in 30 Seconds

A memoized function needs four decisions:

1. Which arguments define the question.
2. How to recognize the same input.
3. Where the saved result lives.
4. When it stops being valid or should be released.

Flow of a memoized function from input to a cache hit or miss

The basic path is direct: build a key, look for a result, and calculate and store it when missing. The next equivalent call becomes a lookup.

Memoization and caching are not perfect synonyms. Memoization is a specific case: it associates the arguments of a deterministic function with its result. A general cache can represent remote data, use a TTL, invalidate after events, or be shared by multiple servers.

02. The Problem Is Not Computing: It Is Repeating States

Fibonacci exposes the problem with very little code:

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

To obtain fib(6), the fib(5) branch asks for fib(4), fib(3), and fib(2). The right branch requests several of those states again. Each call is cheap; the explosion comes from rebuilding complete subproblems.

Fibonacci tree with repeated states compared with unique memoized states

The naive implementation is commonly described as O(2ⁿ)—a simple upper bound for growth closer to φⁿ. After memoization, the relevant universe is no longer the number of paths but the number of unique states: 0, 1, 2, …, n.

This transformation does not happen because a Map is present. It happens because the problem has overlapping subproblems. If every input appears only once, storing results adds memory without avoiding work.

03. Top-Down, Tabulation, and Constant Memory

The top-down version keeps the recursion and shares one map throughout the main call:

function fibMemo(
  n: number,
  memo = new Map<number, number>([[0, 0], [1, 1]])
): number {
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, value);
  return value;
}

Each state is computed once; repetitions become hits. Because the default map is created at the start of every external invocation, it accelerates that recursive tree but does not share results between independent calls.

Bottom-up is tabulation, not strict memoization. It builds states in order and can avoid recursion:

function fibIterative(n: number): number {
  let previous = 0;
  let current = 1;

  for (let i = 0; i < n; i += 1) {
    [previous, current] = [current, previous + current];
  }

  return previous;
}

Comparison of naive recursion, top-down memoization, and bottom-up tabulation

Top-down is natural when you visit only part of a large state space. Bottom-up is often more predictable when every state is needed and a valid construction order is known.

04. The Key and Cache Lifetime Are the Contract

With numbers or strings, a Map recognizes equality by value. With objects, it recognizes reference identity:

const cache = new Map<object, string>();

cache.set({ id: 7 }, "Ada");
cache.get({ id: 7 }); // undefined: this is another object

If two different objects should represent the same question, use an explicit stable key:

type PathQuery = {
  start: { x: number; y: number };
  goal: { x: number; y: number };
  mapVersion: number;
};

function pathKey(query: PathQuery) {
  const { start, goal, mapVersion } = query;
  return `${start.x}:${start.y}|${goal.x}:${goal.y}|v${mapVersion}`;
}

Anatomy of a complete and stable memoization key

The key must avoid collisions, normalize equivalent inputs, and include every dependency that changes the result. You must also choose the scope: one call, one request, one component, or the entire process. An unbounded persistent Map can retain memory indefinitely; a WeakMap allows object keys to be collected when no other references remain.

05. When Remembering Creates New Problems

Memoization trades time for memory. Review these risks first:

• Low reuse: if almost every key is different, misses dominate.
• Stale data: if the answer changes without the key changing, the function was not truly deterministic.
• Mutability: returning the same object lets one consumer alter the answer seen by others.
• Growth: a long-lived function can accumulate entries without a limit.
• Concurrency: two simultaneous requests can start the same work before a result exists.

For asynchronous functions, storing the pending promise shares in-flight work. When the promise rejects, removing it allows a later retry:

function memoizeAsync<Args extends unknown[], Value>(
  fn: (...args: Args) => Promise<Value>,
  keyOf: (...args: Args) => string
) {
  const cache = new Map<string, Promise<Value>>();

  return (...args: Args) => {
    const key = keyOf(...args);
    const hit = cache.get(key);
    if (hit) return hit;

    const pending = fn(...args);
    cache.set(key, pending);
    pending.catch(() => cache.delete(key));
    return pending;
  };
}

When TTL, LRU, event-driven invalidation, cross-server coherence, or dynamic permissions become necessary, the problem belongs to a broader caching policy. Memoization remains the reuse idea; infrastructure decides how long that reuse is safe.

06. Decision Checklist

Before memoizing, answer:

1. Does the same input always produce the same output?
2. Do inputs repeat with meaningful frequency?
3. Does the computation cost more than building a key and checking storage?
4. Does the key represent every dependency?
5. Where should the memory live, and when is it released?
6. Can a returned object be mutated?
7. Must pending work be shared or retries handled?

Memoize when a small set of repeated states exists inside a much larger exploration. Do not wrap every function by reflex: measure hits, misses, retained memory, and avoided cost.

The final question is not “can I save this answer?” It is “will I ask exactly the same question again, and will it still mean the same thing?”.