Recursion

How It Works

Recursion is a technique where a function solves a problem by calling itself on a smaller or simpler version of that same problem. Every recursive function needs two things: a base case (the smallest version of the problem that can be answered directly, without further recursion) and a recursive case, where the function breaks the problem down and calls itself on that smaller piece, combining the result with the current step's work.

Under the hood, each call to a function pushes a new frame onto the call stack, holding that call's local variables and the point it should return to. When the base case is hit, the stack starts unwinding: each frame returns its result to the frame that called it, until the original call returns the final answer. Understanding this stack behavior is essential: it's both how recursion produces its result and the reason deep recursion can fail with a "Maximum call stack size exceeded" error.

Most recursive solutions fall into one of a few shapes: linear recursion (like computing a factorial or summing a linked list, where each call makes exactly one recursive call), branching recursion (like Fibonacci or generating subsets, where each call makes two or more recursive calls), and tree recursion (traversing binary trees or nested structures, where the recursive structure of the data mirrors the recursive structure of the code).

When To Use It

Reach for recursion when the problem can naturally be defined in terms of a smaller version of itself; for example, "the sum of a list is the first element plus the sum of the rest of the list." This self-referential framing is often the clearest signal.

It's also the natural tool whenever you're working with trees, graphs, or other nested/recursive data structures (JSON, nested comments, file systems, DOM trees), since traversing them iteratively usually requires you to manage an explicit stack anyway; recursion lets the call stack do that bookkeeping for you.

Backtracking problems (generating all permutations, combinations, subsets, or valid parenthesis combinations) are almost always recursive, because at each step you're making a choice, recursing into the consequences of that choice, and then "undoing" it to try the next option.

Finally, if a brute-force approach to a problem naturally branches into multiple sub-choices at each step (try option A, try option B, ...), that branching structure is usually much easier to express recursively than with nested loops.

Time & Space Complexity

Time complexity depends entirely on how many calls are made and how much work happens per call. Linear recursion (one recursive call per invocation) typically costs O(n). Branching recursion without memoization can explode to O(2^n) or worse; naive Fibonacci recomputes the same subproblems exponentially many times, which is exactly the pattern memoization or dynamic programming fixes.

Space complexity is the part interviewers probe hardest: every recursive call adds a frame to the call stack, so a recursion that goes n levels deep uses O(n) space, even if it does O(1) work per call. This is easy to miss because it's not "extra" data structure you allocated; it's implicit, paid for by the runtime. Deep recursion (say, over an unbalanced tree or a list of 100,000 elements) can overflow the stack even when the algorithm is logically correct.

// Base case + recursive case: sum of a tree's node values
function sumTree(node) {
  if (node === null) return 0; // base case
  return node.value + sumTree(node.left) + sumTree(node.right); // recursive case
}

// Classic linear recursion with a clear base case
function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case
}

// Branching recursion with memoization to avoid exponential blowup
function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}

Alternative Approaches

Any recursive algorithm can be rewritten iteratively using an explicit stack or queue to simulate the call frames yourself; this trades the elegance of recursion for full control over memory and avoids stack-overflow risk entirely. For linear recursion, an iterative loop is usually just as readable and strictly better on space (O(1) instead of O(n)). For tree and graph traversals, an explicit stack (DFS) or queue (BFS) is the standard non-recursive alternative, and it's worth being comfortable converting between the two forms in an interview.

Tail-call recursion (where the recursive call is the very last operation) is theoretically optimizable into a loop by the runtime, but note that most JavaScript engines, including V8, do not implement tail-call optimization despite it being in the ES2015 spec, so you can't rely on it to avoid stack overflow in JS.

Common Mistakes

• Missing or incorrect base case: causes infinite recursion and a stack overflow. Always identify the base case before writing the recursive case.
• Not making progress toward the base case: recursing on the same or a larger input instead of a strictly smaller one.
• Ignoring call-stack space cost: assuming a recursive solution is "free" in space when it's actually O(depth), which matters for deep trees or large n.
• Recomputing overlapping subproblems: naive branching recursion (like plain Fibonacci) without memoization leads to exponential time.
• Off-by-one errors in the recursive step: passing n instead of n - 1, or slicing an array incorrectly, causing infinite loops or wrong results.
• Forgetting to return the recursive call's result: calling the function recursively but discarding its return value.

Pattern Summary

Recursion lets you express "solve this problem using the solution to a smaller version of itself" directly in code, which is often clearer than the equivalent iterative version, especially for trees, graphs, and backtracking. The tradeoff is call-stack space and the risk of exponential blowup without memoization, so always identify the base case first and think about whether overlapping subproblems need caching.