Suggest an edit

Improve this article

Refine the answer for “Function memoization”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

**Memoization is an optimization technique where a function remembers the results of its calls and returns a ready value instead of recomputing it.** In JavaScript it is built on a closure: an outer function creates the cache, and the inner one checks that cache before reaching for the original function.

## Theory

### TL;DR
- Memoization is an "arguments -> result" cache that lives in the wrapper's closure.
- The cache key is usually built with `JSON.stringify(args)`, and a `Map` is a better store than a plain object.
- It is only correct for pure functions: the result must depend solely on the arguments.
- An unbounded cache grows forever, so real code adds a limit (an LRU strategy).
- The biggest win is recursion with overlapping subproblems, for example Fibonacci numbers.
- For async functions you cache the Promise, not the value, so that parallel calls do not fire two requests.

### Quick example
```javascript
function memoize(fn) {
  const cache = {};

return function (...args) {
    const key = JSON.stringify(args); // build a key from the arguments

if (key in cache) {
      console.log('from cache:', key);
      return cache[key];
    }

console.log('computing:', key);
    const result = fn(...args);
    cache[key] = result;
    return result;
  };
}

function slowAdd(a, b) {
  // simulating heavy computation
  for (let i = 0; i < 1e8; i++);
  return a + b;
}

const memoAdd = memoize(slowAdd);

console.log(memoAdd(2, 3)); // computing
console.log(memoAdd(2, 3)); // from cache
console.log(memoAdd(4, 5)); // computing
```

Repeated calls with the same arguments are no longer recomputed, the value is simply taken from memory.

### The basic implementation: closure plus store
Every memoization consists of three parts:

| Part | Role |
| --- | --- |
| Closure | Keeps the cache alive between calls to the wrapper |
| Key | Turns the argument list into something comparable (a string) |
| Store | An `Object` or a `Map` holding the key-value pairs |

An object as the store is simple but has awkward traits: keys are always coerced to strings, and inherited properties such as `toString` or `constructor` can accidentally be "found" in the cache. So the more universal option is a `Map`:

```javascript
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(...args);
    cache.set(key, result);
    return result;
  };
}
```

Advantages of `Map`: no clashes with the prototype, an honest `size`, keys that keep insertion order (which is what LRU needs), and deletion through `delete` that is faster than `delete obj[key]`.

### Bounding the cache: LRU
An unbounded cache is a memory leak: every new argument set adds an entry that is never released. A simple LRU (least recently used) evicts the entry used longest ago once the cache outgrows its limit. A `Map` is ideal here because it iterates in insertion order: to "refresh" an entry you just delete it and insert it again, which moves it to the end.

```javascript
function memoize(fn, limit = 5) {
  const cache = new Map();

return function (...args) {
    const key = JSON.stringify(args);

if (cache.has(key)) {
      // refresh the usage order
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value);
      return value;
    }

const result = fn(...args);
    cache.set(key, result);

// if the cache is too large, drop the oldest entry
    if (cache.size > limit) {
      const oldestKey = cache.keys().next().value;
      cache.delete(oldestKey);
    }

return result;
  };
}
```

The cache is now a sliding window: it keeps the last N calls, which for real applications is usually exactly what you want.

### Memoizing recursion: Fibonacci numbers
The clearest win is recursion whose subproblems overlap. A naive `fib(n)` computes the same values an exponential number of times.

```javascript
function memoize(fn) {
  const cache = {};
  return function (n) {
    if (n in cache) return cache[n];
    const result = fn(n);
    cache[n] = result;
    return result;
  };
}

const fib = memoize(function f(n) {
  if (n <= 1) return n;
  return f(n - 1) + f(n - 2);
});

console.log(fib(40)); // fast, despite the recursion
```

Without memoization this would be **tens of millions of calls**, and with the cache, **only about 40**. Note the named function expression `function f`: the recursive call must go through the same wrapper, otherwise the inner calls bypass the cache and the optimization disappears.

### Memoizing async functions
When you need to cache the result of a `fetch` or a database query, cache the **Promise**, not the value. Otherwise two concurrent calls with the same key will both start a network request, because the first has not settled yet and the cache is still empty.

```javascript
function memoizeAsync(fn) {
  const cache = new Map();

return async function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);

const promise = fn(...args).then(result => {
      cache.set(key, result);
      return result;
    });

cache.set(key, promise);
    return promise;
  };
}
```

Example usage:

```javascript
const fetchUser = memoizeAsync(async (id) => {
  const res = await fetch(`https://api.example.com/users/${id}`);
  return res.json();
});

await fetchUser(1); // first time, an HTTP request
await fetchUser(1); // second time, instantly from the cache
```

Errors deserve separate thought: if `fn` rejects, the rejected Promise stays in the cache forever. A production version therefore removes the key on failure with `.catch(err => { cache.delete(key); throw err; })`.

### When memoization is worth it

| Scenario | Good fit? | Why |
| --- | --- | --- |
| Expensive computation | Yes | Speeds up repeated calls |
| Repeating arguments | Yes | This is exactly where the cache pays off |
| Different arguments every time | No | The cache only wastes memory |
| HTTP requests, database | With care | Fine if the data changes rarely |
| Large volumes of data | With care | Watch memory, a limit is required |

In short: memoization trades memory for CPU time. Before adding it, measure whether the function really is the bottleneck.

### Common mistakes
1. **Memoizing an impure function.** If the result depends on time, random numbers, module state or an external request, the cache will hand back a stale value. `memoize(() => Date.now())` freezes the first timestamp forever.
2. **Forgetting to bound the cache.** Memoization in a long-lived process (a server, an SPA) without a limit is a classic memory leak.
3. **Recursing into the original instead of the wrapper.** If the recursion calls the original function, the cache fills up but is never read, and there is no win.
4. **Trusting `JSON.stringify` blindly as the key.** Key order in objects affects the string, so `{a: 1, b: 2}` and `{b: 2, a: 1}` produce different keys. On top of that `undefined`, functions and `Symbol` vanish during serialization, and cyclic structures throw.
5. **Holding strong references to argument objects.** Caching by the object itself stops the garbage collector from freeing it; `WeakMap` exists for that case and does not block collection.
6. **Caching the async result instead of the Promise.** Parallel calls will still issue several requests, because the cache entry appears only after the response arrives.
7. **Applying memoization to cheap functions.** Computing the key with `JSON.stringify` costs time by itself, so a wrapper around `(a, b) => a + b` ends up slower than the original.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1204 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.