Recursion

Med

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 Stack (1)
factorial(4)
active
factorial(4) is called. Stack grows.
1 / 8
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

Functions

Declarations, expressions, and arrows

Closures

Functions that remember their scope

Memory Model

Stack vs Heap and garbage collection

Event Loop

How async JavaScript works