Recursion

Explanation

Every recursive function needs two things: a base case (a condition where the function returns without calling itself, stopping the recursion) and a recursive case (where the function calls itself with a simpler or smaller input, moving toward the base case). Without a base case, recursion runs forever until the call stack overflows. Each recursive call creates a new stack frame on the call stack — holding the function's local variables and return address. When the base case is reached, frames resolve one by one as each call returns to its caller. For n = 5 in a factorial function, the stack grows 5 levels deep before returning. For n = 100,000, you get a stack overflow. This is why deeply recursive algorithms often need to be converted to iterative versions for production code. Recursion is natural for problems with self-similar structure: tree traversal (process a node, then recursively process subtrees), file system traversal (process a directory, then recursively process subdirectories), divide-and-conquer algorithms (merge sort, quick sort, binary search), and mathematical sequences (Fibonacci, factorials). The key insight is that a recursive solution directly mirrors the problem's recursive definition. Tail recursion is a special case where the recursive call is the last operation in the function — the current frame's result isn't needed after the recursive call returns. Some language runtimes (Scheme, Haskell, some JS engines) can optimize tail calls to not push new stack frames, making tail recursion as space-efficient as a loop. JavaScript spec supports tail call optimization in strict mode, but few engines implement it.

Code Example

// Recursion fundamentals

// 1. Factorial — classic recursion
function factorial(n) {
  if (n <= 1) return 1;         // base case
  return n * factorial(n - 1); // recursive case
}

// 2. Fibonacci — naive recursion (O(2^n)) vs memoized (O(n))
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2); // exponential!
}

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

// 3. Tree traversal — recursion matches the data structure
function treeSum(node) {
  if (!node) return 0;  // base case: null node contributes 0
  return node.val + treeSum(node.left) + treeSum(node.right);
}

// 4. Converting recursion to iteration (avoid stack overflow)
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

Why It Matters for Engineers

Recursion is the foundation of tree and graph traversal, divide-and-conquer algorithms, dynamic programming, and most of theoretical computer science. Almost every interesting algorithm — DFS, merge sort, binary search — is naturally expressed recursively. If you're fuzzy on recursion mechanics (the call stack, base cases, return values propagating upward), you'll struggle to understand, debug, or write these algorithms. Recursion also trains you to think in terms of subproblem decomposition: "what's the simplest version of this problem?" and "how does the full problem build on smaller versions?" This decomposition mindset is valuable far beyond recursive code.