Memoization in Python: lru_cache, when it helps and how it differs from a table

Short answer. Memoization is a cache in front of a recursive function. The function stores the answer for each set of arguments. A repeated call returns it from the dictionary. Exponential recursion turns linear or quadratic. In Python it is one line: the lru_cache decorator. Below: when it works, code, a traced example and the bottom-up comparison.

What is memoization?

A recursive function often calls itself with the same arguments. Fibonacci: fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. The call tree grows like 2ⁿ.

Memoization puts a dictionary in front of the function. Answer present: return it. Answer missing: compute, store, return. Each set of arguments is computed once.

This is top-down dynamic programming. Same table, but recursion picks the fill order.

The word is spelled without an r. It comes from memo, a note. The function leaves itself notes about past answers.

When does memoization help, and when not?

• It helps when subproblems repeat: Fibonacci, path counts, string splits.
• It helps when the function is pure. The answer depends only on the arguments.
• It does nothing when every call is different: tree traversal, sorting.
• It fails when arguments are unhashable: lists, dictionaries.

The test is simple. Draw the call tree for a small input. Repeated nodes mean memoization will work.

What does memoization look like on an example?

fib(5) without a cache: 15 calls. With a cache: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0) run once each. Every other call returns from the dictionary. Six real computations.

For n = 40 it is hundreds of millions of calls against forty.

How do you write memoization in Python?

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

# the same by hand
def fib_memo(n, memo=None):
    memo = {} if memo is None else memo
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

@lru_cache(maxsize=None)
def unique_paths(r, c):
    if r == 1 or c == 1:
        return 1
    return unique_paths(r - 1, c) + unique_paths(r, c - 1)

def word_break(s, words):
    words = set(words)

    @lru_cache(maxsize=None)
    def can(i):                      # can s[i:] be split
        if i == len(s):
            return True
        return any(s[i:j] in words and can(j) for j in range(i + 1, len(s) + 1))

    return can(0)

lru_cache hashes the arguments. They must be numbers, strings or tuples. Turn lists into tuples first.

How is memoization different from a bottom-up table?

Trait	Memoization	Bottom-up table
Code	Recursion plus a dictionary	A loop plus an array
Order	Recursion decides	You decide
Unneeded states	Never computed	All computed
Memory	Dictionary plus call stack	Array, often shrinkable
Limit	Python recursion depth	You must find the order
Pick it when	The transition is complex, states are sparse	States are many, memory matters

How does memoization solve Unique Paths?

An r by c grid, moves go right or down. How many paths corner to corner? Paths from a cell equal paths from its right neighbour plus its lower neighbour. Base: one row or one column, one path.

There are r · c states, each computed once. Time O(r · c). Without the cache it is exponential.

How does it solve Word Break?

Can a string be split into dictionary words? The function can(i) answers for the suffix from position i. Try each cut j. The prefix must be a word and the rest from j must split. Caching on i gives O(n²) plus substring checks.

When is memoization not enough?

When n is above ten thousand. Recursion goes n deep, and Python stops it. Rewrite bottom-up as a loop. The transition stays the same, only the code shape changes.

The second case is memory. The dictionary holds every state. A loop with two variables holds two numbers. Interviewers ask about this after the working solution.

What mistakes break memoization?

• A mutable default argument memo={}. The cache leaks between top-level calls.
• The function reads an outer variable that the cache key ignores.
• Recursion deeper than Python's limit. Raise it or switch to a loop.
• Caching on objects compared by identity. Equal data produces different keys.

How do you explain memoization in an interview?

Write the plain recursion first. Then show that subproblems repeat. Then add the dictionary. Three steps, and the interviewer sees your reasoning.

Give the complexity as distinct states times work per call. For Fibonacci that is O(n).

Drill this pattern on the recursion with memoization page. The bottom-up form lives on the dynamic programming page.

FAQ

What is the difference between lru_cache and cache?

functools.cache is lru_cache with no size limit. It arrived in Python 3.9. For interviews there is no difference.

How do you memoize a method?

The decorator works, but self becomes part of the key. Better to move the computation into a nested function inside the method.

Can you memoize a function with two arguments?

Yes. The key becomes the tuple of arguments. The state count is the product of the ranges, so watch memory.

Where does memoization show up in real systems?

React memoizes a component's render for the same inputs. Parsers cache partial results for grammars. Any query cache keyed by parameters is the same idea.