Recursion hides complexity. You can't just count the for loops — you have to reason about the call tree.
Time Complexity: $O(\text{branches}^{\text{depth}})$
Draw the recursion tree. Count the branches at each node and the depth of the tree.
Example — Naive Fibonacci:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # 2 branches per call
Each call spawns 2 more calls. The tree has depth N. Total calls ≈ $2^N$. Time complexity: $O(2^N)$.
Example — Binary Search (recursive):
def binary_search(arr, lo, hi, target):
if lo > hi:
return -1
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, mid + 1, hi, target) # 1 branch
else:
return binary_search(arr, lo, mid - 1, target) # 1 branch
Each call spawns 1 more call, and the problem halves each time. Depth = $\log N$. Time complexity: $O(\log N)$.
Space Complexity: $O(\text{depth})$
Space is determined by the maximum height of the call stack — how many function frames are open simultaneously at the deepest point of recursion.
Even if Fibonacci takes $O(2^N)$ time, the call stack only goes N levels deep at any one moment (it explores one branch fully before backtracking). Space complexity: $O(N)$.
The plate stack analogy: Recursion adds a plate to the stack on each call and removes a plate on each return. Space complexity is the maximum height the stack ever reaches — not the total number of plates ever used.
fib(5)
fib(4)
fib(3)
fib(2)
fib(1) ← deepest point: 5 frames on stack simultaneously