Chapter 05 — Recursion & the Call Stack
Chapter 05 — Recursion & the Call Stack
Hey everyone! Welcome back to Namaste DSA!
Recursion scares a lot of people — but it's just a function that calls itself to solve a smaller version of the same problem. Once you can draw the call stack and the recursion tree, recursion stops being magic. And you'll need it for trees, graphs, backtracking, and DP — so let's nail it now.
What we will cover:
- Base case + recursive case — the two rules
- The call stack drawn step by step
- The recursion tree
- Factorial, sum, Fibonacci
- Why naive Fibonacci is O(2ⁿ)
- Recursion vs iteration
- Stack overflow & recursion's hidden space cost
- Interview Questions
1. The Two Rules of Recursion
┌─────────────────────────────────────────────────────────────┐ │ EVERY RECURSION NEEDS: │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 1. BASE CASE — when to STOP (no more recursion) │ │ 2. RECURSIVE CASE — call itself on a SMALLER problem │ │ │ │ Miss the base case → infinite recursion → stack overflow! │ │ │ └─────────────────────────────────────────────────────────────┘
function factorial(n) {
if (n <= 1) return 1; // BASE CASE
return n * factorial(n - 1); // RECURSIVE CASE (smaller n)
}
2. The Call Stack — Drawn Step by Step
Each call waits ("pauses") for the call below it to finish. Calls pile up, then unwind.
factorial(4) GOING DOWN (calls pile up): ┌──────────────────────┐ │ factorial(1) = 1 │ ← base case hit, returns 1 │ factorial(2) = 2*? │ │ factorial(3) = 3*? │ │ factorial(4) = 4*? │ ← first call, at the bottom └──────────────────────┘ COMING BACK UP (each resolves): factorial(1) → 1 factorial(2) → 2 * 1 = 2 factorial(3) → 3 * 2 = 6 factorial(4) → 4 * 6 = 24 ✔
3. A Simple One — Sum of an Array
function sum(arr, i = 0) {
if (i === arr.length) return 0; // base case
return arr[i] + sum(arr, i + 1); // current + rest
}
// sum([1,2,3]) = 1 + (2 + (3 + 0)) = 6
4. Fibonacci & the Recursion Tree
Fibonacci: each number is the sum of the previous two. fib(n) = fib(n-1) + fib(n-2).
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
Look at the recursion tree for fib(5) — notice all the repeated work:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ ... ...
fib(2) fib(1)
fib(3) computed TWICE. fib(2) computed THREE times.
The tree roughly DOUBLES each level → O(2ⁿ) calls!
5. Why Naive Fibonacci is O(2ⁿ)
Each call spawns 2 more calls, which each spawn 2 more... The tree has about 2ⁿ nodes. fib(50) would make over a trillion calls. This is the poster child for why we need memoization (Chapter 21) — remembering answers we already computed turns O(2ⁿ) into O(n).
// Memoized — O(n)
function fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n]; // reuse!
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
6. Recursion vs Iteration
| Recursion | Iteration | |
|---|---|---|
| Readability | Cleaner for trees/graphs | Cleaner for simple loops |
| Space | O(depth) — call stack | O(1) usually |
| Risk | Stack overflow if too deep | No stack risk |
Anything recursive can be written iteratively (sometimes with an explicit stack) and vice versa. Choose recursion when the problem is naturally recursive — trees, divide & conquer, backtracking.
7. Stack Overflow & Recursion's Hidden Space Cost
Every pending call sits on the call stack until it returns. So a recursion that goes n deep uses O(n) space even if it allocates nothing visible. Too deep (e.g. recursing 100,000 times) → the stack runs out of room → "Maximum call stack size exceeded".
┌─────────────────────────────────────────────────────────────┐ │ RECURSION SPACE = MAX DEPTH OF THE CALL STACK │ │ │ │ factorial(n) → depth n → O(n) space │ │ binary search → depth log n → O(log n) space │ │ tree DFS → depth = tree height │ └─────────────────────────────────────────────────────────────┘
Interview Questions — Quick Fire!
Q: What are the two essential parts of any recursive function?
"A base case that stops the recursion, and a recursive case that calls the function on a smaller input moving toward the base case. Without a reachable base case you get infinite recursion and a stack overflow."
Q: Why is naive recursive Fibonacci so slow?
"Because it recomputes the same subproblems over and over. fib(n) calls fib(n-1) and fib(n-2), and the call tree roughly doubles at each level, giving O(2ⁿ) calls. Memoizing the results brings it down to O(n)."
Q: Does recursion use extra memory?
"Yes — each pending call occupies a frame on the call stack until it returns, so the space cost is O(maximum recursion depth). For a linear recursion that's O(n); for balanced tree recursion it's O(height). It's a common mistake to call a recursive solution O(1) space."
Q: What causes a stack overflow?
"Recursing too deeply — either a missing or unreachable base case causing infinite recursion, or a legitimately huge depth that exhausts the call stack's fixed size. The fix is to add/fix the base case, or convert to iteration with an explicit stack."
Q: Can every recursion be written iteratively?
"Yes. Any recursion can be simulated with a loop and an explicit stack. Recursion is often more readable for naturally recursive structures like trees, but iteration avoids the call-stack space and overflow risk."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Base case | The stop condition — required. |
| Recursive case | Call self on a smaller input. |
| Call stack | Calls pile up, then unwind. |
| Recursion tree | Visualizes the calls & repeated work. |
| Naive Fib | O(2ⁿ); memoize → O(n). |
| Space cost | O(max depth) — the hidden stack. |
What's Next?
That wraps Season 1 — Foundations! In Chapter 06 we begin Season 2 — Patterns with the Two Pointers technique, which turns many O(n²) brute forces into clean O(n) solutions.
Keep coding, keep grinding! See you in the next one!
Post a Comment