Recursion Tree Visualization

Every Recursive Call Is a Node

You've been working with trees as data structures — nodes with children, stored in memory. But there's another kind of tree that shows up everywhere in algorithm analysis: the recursion tree.

Every time a function calls itself, that call is a node. Its recursive subcalls are its children. The entire execution of a recursive function IS a tree.

This isn't a metaphor. It's literal. And once you learn to draw it, you can see why some algorithms are fast and others are catastrophically slow.

---

Draw the Tree for fib(6)

The naive Fibonacci function:

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Every call to fibonacci(n) makes two subcalls: fibonacci(n-1) and fibonacci(n-2). That's a binary tree.

                          fib(6)
                        /        \
                   fib(5)          fib(4)
                  /      \        /      \
             fib(4)    fib(3)  fib(3)   fib(2)
            /    \     /   \    /   \    /   \
        fib(3) fib(2) f(2) f(1) f(2) f(1) f(1) f(0)
        /   \   / \   / \
     f(2) f(1) f(1) f(0) f(1) f(0)
     / \
   f(1) f(0)

Count the nodes: 25 function calls to compute fib(6) = 8.

Look at the tree carefully. fib(4) appears twice. fib(3) appears three times. fib(2) appears five times. The tree is full of identical subtrees — the same computation repeated over and over.

Redundant computation = identical subtrees in the recursion tree. If you see the same subtree appearing multiple times, the algorithm is doing unnecessary work.

---

The Numbers Tell the Story

\(n\)	fib(\(n\))	Number of calls
1	1	1
2	1	3
3	2	5
4	3	9
5	5	15
6	8	25
10	55	177
20	6765	21,891
40	102334155	~331 million

The number of calls grows exponentially — roughly \(O(2^n)\). More precisely, it's \(O(\phi^n)\) where \(\phi \approx 1.618\) is the golden ratio. For \(n = 40\), you're making over 300 million calls to compute a number that fits in a 32-bit integer.

---

Memoization: Collapsing the Tree

What if, the first time you compute fib(4), you store the result? The second time someone asks for fib(4), you return the stored value immediately — no subtree, no recursion.

int fibonacciMemo(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

The recursion tree with memoization:

    fib(6)
    /    \
  fib(5)  fib(4) ← cached, returns immediately
  /    \
fib(4)  fib(3) ← cached
/    \
fib(3) fib(2) ← cached
/    \
fib(2) fib(1) ← base case
/    \
fib(1) fib(0) ← base cases

The right child of almost every node is a cache hit — a single lookup, not a subtree. The tree has collapsed into essentially a chain: fib(6) → fib(5) → fib(4) → fib(3) → fib(2) → fib(1).

Only 7 unique subproblems are solved: fib(0) through fib(6). Everything else is a cache lookup. From 25 calls down to 11 (7 real computations + 4 cache hits).

Step	Call	Computed or Cached?	Result
1	fib(6)	Compute	—
2	fib(5)	Compute	—
3	fib(4)	Compute	—
4	fib(3)	Compute	—
5	fib(2)	Compute	—
6	fib(1)	Base case	1
7	fib(0)	Base case	0
8	fib(2) returns	—	1
9	fib(1)	Cached	1
10	fib(3) returns	—	2
11	fib(2)	Cached	1
12	fib(4) returns	—	3
13	fib(3)	Cached	2
14	fib(5) returns	—	5
15	fib(4)	Cached	3
16	fib(6) returns	—	8

---

The Visual Insight

Here's what to take away from this:

The DP table is the collapsed tree laid flat. Each cell in the table corresponds to a unique node in the recursion tree. Memoization eliminates the duplicate subtrees. Bottom-up DP eliminates the tree entirely and fills the table in order.

The fib DP table: [0, 1, 1, 2, 3, 5, 8]. Seven entries — one per unique subproblem. The recursion tree had 25 nodes, but only 7 were unique. The table keeps only the unique ones.

This is why drawing the recursion tree is the first step when analyzing any recursive algorithm. The tree shows you:

1. How many total calls — the tree size gives the time complexity of the naive version.
2. How many unique calls — the number of distinct subproblems gives the time complexity after memoization.
3. Which calls are redundant — identical subtrees are the targets for memoization.

We show you the visualization here. The DP course will teach you how to systematically identify subproblems, define recurrences, and fill tables bottom-up. The tree is the lens — the optimization technique comes later.

---

---

Try It

The starter code has both fibonacci and fibonacciMemo. Run both for \(n = 6\) and verify they return the same value.

Predict before running: How many times does the naive fibonacci call fibonacci(2)? Draw the tree and count. (Answer: 5 times.)

Challenge: Add a global counter to fibonacci and fibonacciMemo to count total function calls. Compare the counts for \(n = 20\). The naive version should make about 21,891 calls. The memoized version should make about 37.

Challenge 2: Can you draw the recursion tree for fibonacci(7) by extending the fib(6) tree? How many nodes does it have? (Hint: fib(7) calls fib(6) and fib(5). You already know the subtree for fib(6) has 25 nodes and fib(5) has 15.)

Edge Cases to Watch For

• Memo array too small: If the memo vector has size \(n\) but indices go up to \(n\), you get an out-of-bounds access. Initialize with size \(n + 1\).
• Negative \(n\): The base case n <= 1 catches \(n = 0\) and \(n = 1\), but negative \(n\) would cause infinite recursion. Add a guard if (n < 0) return 0 or document the precondition.
• Integer overflow: fib(46) exceeds INT_MAX (\(2^{31} - 1\)). For large \(n\), use long long. fib(93) exceeds LLONG_MAX.

Problems

Problem	Link	Difficulty
LC 509 — Fibonacci Number	leetcode.com/problems/fibonacci-number	Easy
LC 70 — Climbing Stairs	leetcode.com/problems/climbing-stairs	Easy