Recursive Thinking & Recursion Trees

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~25 minutes

From a Chain to a Tree
Drawing the Fibonacci Recursion Tree
Spotting Overlapping Subproblems
A Preview: Fixing the Waste
Converting Simple Recursion to Iteration
Summary & Next Steps

1. From a Chain to a Tree

factorial(n) (Chapter 1) makes exactly one recursive call per level — its call stack is a straight chain. Many recursive problems instead make multiple recursive calls per level, branching outward into a tree shape rather than a line. Naive Fibonacci, first mentioned in Module 1 Chapter 2, is the textbook example:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)     # TWO recursive calls, not one

2. Drawing the Fibonacci Recursion Tree

Tracing fib(4) by hand reveals the branching:

                        fib(4)
                       /      \
                 fib(3)        fib(2)
                /     \        /     \
          fib(2)     fib(1) fib(1)  fib(0)
          /    \
     fib(1)   fib(0)

Every node is a call; every call that isn't fib(0) or fib(1) branches into two more. Count the nodes and you'll see why Module 1 called naive Fibonacci O(2ⁿ) — the tree's size roughly doubles with every increase in n.

3. Spotting Overlapping Subproblems

Look closely at the tree above: fib(2) appears twice, and fib(1) appears three times. Each occurrence redoes the exact same work from scratch — fib(2)'s entire subtree gets recomputed both times it's needed, even though the answer is identical both times.

This is called an overlapping subproblem, and it's the specific reason naive recursive Fibonacci is so slow: the tree isn't wasteful because the idea is bad, it's wasteful because identical work is repeated many times over.

# How many times is fib(2) actually computed while running fib(6)?
# Draw the tree yourself and count — the answer grows fast as n increases.

Contrast this with factorial(n) from Chapter 1: its call chain has no branching, so there's nothing to overlap — every call is unique. Overlapping subproblems only show up once a function branches into more than one recursive call per level.

4. A Preview: Fixing the Waste

If the same subproblem is being solved repeatedly, an obvious fix is: solve it once, remember the answer, and reuse it instead of recomputing.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]           # already solved — reuse it
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
    # Each fib(k) is now computed once, not repeatedly → O(n) time

This technique — caching recursive results so overlapping subproblems are only solved once — is called memoization, and it's the entire subject of Module 10 (Dynamic Programming). You don't need to master it here; just recognize the shape: recursion + overlapping subproblems is the signal that memoization applies.

5. Converting Simple Recursion to Iteration

Not every recursive function needs to stay recursive. When a recursive function only ever makes one recursive call, and that call is the very last thing it does (a "tail call"), it can usually be rewritten as a simple loop — trading the O(n) stack space from Chapter 1 for O(1) space, since Python does not optimize tail calls automatically the way some other languages do.

# Recursive (chain-shaped, like factorial) — O(n) space
def sum_to_n_recursive(n):
    if n == 0:
        return 0
    return n + sum_to_n_recursive(n - 1)
 
# Iterative — same O(n) time, but O(1) space
def sum_to_n_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Tree-shaped recursion (like fib) is harder to convert directly to a simple loop — that's exactly why techniques like memoization (Module 10) matter more there than a naive loop rewrite would.

6. Summary & Next Steps

Key Takeaways

Some recursive functions call themselves once per level (a chain, like factorial); others call themselves multiple times per level (a tree, like fib).
Tree-shaped recursion can suffer from overlapping subproblems — the same subproblem solved repeatedly from scratch — which is exactly why naive Fibonacci is O(2ⁿ).
Memoization (caching results of subproblems) fixes overlapping subproblems and is the foundation of Module 10's Dynamic Programming.
Simple chain-shaped recursion can often be rewritten as an iterative loop to save stack space; tree-shaped recursion usually needs memoization instead.

Concept Check

Why does factorial(n) have no overlapping subproblems, while fib(n) does?
In the fib(4) tree, which subproblem appears the most times?
What's the difference between "converting recursion to iteration" and "memoizing a recursive function" — when would you reach for each?

Next Chapter

→ Chapter 3: Classic Recursion Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index