Recursion Tree and Call Stack
When a recursive function runs, it creates a tree-shaped structure of calls. Drawing this recursion tree is the single most powerful technique for understanding what a recursive algorithm does and why it has a certain time complexity. The call stack is the runtime implementation of this tree, storing each active call frame in memory.
The Call Stack — Memory Layout
Every time a function is called, the CPU pushes a stack frame onto the call stack. A stack frame contains:
The function arguments for that call
Local variables
A return address (where to resume when this call finishes)
The return value slot
When a function returns, its frame is popped off the stack and the previous frame resumes from where it left off. This is why recursion "unwinds" — it returns through each frame in reverse order.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
factorial(4)
# Call stack evolution:
#
# [1] factorial(4) called
# Stack: | factorial(4): n=4, waiting for factorial(3) |
#
# [2] factorial(3) called
# Stack: | factorial(3): n=3, waiting for factorial(2) |
# | factorial(4): n=4, waiting for factorial(3) |
#
# [3] factorial(2) called
# Stack: | factorial(2): n=2, waiting for factorial(1) |
# | factorial(3): n=3, waiting for factorial(2) |
# | factorial(4): n=4, waiting for factorial(3) |
#
# [4] factorial(1) called
# Stack: | factorial(1): n=1, waiting for factorial(0) |
# | factorial(2): n=2, waiting for factorial(1) |
# | factorial(3): n=3, waiting for factorial(2) |
# | factorial(4): n=4, waiting for factorial(3) |
#
# [5] factorial(0) called → returns 1 immediately
# Stack unwinds:
# factorial(1) resumes → returns 1 * 1 = 1
# factorial(2) resumes → returns 2 * 1 = 2
# factorial(3) resumes → returns 3 * 2 = 6
# factorial(4) resumes → returns 4 * 6 = 24Stack Overflow
import sys
print(sys.getrecursionlimit()) # 1000 by default in CPython
# This will crash with RecursionError:
def infinite(n):
return infinite(n + 1) # never reaches a base case
# This crashes for large n:
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
# sum_to(5000) → RecursionError on default Python settingsDrawing a Recursion Tree
A recursion tree visualizes every call as a node. The root is the original call. Each child represents a recursive call made from the parent. Leaves are base cases. Rules for drawing:
Start with the original call as the root node
For each recursive call made, draw a child node
Label each node with its arguments
Mark base cases (leaves) specially
Annotate each node with the work done at that level (excluding recursive calls)
Fibonacci Recursion Tree
The naive Fibonacci function makes this structure painfully visible:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Recursion tree for fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Nodes: fib(0) called 3 times
fib(1) called 5 times
fib(2) called 3 times
fib(3) called 2 times
fib(4) called 1 time
fib(5) called 1 time
Total calls: ~2^5 = 32 (actually 15 for n=5)
For fib(50): ~2^50 ≈ 1 quadrillion calls!Using the Tree to Compute Complexity
To find time complexity from a recursion tree: 1. Find the height of the tree (depth of recursion) 2. Count nodes at each level 3. Determine work per node (excluding recursive calls) 4. Multiply nodes × work per level, then sum across all levels
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # left half
right = merge_sort(arr[mid:]) # right half
return merge(left, right) # merge: O(n)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]Recursion tree for merge_sort([1,2,3,4,5,6,7,8]) — n=8:
Level 0: [1,2,3,4,5,6,7,8] 1 node, n=8 → work: O(8)
/ \
Level 1: [1,2,3,4] [5,6,7,8] 2 nodes, n=4 → work: O(4)+O(4) = O(8)
/ \ / \
Level 2: [1,2][3,4] [5,6][7,8] 4 nodes, n=2 → work: O(2)×4 = O(8)
/\ /\ /\ /\
Level 3: [1][2][3][4][5][6][7][8] 8 nodes, n=1 → work: O(1)×8 = O(8)
Height of tree: log₂(n) = log₂(8) = 3 levels
Work per level: O(n) (always 8 units total across all nodes at that level)
Total levels: log₂(n) + 1
Total work = O(n) × O(log n) = O(n log n) ✓General Template for Tree Analysis
Recursion shape | Recurrence | Tree height | Nodes per level | Total work |
|---|---|---|---|---|
T(n) = T(n-1) + O(1) | Decrease by 1 | n | 1 per level | O(n) |
T(n) = T(n/2) + O(1) | Halve | log n | 1 per level | O(log n) |
T(n) = 2T(n-1) + O(1) | Decrease by 1, 2 branches | n | 2ⁱ at level i | O(2ⁿ) |
T(n) = 2T(n/2) + O(n) | Halve, 2 branches | log n | 2ⁱ nodes × n/2ⁱ work | O(n log n) |
T(n) = T(n/2) + O(n) | Halve, 1 branch | log n | n + n/2 + ... + 1 | O(n) |
The Master Theorem
For divide-and-conquer recurrences of the form:
**T(n) = a · T(n/b) + f(n)**
where a ≥ 1 (number of subproblems), b > 1 (factor by which input shrinks),
and f(n) is the work done outside recursive calls, the Master Theorem gives
a direct answer.
Case | Condition | Result | Intuition |
|---|---|---|---|
Case 1 | f(n) = O(n^(log_b(a) - ε)) | T(n) = Θ(n^log_b(a)) | Recursive calls dominate |
Case 2 | f(n) = Θ(n^log_b(a)) | T(n) = Θ(n^log_b(a) · log n) | Equal contribution at each level |
Case 3 | f(n) = Ω(n^(log_b(a) + ε)) | T(n) = Θ(f(n)) | Non-recursive work dominates |
# Master Theorem examples: # Binary search: T(n) = T(n/2) + O(1) # a=1, b=2, f(n)=O(1) # log_b(a) = log_2(1) = 0 # f(n) = O(1) = O(n^0) → Case 2 (f matches n^0) # T(n) = Θ(log n) ✓ # Merge sort: T(n) = 2T(n/2) + O(n) # a=2, b=2, f(n)=O(n) # log_b(a) = log_2(2) = 1 # f(n) = O(n) = O(n^1) → Case 2 (f matches n^1) # T(n) = Θ(n log n) ✓ # Karatsuba multiplication: T(n) = 3T(n/2) + O(n) # a=3, b=2, f(n)=O(n) # log_b(a) = log_2(3) ≈ 1.585 # f(n) = O(n) = O(n^1) < O(n^1.585) → Case 1 # T(n) = Θ(n^1.585) ✓ (beats naive O(n²))
Worked Example: Counting Recursion Tree Nodes
# How many calls does fib(n) make?
call_count = 0
def fib_counted(n):
global call_count
call_count += 1
if n <= 1:
return n
return fib_counted(n - 1) + fib_counted(n - 2)
for n in range(10):
call_count = 0
fib_counted(n)
print(f"fib({n}): {call_count} calls")fib(0): 1 calls fib(1): 1 calls fib(2): 3 calls fib(3): 5 calls fib(4): 9 calls fib(5): 15 calls fib(6): 25 calls fib(7): 41 calls fib(8): 67 calls fib(9): 109 calls
The call count follows: calls(n) = calls(n-1) + calls(n-2) + 1. This grows as Θ(2ⁿ), confirming the tree analysis.
Memoization Collapses the Tree
When you add memoization (caching previously computed results), the recursion tree becomes a DAG (directed acyclic graph) — repeated subtrees are visited only once. The tree structure collapses dramatically.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# fib_memo(5) call tree with memoization:
#
# fib(5)
# fib(4)
# fib(3)
# fib(2)
# fib(1) → 1 (cached)
# fib(0) → 0 (cached)
# fib(1) → 1 (CACHED — no tree below)
# fib(2) → 1 (CACHED — no tree below)
# fib(3) → 2 (CACHED — no tree below)
#
# Total unique calls: n+1 = 6 for fib(5)
# Each call: O(1) work
# Total: O(n) vs. O(2ⁿ) without memoizationStack Depth and Space Complexity
The maximum stack depth equals the height of the recursion tree. This is also the space complexity from the call stack (ignoring other allocations).
Algorithm | Max stack depth | Space from stack |
|---|---|---|
factorial(n) | n frames | O(n) |
binary_search(n) | log n frames | O(log n) |
fib(n) naive | n frames (leftmost path) | O(n) |
merge_sort(n) | log n frames | O(log n) |
DFS on a graph with n nodes | n frames worst case | O(n) |
Visualizing DFS as a Recursion Tree
# Depth-First Search — recursion tree mirrors the graph structure
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': [],
}
def dfs(node, visited=None, depth=0):
if visited is None:
visited = set()
visited.add(node)
print(" " * depth + node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, visited, depth + 1)
dfs('A')A
B
D
E
C
F
Recursion tree:
A (depth 0)
/ \
B C (depth 1)
/ \ \
D E F (depth 2)
Stack at deepest point (reaching D):
| dfs(D) |
| dfs(B) |
| dfs(A) |Interview Tips
When asked "what is the time complexity?" — draw the tree first, then count nodes and work per node
For any T(n) = aT(n/b) + f(n) recurrence, try the Master Theorem first
If Master Theorem does not apply, draw the tree and sum the work level by level
Remember: stack space = tree height = O(log n) for halving, O(n) for decrementing
Memoization converts exponential tree to linear by caching repeated subtrees