Recursion

How recursion works

A recursive function has two parts:

1. Base case — the input small enough to solve directly. Returns a value without recursing.
2. Recursive case — handles all other inputs by reducing them toward the base case and calling itself.

Without a base case, recursion is infinite and crashes the stack. Without a recursive case, the function isn't recursive. Every recursive function must have both.

The classic example is factorial:

function factorial(n) {
  if (n === 0) return 1;        // base case
  return n * factorial(n - 1);  // recursive case
}

To compute factorial(5), the runtime calls factorial(4), which calls factorial(3), all the way to factorial(0) which returns 1. Then each call returns n × (returned value): 1, 1, 2, 6, 24, 120. Each pending call lives in a stack frame; the stack here grows 5 deep.

Recursion is a stack in disguise

Every recursive call pushes a frame onto the call stack. The frame holds local variables, the return address, and saved registers. When the call returns, the frame is popped and control flows back to the caller.

This is why every recursive algorithm has an iterative equivalent — you simulate the call stack with an explicit data structure on the heap:

// Recursive
function sumList(node) {
  if (!node) return 0;
  return node.value + sumList(node.next);
}

// Iterative (explicit stack — though for this case a simple loop suffices)
function sumListIter(head) {
  let total = 0;
  for (let node = head; node; node = node.next) total += node.value;
  return total;
}

For tree and graph traversals, the conversion is less trivial — you push frames onto an explicit stack and process them in a loop. The output is identical to the recursive version, but the stack lives on the heap and can hold millions of frames instead of the ~50,000-frame call-stack limit.

Linear recursion vs tree recursion

	Linear recursion	Tree recursion
Recursive calls per invocation	1	2 or more
Total calls	O(n)	Up to O(2^n) without memoization
Stack depth	O(n)	O(depth)
Examples	Factorial, list traversal, sum	Fibonacci, tree DFS, generate subsets
Optimization needed	Tail call (sometimes)	Memoization (often)
Performance risk	Stack overflow on long lists	Exponential time on overlapping subproblems

Tree recursion is where dynamic programming earns its keep. Naive recursive Fibonacci recomputes fib(3) billions of times for n = 50; memoizing the function turns it into O(n) by caching each call's result.

Tail recursion and tail-call optimization

A call is in tail position if it's the last action a function performs. Compare:

// Not tail-recursive: the multiplication happens AFTER the recursive call returns
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

// Tail-recursive: the recursive call IS the last action
function factorialTail(n, acc = 1) {
  if (n === 0) return acc;
  return factorialTail(n - 1, n * acc);
}

In tail position, there's nothing the caller needs to do after the recursive call returns — the caller's frame is dead. A tail-call-optimized compiler reuses the frame instead of pushing a new one, turning the recursion into a loop with O(1) stack space.

Languages with TCO: Scheme, Haskell, OCaml, F#, Lua, Erlang, Elixir. Languages WITHOUT TCO: Python (Guido decided against it), Java, C#, JavaScript (the ES6 spec required it but no major browser implements it). For those languages, tail recursion is just a coding style — the runtime still pushes frames per call.

When to use recursion

• Tree and graph traversal. Pre/in/post-order tree walks, depth-first graph search. The recursive version is 5-10× shorter and clearer than the iterative equivalent.
• Divide-and-conquer. Merge sort, quick sort, binary search, fast Fourier transform, Karatsuba multiplication — all recursive. The recursion mirrors the problem structure: split, solve smaller pieces, combine.
• Parsers and grammars. Recursive descent parsers map naturally to grammar rules. Each non-terminal becomes a function that calls other non-terminal functions.
• Backtracking. Generate all permutations, solve sudoku, n-queens, maze pathfinding. Recursion makes "try this branch, if it fails undo and try the next" trivial — the call stack does the bookkeeping.
• Mathematical recurrences. Factorial, Fibonacci, Ackermann's function, recursive sequences. The code reads like the math.

Avoid recursion when the depth is unbounded by data (e.g., processing a stream of unknown length) or when stack-overflow risk would crash the program. For those, use iteration.

Famous recursive problems

Fibonacci — naive vs memoized

// Naive: O(2^n) — recomputes the same fib(k) billions of times
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

// Memoized: O(n) — each fib(k) computed once, cached
function fibMemo(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

Binary tree in-order traversal

function inorder(node, visit) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.value);
  inorder(node.right, visit);
}

The recursive version is three lines. The iterative version using an explicit stack is fifteen and easy to get wrong on the first try.

Python implementation

import sys
sys.setrecursionlimit(10000)  # Python's default is 1000 — raise it if you need deeper recursion

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

def fib_memo(n, memo=None):
    if memo is None: memo = {}
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Or with @functools.lru_cache:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Common bugs and edge cases

• Forgotten or unreachable base case. The most common bug — usually a typo in the comparison (< vs <=) means inputs skip past the base case and recurse forever. Test with the smallest valid input first.
• Stack overflow on large inputs. If your input size could exceed ~10,000, switch to iteration. Tree recursion on a balanced tree of 1M nodes uses ~20 frames (log₂ 1M); on a degenerate left-skewed tree it uses 1M frames and crashes.
• Exponential blowup from overlapping subproblems. Tree recursion that recomputes the same input multiple times — Fibonacci is the canonical example. Add memoization or convert to dynamic programming.
• Mutating shared state across recursive branches. If a backtracking algorithm mutates a shared array, all branches share the mutation. Either pass a fresh copy down (slow but safe) or undo the mutation on the way out of each frame.
• Assuming TCO in a language that doesn't support it. Writing tail-recursive code in JavaScript or Python doesn't save stack space — the runtime still pushes frames. Convert to a loop if the depth might be large.