Many calls at once: Fibonacci

Every function so far called itself once, so its recursion tree was a straight line. Fibonacci calls itself twice.

The code is three lines long. Yet fib(40) makes more than 330 million calls. This lesson draws the tree, counts it, and shows the fix you will use all through dynamic programming.

Read the problem

Ask these before you code:

• Does the count start at 0 or 1? Here fib(0) = 0 and fib(1) = 1. Getting this wrong shifts every answer by one place.
• Why two base cases? Each call reaches back two places, so both 0 and 1 need a direct answer.
• How big can the answer get? fib(30) is 832,040, so a plain integer is fine in every language. For bigger n, each language stops at a different place:
  • Java: an int holds up to fib(46), a long up to fib(92).
  • Python: integers never overflow.
  • TypeScript: numbers stay exact up to fib(78). Past that, use BigInt.

n ≤ 30 is small: the card says even O(n³) fits. So a slow answer may pass here. Keep that in mind, because the trouble starts when n grows.

Brute force: copy the definition

The definition turns straight into code:

JavaPythonTypeScript

int fib(int n) {
    if (n <= 1) return n; // fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2); // two calls
}

• n <= 1 covers both base cases, because fib(0) is 0 and fib(1) is 1.
• The last line makes two recursive calls. That one change turns the straight line into a tree.

The recursion tree

Here is every call that fib(5) makes:

┌────────────────────────────────────────────┐
│                                            │
│                        5                   │
│                ┌───────┴───────┐           │
│                4              [3]          │
│           ┌────┴────┐       ┌──┴──┐        │
│           3        [2]     [2]   [1]       │
│        ┌──┴──┐    ┌─┴─┐   ┌─┴─┐            │
│        2    [1]  [1] [0] [1] [0]           │
│      ┌─┴─┐                                 │
│      1   0                                 │
│                                            │
│       [n] = a repeat: solved before        │
│                                            │
└────────────────────────────────────────────┘

Read it like this:

• Each node is one call. There are 15 of them, for an answer of 5.
• A bracket marks a repeat. Only 6 calls are new: 5, 4, 3, 2, 1 and 0 down the left edge. The other 9 redo work that is already done.
• The left side runs first. All of fib(4) finishes before the right fib(3) starts.
• The stack holds one path at a time. The deepest path is 5, 4, 3, 2, 1, so the stack never holds more than 5 frames. Space is O(n).

Now count the repeats. Inside fib(5):

The right subtree, fib(3), repeats work the left side already did. And each repeat contains smaller repeats.

Count the calls

We added a counter to fib and ran it in all three languages on one laptop. The calls are the same in each. The time is not:

Look down the calls column. Each 10 added to n multiplies the calls by about 123. So the limit in the problem decides whether the brute force is enough:

• n ≤ 30: 2.7 million calls. A few milliseconds in Java and Node, about 60 ms in Python. The brute force passes.
• n around 45: billions of calls and seconds of waiting, more than a minute in Python. Too slow.
• n up to 100,000: you need one of the fixes below, and only the loop survives in all three languages (see the memo's catch).

Python runs the same calls about 20 times slower than Java here. So in Python the brute force stops being enough sooner: fib(35) already takes 0.7 s.

The repeats explode too. Inside fib(40), the call fib(2) runs 63,245,986 times. There are only 41 different answers, fib(0) to fib(40).

Why "about 2ⁿ"

There are two honest answers, and you should know both:

1. The simple bound: O(2ⁿ). Each call makes at most two calls, and the tree has at most n levels. A tree like that has at most 2ⁿ nodes. Interviewers accept this answer.
2. The tight answer: about 1.618ⁿ. The right child is fib(n − 2), one level shorter, so the tree is lopsided. In our runs, each step from n − 1 to n multiplied the calls by 1.618. That number is the golden ratio, and 1.618¹⁰ is about 123.

The exact count is 2 × fib(n + 1) − 1. For n = 40 that is 331,160,281, while 2⁴⁰ is about 1.1 trillion.

So O(2ⁿ) is a safe ceiling, not the real size. Both are exponential: each extra n multiplies the work.

The key insight: never solve the same call twice

The brute force forgets every answer the moment it returns. The fix: write each answer down the first time, and read it back after that.

Think of a times table in school. You work out 7 × 8 once, then you remember 56. You do not count it out again each time.

Better: remember answers in a hash map

This trick is called memoization. A hash map from n to fib(n) is the memory: a HashMap in Java, a dict in Python, a Map in TypeScript.

JavaPythonTypeScript

int fibMemo(int n, Map<Integer, Integer> memo) {
    if (n <= 1) return n;
    Integer saved = memo.get(n);
    if (saved != null) return saved; // solved before: no new calls
    int answer = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, answer); // write it down
    return answer;
}

// call it as fibMemo(n, new HashMap<>())

• memo maps a position to its answer. Every call shares the same map.
• The saved check returns at once for any n solved before.
• The write runs once per n, right after the first time it is solved.

Two language notes:

• In Java, memo.get(n) returns null for a missing key. That is why saved is an Integer, not an int.
• In Python, do not write memo: dict = {} as a default value. Python builds that dict once and shares it with every later call. Pass a new {} instead.

┌────────────────────────────────────────────┐
│                                            │
│                         5                  │
│                     ┌───┴───┐              │
│                     4      (3)             │
│                 ┌───┴───┐                  │
│                 3      (2)                 │
│              ┌──┴──┐                       │
│              2     1                       │
│            ┌─┴─┐                           │
│            1   0                           │
│                                            │
│          (n) = read from the memo          │
│                                            │
└────────────────────────────────────────────┘

The left path solves 4, 3 and 2 for the first time. By the time any right child asks for an answer, the Map already holds it. So each right child is one quick lookup, not a subtree.

Cost. Each position from 2 to n is solved once, with O(1) work, so time is O(n). In our run, n = 40 took 79 calls instead of 331 million. Space is O(n): the Map holds about n answers, and the stack goes n deep.

The catch. The memo removes the repeats, but not the depth. The calls still go n deep, so the stack limits from What is recursion? apply:

• In our runs, fibMemo(100000) overflowed the stack in Java and in Node.
• In Python it fails much sooner. fib_memo(1000, {}) already raises RecursionError, because the default limit is 1,000 frames.

The loop below has no stack, so depth never limits it.

Best: a loop with two variables

Each answer needs only the two before it. So keep two numbers and slide them forward.

• prev holds fib(i − 1).
• curr holds fib(i).

That stays true after every pass of the loop. When i reaches n, curr is the answer.

JavaPythonTypeScript

int fibLoop(int n) {
    if (n <= 1) return n;
    int prev = 0; // fib(0)
    int curr = 1; // fib(1)
    for (int i = 2; i <= n; i++) {
        int next = prev + curr; // slide both one place forward
        prev = curr;
        curr = next;
    }
    return curr;
}

Python and TypeScript move both values in one line. Java needs a third variable, next, so it does not lose the old curr before it adds.

Cost. The loop runs n − 1 times, so time is O(n): 39 passes for n = 40. It keeps two numbers and has no stack, so extra space is O(1).

Side by side

All three fit n ≤ 30. Only the last two survive when n grows, and only the loop needs no extra memory.

How to spot this pattern

These three steps are the whole recipe of dynamic programming:

1. Write the recursion. Find the base cases and the calls.
2. Add a memo. Same arguments, saved answer.
3. Turn it into a loop. Fill answers from small to large, and keep only what the next step needs.

Two problems you will meet in the dynamic programming chapter grow the same tree:

• Climbing Stairs: the ways to reach step n are the ways to reach n − 1 plus the ways to reach n − 2. It is Fibonacci with new words.
• Frog Jump: the cheapest way to reach stone n comes from stone n − 1 or n − 2. Same two calls, with a minimum in place of a sum.

take U forwardYouTube

Read more

• Fibonacci sequence on Wikipedia, with its link to the golden ratio
• Memoization on Wikipedia, the idea and where the name comes from
• useMemo in the React docs, memoization in a real library

Next: selection, bubble and insertion sort, three simple ways to put an array in order.