🔁 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

Every recursive function needs:

1. Base case — 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.

---

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

---

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