🔁 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:

1. Base case — the smallest input, solved directly; stops the recursion.
2. Recursive case — reduces the problem toward the base case.
3. 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

Problem	Difficulty	Solution
LC 231 — Power of Two	Easy
LC 110 — Balanced Binary Tree	Easy
LC 24 — Swap Nodes in Pairs	Medium
LC 344 — Reverse String	Easy
LC 509 — Fibonacci Number	Easy
LC 326 — Power of Three	Easy
LC 779 — K-th Symbol in Grammar	Medium
LC 95 — Unique Binary Search Trees II	Medium
LC 894 — All Possible Full Binary Trees	Medium
CC — Recamán Sequence (RECAMAN)	Easy
LC 241 — Different Ways to Add Parentheses	Medium
LC 21 — Merge Two Sorted Lists	Easy
LC 50 — Pow(x, n)	Medium
LC 70 — Climbing Stairs	Easy
LC 104 — Maximum Depth of Binary Tree	Easy
LC 111 — Minimum Depth of Binary Tree	Easy
LC 206 — Reverse Linked List	Easy
LC 226 — Invert Binary Tree	Easy
LC 234 — Palindrome Linked List	Easy
LC 342 — Power of Four	Easy
LC 372 — Super Pow	Medium
LC 390 — Elimination Game	Medium
LC 486 — Predict the Winner	Medium
LC 687 — Longest Univalue Path	Medium
LC 698 — Partition to K Equal Sum Subsets	Medium
LC 700 — Search in a Binary Search Tree	Easy
LC 701 — Insert into a Binary Search Tree	Medium
LC 1137 — N-th Tribonacci Number	Easy
LC 1342 — Number of Steps to Reduce to Zero	Easy
LC 1545 — Find Kth Bit in Nth Binary String	Medium
CC — Factorial (FACT)	Easy
CC — Tower of Hanoi (HANOI)	Medium
CC — Recursive Function (RECFUNC)	Easy

---

Related Topics

• Backtracking — recursion with undo
• Dynamic Programming — memoised recursion
• Trees — most tree algorithms are recursive

← Back to Home · © sparshjaswal