Recursion and the call stack
A function that calls itself on a smaller problem.
It runs on the call stack — a stack you don't manage by hand.
Two mandatory parts
- Base case — the smallest problem, answered outright (stops it)
- Recursive case — shrink to smaller instances, combine
- Miss the base → runs forever. Don't shrink → never reaches it.
- Each call = one frame on the call stack → O(depth) space
Watch Hanoi solve itself
Move n−1 aside · move the big disk · move n−1 back.
Trust the recursion for the smaller problem.
Exponential cost
T(n)=2T(n−1)+1=2n−1
64 disks = 2⁶⁴−1 ≈ 585 billion years. The monks are safe.
Recursion vs iteration
- Recursion has call overhead + a depth limit (Python ~1000)
- Every recursion has an iterative/explicit-stack twin
- Prefer the loop when it's just as clear; recurse for self-similar problems
Takeaway
Solve the smaller problem by trusting the recursion.
It's a stack in disguise. Next: divide-and-conquer sorts.