Pointer Walk

Recursion and Memoization

Naive fib(30) makes 2,692,537 calls, most of them repeats. One cache turns the call tree into a line.

AlgorithmsBeginner10 min read

A function that calls itself

Some problems are easiest to describe in terms of smaller versions of themselves. The Fibonacci numbers are the standard example: each one is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

That description turns directly into code:

python
def fib(n):
    if n < 2:
        return n                      # base case: fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2)    # the answer, in terms of smaller answers

A function that calls itself is recursive. Every recursive function needs two parts:

  • a base case: an input small enough to answer directly, and
  • a recursive case: break the problem into smaller ones and combine their answers.

It is short, it is obviously correct, and it has a serious problem.

Watch the calls pile up

Here is every call made to compute fib(6).

fib(6), the naive wayInteractive
f(6)f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)f(3)f(2)f(1)f(0)f(1)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)
  • the current call
  • repeated work

Start. fib(6) is fib(5) + fib(4), and each of those is two more calls. Watch how many calls that takes.

Calls so far
0

Twenty-five calls for one small number. Look at the pink boxes: fib(4) is computed twice, fib(3) three times, fib(2) five times. Each time, the function starts from nothing, because it has no memory of having done it before.

The tree roughly doubles in size each time n goes up by one or two.

nCalls made by naive fib(n)
625
10177
2021,891
302,692,537
40331,160,281
5040,730,022,147

fib(50) is a number with 11 digits, and getting it this way takes over 40 billion calls. Almost all of them recompute an answer that was already known.

Memoization: remember what you computed

The fix is as simple as the problem. The first time you compute an answer, write it down. The next time you are asked, look it up. This is called memoization.

python
memory = {}

def fib(n):
    if n in memory:
        return memory[n]              # seen before: answer at once
    if n < 2:
        return n
    result = fib(n - 1) + fib(n - 2)
    memory[n] = result                # remember it for next time
    return result
fib(6) with a memoryInteractive
f(6)f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(3)f(4)
  • the current call
  • answered from memory

Start. fib(6) is fib(5) + fib(4), and each of those is two more calls. Watch how many calls that takes.

Calls so far
0

The tree has collapsed into a single line down the left. Every green box is an answer that came from memory, and the whole branch that used to hang below it is gone.

With memoization, fib(50) computes each value from fib(0) to fib(50) exactly once: 51 values, instead of 40 billion calls.

In Python the whole thing is one line above the original function:

python
from functools import lru_cache

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

The function body is untouched. The decorator keeps a table of past inputs and their answers.

Compare them

fib(6), the naive wayInteractive
Version
f(6)f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)f(3)f(2)f(1)f(0)f(1)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)
  • the current call
  • repeated work

Start. fib(6) is fib(5) + fib(4), and each of those is two more calls. Watch how many calls that takes.

Calls so far
0

When memoization works

It needs two things to be true.

  1. The same sub-problems come up again and again

    If every call has a different input, there is nothing to reuse.

  2. The same input always gives the same answer

    The function must depend only on its arguments, not on the time, a file, or anything else that can change.

When both hold, an exponential amount of work often becomes linear. This is the idea behind dynamic programming: solve each sub-problem once and build larger answers from stored smaller ones.

Key takeaways

  • A recursive function solves a problem by calling itself on smaller versions, down to a base case.
  • Naive recursion can recompute the same answers a huge number of times: 2,692,537 calls for fib(30).
  • Memoization stores each answer the first time and looks it up afterwards.
  • It turns the call tree into a line: fib(50) needs 51 values, not 40 billion calls.
  • It works when sub-problems repeat and the function's answer depends only on its input.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress