Recursion
One-line summary: Solve a problem by breaking it into smaller instances of itself — the foundation of DFS, divide-and-conquer, backtracking, and tree algorithms.
Diagram
🎯 Concept
Recursion is when a function calls itself to solve smaller instances of the same problem. Every recursive function needs:
- Base case — the smallest input, solved directly; stops the recursion.
- Recursive case — reduces the problem toward the base case.
- Trust the recursion — assume the recursive call returns the correct answer (the "recursive leap of faith").
The Call Stack
Each recursive call is pushed onto the call stack with its own local variables. When the base case returns, the frames unwind in reverse (LIFO) order.
flowchart TD
A["fact(4)"] --> B["4 * fact(3)"]
B --> C["3 * fact(2)"]
C --> D["2 * fact(1)"]
D --> E["fact(1) = 1 (base case)"]
E -.returns 1.-> D
D -.returns 2.-> C
C -.returns 6.-> B
B -.returns 24.-> A
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Elegant for trees/divide-and-conquer | Simpler for linear loops |
| Memory | O(depth) stack frames | O(1) usually |
| Risk | Stack overflow on deep recursion | None |
| Conversion | Any recursion → loop + explicit stack | — |
Memoization (Intro)
When recursive calls repeat the same subproblem, cache results to avoid recomputation — turning exponential time into linear. This is the bridge to Dynamic Programming.
⚡ Time & Space Complexity
| Recursive Pattern | Time | Space (stack) |
|---|---|---|
| Linear (factorial) | O(n) | O(n) |
| Binary (naive Fibonacci) | O(2ⁿ) | O(n) |
| Binary (memoized Fibonacci) | O(n) | O(n) |
| Divide & conquer (merge sort) | O(n log n) | O(log n) |
| Fast exponentiation | O(log n) | O(log n) |
Key Insight: Recursion depth determines auxiliary space — always bound the depth to avoid stack overflow.
Common Patterns
Factorial
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
Fibonacci (memoised)
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return (memo[n] = fib(n - 1, memo) + fib(n - 2, memo));
}
Power (fast exponentiation)
function power(base, exp) {
if (exp === 0) return 1;
if (exp % 2 === 0) {
const half = power(base, exp / 2);
return half * half;
}
return base * power(base, exp - 1);
}
Pitfalls
- Missing base case → infinite recursion / stack overflow
- Redundant subproblem calls → add memoisation
- Deep recursion in JS → stack size ~10k; consider iterative with explicit stack
🧪 Worked Example: Naive vs Memoized Fibonacci
The classic demonstration of why memoization matters.
// ❌ Naive: recomputes the same subproblems exponentially
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Time: O(2^n) — fib(40) makes ~1.6 billion calls!
// ✅ Memoized: each subproblem solved once
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
// Time: O(n), Space: O(n)
Takeaway: The recursion tree for fibNaive(5) computes fib(2) three times and fib(1) five times. Memoization prunes those repeats — the same idea that powers Dynamic Programming.
Practice Problems
Related Topics
- Backtracking — recursion with undo
- Dynamic Programming — memoised recursion
- Trees — most tree algorithms are recursive
← Back to Home · © sparshjaswal