One Line Made This Python Function 1,000,000x Faster (Memoization with @cache)

This Python function takes 6 seconds. I add one line, and it takes 4 microseconds, which is more than a million times faster. The trick is called memoization. It's a classic interview topic, and it fixes real slow code too.

Every number below was measured on Python 3.15.2 (and Node.js 22 for the JS version).

Video version:

The slow function

Fibonacci, the textbook way:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(40)   # 102334155

Short, clean, correct. Here's how long it takes, and how many times fib gets called:

fib(20)    0.001 s        21,891 calls
fib(25)    0.010 s       242,785 calls
fib(30)    0.108 s     2,692,537 calls
fib(35)    1.2 s      29,860,703 calls
fib(40)    5.96 s    331,160,281 calls   🐌

Every +5 on n makes it about 10× slower. That's exponential time, roughly O(φⁿ).

Why it's slow: the same work, again and again

fib(5)
├── fib(4)
│   ├── fib(3)        ← fib(3), once
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)            ← fib(3) again!
    ├── fib(2)        ← fib(2): 3rd time
    └── fib(1)

Nothing is remembered. Even in fib(5), fib(3) is computed twice and fib(2) three times. For fib(40), the same small values are recomputed millions of times. This is called having overlapping subproblems.

The fix: one line

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

@cache stores the result for every argument. The first time fib(30) is computed it's saved, and every later call is just a dictionary lookup.

>>> fib(40)
102334155            # 3.8 µs (median of 7 runs, cold cache)
>>> fib.cache_info()
CacheInfo(hits=38, misses=41, maxsize=None, currsize=41)

That's 5.96 s → 3.8 µs, about 1.5 million times faster in my test. Each value from 0 to 40 is computed exactly once (41 misses), and the 331 million calls become 79. It now runs in linear time, O(n). Even fib(500), a 105-digit number, takes under a millisecond.

@cache is available since Python 3.9. On older versions, use @lru_cache(maxsize=None).

The interview version: grid paths

Interviewers love this pattern. How many paths are there from the top-left to the bottom-right of a grid, moving only right or down?

from functools import cache

@cache
def paths(r, c):
    if r == 0 or c == 0:
        return 1
    return paths(r - 1, c) + paths(r, c - 1)

paths(2, 2)     # 6
paths(16, 16)   # 601080390

The number of paths to a cell is the paths from above plus the paths from the left. That's the same overlapping-subproblem structure, so the same one-line fix applies. For paths(13, 13), it went from 0.51 s → 32 µs. (Sanity check: math.comb(32, 16) is also 601,080,390.)

Climbing stairs, coin change, edit distance and longest common subsequence all follow this recipe: write the recursion, then add memoization. That's top-down dynamic programming.

JavaScript: write memoize yourself

There's no built-in decorator, but it only takes a few lines:

function memoize(fn) {
  const cache = new Map();
  return (n) => {
    if (cache.has(n)) return cache.get(n);
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

const fib = memoize((n) => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// fib(40): 567 ms → 0.022 ms

Note that the recursive calls must go through the memoized fib, or nothing gets cached.

When (not) to use @cache

✅ Use it when:

• The same inputs are computed again and again
• The function is pure: same input, same output

❌ Don't use it for:

• Functions with side effects (sending emails, writing files) or random results
• Unhashable arguments. Lists and dicts raise TypeError: unhashable type; pass tuples instead.

⚠️ Watch out for:

• Memory: @cache never forgets. For many different inputs, use @lru_cache(maxsize=1000).
• Recursion depth: fib(5000) with a cold cache still raises RecursionError: maximum recursion depth exceeded. For big n, a simple loop wins:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Which slow function in your code could use @cache? 👇

---

I post one tested coding tip every day on YouTube at Refactorly. The 30-second version of this one is here.