🔁

Recursion

intermediate

Recursion is when a function calls itself to solve smaller instances of the same problem. Every recursive function needs a base case (stopping condition) and a recursive case. Understanding the call stack is key to mastering recursion.

🎮Interactive Visualization

CodeCalling ↓
1function factorial(n) {
2  if (n <= 1) return 1;
3  return n * factorial(n - 1);
4}
5 
6factorial(4);  // 24
Call Stack1 frames
factorial(4)
active
Step 1/8factorial(4) is called. Stack grows.
Key Insight: Recursion = function calling itself. Every recursive function needs a BASE CASE to stop!

Key Points

  • A recursive function calls itself with a smaller/simpler input
  • Every recursion needs a BASE CASE to stop (or you get infinite recursion)
  • The call stack grows with each recursive call, then unwinds as functions return
  • Recursion can be converted to iteration (and vice versa)
  • Memoization can optimize recursive functions with overlapping subproblems

💻Code Examples

Factorial

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Classic recursion: multiply n by factorial of (n-1)

Countdown

function countdown(n) {
  if (n <= 0) return;
  console.log(n);
  countdown(n - 1);
}

Simple recursion with side effects

Fibonacci

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Tree recursion: TWO recursive calls combine results

Climbing Stairs

function climbStairs(n) {
  if (n <= 1) return 1;
  return climbStairs(n - 1)
       + climbStairs(n - 2);
}

Ways to climb: take 1 step OR 2 steps (branching)

Max Tree Depth

function maxDepth(node) {
  if (!node) return 0;
  let left = maxDepth(node.left);
  let right = maxDepth(node.right);
  return Math.max(left, right) + 1;
}

Compare TWO recursive results, take the max

Subsets

function subsets(nums, i = 0, curr = []) {
  if (i === nums.length) {
    return [curr.slice()];
  }
  // Branch 1: exclude nums[i]
  let without = subsets(nums, i + 1, curr);
  // Branch 2: include nums[i]
  curr.push(nums[i]);
  let with_ = subsets(nums, i + 1, curr);
  curr.pop();
  return [...without, ...with_];
}

Include OR exclude each element - exponential branching

Memoization

function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo)
          + fibMemo(n - 2, memo);
  return memo[n];
}

Cache results to avoid recalculating branches

Tree DFS

function dfs(node) {
  if (!node) return;
  console.log(node.val);
  dfs(node.left);   // Branch 1
  dfs(node.right);  // Branch 2
}

Visit node, then recurse on BOTH children

Common Mistakes

  • Forgetting the base case (causes infinite recursion / stack overflow)
  • Base case that is never reached
  • Not reducing the problem size in recursive call
  • Using recursion when simple iteration would be clearer

Interview Tips

  • Always identify the base case first
  • Trace through with a small example on paper
  • Know when to use memoization (overlapping subproblems)
  • Be able to convert between recursion and iteration

🔗Related Concepts

🎒

Closures

Functions that remember their scope

🧠

Memory Model

Stack vs Heap and garbage collection

🔄

Event Loop

How async JavaScript works