Solvequill Blog · coding · 3 min read · 18 views

Naive fib(30) makes 2.7 million calls. Memoised, it makes 61.

Memoisation is not a speed trick bolted on afterwards. Counting the calls shows exactly which work it removes and why the shape of the recursion changes.

Published: August 25, 2026

Loading the lesson…

The Solvequill lesson for this question.

The question

The naive recursive Fibonacci makes an enormous number of calls. Count exactly how many calls fib(n) makes, explain why memoisation reduces it to about 2n, and state the resulting complexity.

The left column multiplies by about 123 each time; the right adds 20.

What to notice first

Draw the call tree for fib(5) and the problem is visible immediately: fib(3) is computed twice, fib(2) three times, fib(1) five times. The recursion re-derives answers it already found, and the duplication compounds at every level.

Working it through

The naive version. Correct, and unusable past about $n = 40$ :

Python

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

Count the calls. Let C(n) be the total number of invocations. It satisfies its own recurrence, and solving it gives a closed form in terms of Fibonacci numbers themselves:

C (n) = 2 F (n + 1) - 1

For $n = 30, F (31) = 1346269$ so:

C (30) = 2 (1346269) - 1 = 2692537

Since F(n) grows like $φ^{n}$ , the call count grows exponentially — that is the real complexity, not O( $n^{2}$ ) as the two recursive calls might suggest:

C (n) = O (φ^{n}), φ \approx 1.618

Memoisation stores each result the first time it is computed, so every distinct argument is evaluated once:

Python

1def fib_memo(n, cache=None):2    if cache is None:3        cache = {}4    if n < 2:5        return n6    if n in cache:7        return cache[n]8    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)9    return cache[n]

There are only n distinct arguments, and each is computed once and then returned from the cache thereafter — about 2n+1 calls in total:

O (φ^{n}) ⟶ O (n)

The answer

C (30) = 2692537 ⟶ 61 calls

The cache holds n entries, so this buys O(n) time with O(n) space. An iterative version does the same in O(1) space by keeping only the last two values — memoisation is the general tool, not always the best one.

The mistake this one catches

Prefer to watch it? The lesson above walks through every line.

Turn your own question into an explanation video

Type the question or upload a photo; Solvequill produces a narrated video that walks through the solution step by step.

Open Solvequill