Recursion

Recursion occurs when a function calls itself to solve a smaller instance of the same problem. It is the natural control flow for any problem with a recursive structure — trees, graphs, and anything that “contains a smaller version of itself.”

Every correct recursive solution has two mandatory parts:

1. Base case(s): the smallest input solved directly, without recursion. Without one, the function recurses forever.
2. Recursive case(s): the problem is reduced toward the base case — each call must work on a strictly smaller input, or the base case is unreachable.

factorial(n):
  if n ≤ 1: return 1         # base case
  return n * factorial(n-1)  # recursive case

The Call Stack and Stack Frames

Each call pushes a stack frame holding the function’s parameters, local variables, and the return address. Recursion is not magic — it is nested calls to the same code, and frames pop off in reverse order as calls complete:

factorial(3)  →  factorial(2)  →  factorial(1) → 1
  1×2 = 2     ←  2×3 = 6       ←  unwind with results

Depth limit: every runtime bounds stack depth (typically ~10⁴–10⁶ frames). Exceeding it raises a stack overflow — a crash, not a slow result. If the recursion depth scales with input size, the overflow risk is a correctness bug, not a style issue.

Divide and Conquer

A recursive pattern that splits a problem into independent subproblems of the same type:

1. Divide into smaller subproblems.
2. Conquer each subproblem recursively (or directly at the base case).
3. Combine the sub-results into the final answer.

Examples: merge sort, quicksort, binary search, tree traversals. Because the subproblems are independent, divide-and-conquer is naturally parallelizable, and its recursion tree is exactly what you analyze to derive the big-O recurrence.

Backtracking

Backtracking is recursion with undo: try a candidate, recurse, and if the branch fails, revert the choice and try the next. The call stack itself holds the state — no explicit stack needed.

solve(board, pos):
  if pos past the end: return solved
  for each candidate:
    place candidate
    if solve(board, pos + 1): return solved
    remove candidate          # backtrack
  return dead-end

Patterns: N-Queens, maze solving, Sudoku — any exhaustive search where pruning (rejecting a branch early) matters more than the base recursion.

Tail Recursion vs Iteration

A call is tail-recursive when it is the last operation in the function — the recursive call’s result is returned directly, with nothing left to do. A tail-call-optimizing compiler reuses the current frame, effectively turning the recursion into a loop:

factorialTail(n, acc):          # O(1) stack if the runtime optimizes
  if n ≤ 1: return acc
  return factorialTail(n-1, n * acc)

Non-tail recursion (like n * factorial(n-1) above) must keep one frame per level. That is why naive recursion on linear input is O(n) stack, while balanced divide-and-conquer is only O(log n) stack — and why depth is the variable to watch.

Recursion vs Iteration

Decision rule: use recursion when the problem is defined recursively — trees, DAGs, exhaustive search. Switch to iteration (or tail recursion) when the depth scales with input size, or when the call overhead sits on a hot path.

Worked Example

Fibonacci is the classic trap — a beautiful recursion with an exponential recursion tree:

fib(n):
  if n ≤ 1: return n
  return fib(n-1) + fib(n-2)

fib(5) ── fib(4) ── fib(3) ── fib(2) → 1
                    │         └─ fib(1) → 1
                    └─ fib(2) → 1
         └─ fib(3) ── fib(2) → 1      (recomputed from scratch)
                    └─ fib(1) → 1

fib(2) is computed three times and fib(3) twice — the tree holds ~O(2ⁿ) nodes, so naive Fibonacci is exponential. Add memoization and each state is computed once: O(n) time. The lesson generalizes: recursion is a control-flow tool, and its pattern — not recursion itself — determines cost. Overlapping subproblems demand memoization or full dynamic programming.

Practice Trajectory

1. Write recursive factorial and fibonacci with a depth counter; run them at n = 1000 and observe the failure mode.
2. Rewrite both in tail-recursive form and, if your language optimizes tail calls, confirm the stack stops growing.
3. Implement merge sort recursively and trace its recursion tree on an 8-element array.
4. Implement backtracking N-Queens, add a pruning check, and measure the search-tree reduction.
5. Convert an in-order tree traversal from recursive to explicit-stack iterative; compare code size and stack usage.

When It’s the Right Tool