Recursion: why fib(30) makes 2.7 million calls, and how a notebook fixes it

Here is a trick that surprises many beginners: a function is allowed to call itself. This is called recursion. It sounds like a loop that never ends, but it works as long as each call gets a slightly smaller problem and there is a point where the calls stop.

Two ingredients

Every recursive function has two parts. The base case is the situation so small that the answer is known right away. The recursive case solves a slightly smaller version of the same problem by calling the function again, then uses that answer. Here is the factorial of a number (5! means 5 × 4 × 3 × 2 × 1):

def fact(n):
    if n == 0:          # base case: stop here
        return 1
    return n * fact(n - 1)   # recursive case: a smaller problem

print(fact(5))   # 120

When you call fact(5), it needs fact(4), which needs fact(3), and so on down to fact(0), which simply returns 1. Then each waiting call finishes in turn: 1, then 1 × 1, 2 × 1, 3 × 2, 4 × 6, and finally 5 × 24 = 120. Python keeps track of the waiting calls on the call stack, a pile where each unfinished call sits until the call above it is done.

What happens without a base case

If the calls never reach the base case, the pile grows and grows. Python protects you by stopping at a limit (1000 calls deep by default in standard Python):

def forever(n):
    return forever(n + 1)

forever(0)
# RecursionError: maximum recursion depth exceeded

So the first question to ask about any recursive function is: does every path end at the base case?

When a function calls itself twice

Factorial calls itself once, so its calls form a single chain. Now take the Fibonacci numbers, where each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13... The definition is already recursive: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 as base cases.

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6), calls)   # 8 25

Computing fib(6) gave the right answer, 8, but it took 25 calls for such a small number. Because each call makes two more calls, the calls branch into a tree. Try it yourself below. Press Step to watch the calls happen in order, one at a time. The filled circle is the call running right now.

Look at the tree with n = 5. The value fib(3) is worked out twice, from scratch, and fib(2) three times. The function has no memory, so it repeats work it has already done. Move the slider up and the tree grows fast: with n = 30 the real count is 2,692,537 calls for an answer that has only 31 different questions in it.

Fix: write answers down

The cure is simple. Keep a notebook, which in Python is a dictionary, and write each answer in it. Before doing any work, look in the notebook first. This idea is called memoization (from "memo", a note to remember).

memo = {}
calls = 0
def fib(n):
    global calls
    calls += 1
    if n in memo:         # already solved? use the note
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(6), calls)   # 8 11

Now click Remember answers in the figure above and step through again. The repeated branches shrink to a single dashed circle, because the answer is already written down. I ran this code for a few sizes and counted the calls:

n	Without notebook	With notebook
10	177	19
20	21,891	39
30	2,692,537	59

Without the notebook, the work roughly multiplies by 1.6 each time n goes up by one. With it, the work grows by two calls per step. Same answer, wildly different cost.

What to take into your own code

When you write a recursive function, check three things: a base case exists, each call moves toward it, and the same smaller problem is not being solved again and again. If it is, a dictionary of past answers is often all you need. Python also ships a ready-made notebook: put @functools.cache above a function and it remembers results for you.

Recursion is not always the best tool. A plain loop is fine for simple counting, and very deep recursion can hit the limit. But for problems that split into smaller copies of themselves, such as folders inside folders or branching choices, it is often the clearest way to say what you mean.