---
title: "Recursion with memoization"
url: https://algopath.pro/patterns/memoization
language: en
summary: "Recursion that writes down every answer it computes. When the same argument comes back, the stored value is handed back."
updated: 2026-08-24
---

# Recursion with memoization

Recursion that writes down every answer it computes. When the same argument comes back, the stored value is handed back.

## How does Recursion with memoization work?

Write the plain recursion first. Get it correct before trying to make it fast.

Look at what the arguments really are. If two calls share them, they share the answer.

Add a cache keyed by those arguments. A map or a plain array both work.

At the top of the function, return the cached answer if one exists. Nothing else runs.

Before returning, store the answer under its key. The next call reads it instead of recomputing.

Each distinct argument is now computed once. The tree of calls collapses into a graph.

- `fib(5) needs fib(4) and fib(3)` The naive version splits into two calls.
- `fib(4) needs fib(3) and fib(2)` Now fib(3) is wanted twice over.
- `cache = {2: 1, 3: 2}` The first fib(3) is computed and stored.
- `fib(3) is a lookup` The second fib(3) reads the cache. Its whole subtree is skipped.
- `15 calls become 9` Without a cache, fib(50) would take billions of calls.

## When should you use Recursion with memoization?

- recursive calls repeat the same arguments (overlapping subproblems)
- plain recursion is correct but too slow / exponential blow-up
- small number of distinct states even though the recursion tree is huge
- cache/memo the result of (i, ...) before returning
- Fibonacci / climbing stairs / grid-path wording with a hint to cache

## What is Recursion with memoization confused with?

- **Recursion** - Plain recursion recomputes a repeated argument every time. The cache is the entire difference.
- **Dynamic programming (1-D)** - Bottom-up DP fills a table in a fixed order. This fills it on demand, from the top down.
- **Hash set / map** - The cache is usually a map. This page is about deciding when to keep one.
- **Backtracking** - Backtracking explores paths that all differ, so nothing repeats. A cache there stores keys never asked again.

## What is the time and space complexity of Recursion with memoization?

Cost is the number of distinct arguments times the work per call. A cache of 1e6 keys is fine.

## A worked example of Recursion with memoization

### Fewest coins for an amount

You get a list of coin values and an amount. Return the fewest coins that add up to it.

If no combination works, return minus one.

Ask the same question about a smaller amount. Each coin gives one branch.

The remaining amount alone identifies a subproblem. So the cache is keyed by that amount.

```javascript
function coinChange(coins, amount) {
    const cache = new Map();

    function best(left) {
        if (left === 0) return 0;
        if (left < 0) return Infinity;
        if (cache.has(left)) return cache.get(left); // computed before

        let answer = Infinity;
        for (const coin of coins) {
            answer = Math.min(answer, best(left - coin) + 1);
        }

        cache.set(left, answer); // store the failure too
        return answer;
    }

    const result = best(amount);
    return result === Infinity ? -1 : result;
}
```

## Common mistakes with Recursion with memoization

- **A key that leaves out an argument** Every value the answer depends on belongs in the key. A partial key returns another call's answer.
- **Caching a mutable object** Storing a reference lets a later call change it. Store a copy or a plain value.
- **Not caching a failure** A branch that fails is still an answer worth keeping. Otherwise dead ends get explored again.
- **Caching where nothing repeats** If every argument is unique, the cache only costs memory. Check the overlap before adding it.

## Which interview problems use Recursion with memoization?

- **Fibonacci** The shortest example of an overlapping subproblem.
- **Climbing stairs** The same shape with a different base case.
- **Coin change** Keyed by the amount still left.
- **House robber** Keyed by the index you are standing on.
- **Word break** Keyed by the start position in the string.
- **Unique paths** Keyed by the pair of coordinates.
- **Longest increasing path in a matrix** Keyed by the cell, and no visited set is needed.

## JavaScript

```javascript
function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}
```

## Python

```python
def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]
```

## PHP

```php
function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fib($n - 1, $memo) + fib($n - 2, $memo);
}
```