Recursion: Base Cases, the Call Stack & Patterns

Recursion

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. It's a way of thinking as much as a technique: instead of describing how to loop through every step, you describe how to reduce a problem to a smaller one and what the smallest case looks like. Many problems — trees, graphs, divide-and-conquer sorts, backtracking searches — are far more natural to express recursively than iteratively.

The whole idea rests on two parts: a base case that stops the recursion, and a recursive case that moves toward it. Get those right and recursion is elegant; get the base case wrong and you get infinite recursion and a stack overflow. Understanding the call stack is what makes it click.

TL;DR

A recursive function calls itself on a smaller subproblem.
Every recursion needs a base case (stop) and a recursive case (reduce).
Each call uses stack space — deep recursion can overflow.
Natural for trees, graphs, divide-and-conquer, and backtracking.

Quick Example

Factorial — a base case and a recursive case that shrinks toward it:

The Two Essential Parts

Base case — the smallest input you can answer directly, without recursing. Without it (or with a wrong one), the function calls itself forever.
Recursive case — solves the problem in terms of a smaller instance, making progress toward the base case.

Every recursive function must, on every path, move closer to a base case. If it doesn't, it recurses infinitely.

The Call Stack

Each recursive call gets its own stack frame (its local variables and where to return). Calls pile up as you recurse deeper, then unwind as each returns:

This is also why deep recursion overflows the stack — each frame uses memory, and there's a limit (Python defaults to ~1000 deep). For very deep recursion, convert to iteration or increase the limit deliberately.

Common Patterns

Divide-and-conquer — split into independent subproblems, solve each recursively, combine (mergesort, quicksort, binary search).
Tree/graph traversal — recurse into children/neighbors (DFS, tree walks).
Backtracking — try a choice, recurse, undo if it fails (permutations, sudoku, N-queens, maze solving).
Recursive structures — anything naturally nested (JSON, file systems, expression parsing).

Recursion vs Iteration

Anything recursive can be written iteratively (with an explicit stack) and vice versa. Recursion is often clearer for naturally recursive structures (trees, divide-and-conquer); iteration is often more efficient (no call overhead, no stack-depth limit) for linear processes.

💡 Some languages optimize tail recursion into a loop (no stack growth), but Python and JavaScript generally do not — so deep recursion there needs an iterative rewrite.

Best Practices

Write the base case first — and make sure every path reaches it.
Ensure each call shrinks the problem toward the base case.
Add memoization when subproblems overlap — that's dynamic programming.
Watch recursion depth — convert deep/linear recursion to iteration.
Prefer recursion for recursive structures (trees/graphs), iteration for simple loops.

Common Mistakes

Missing or wrong base case

Deep recursion that should be iteration

FAQ

When should I use recursion instead of a loop?

Use recursion when the problem is naturally recursive — traversing trees or graphs, divide-and-conquer algorithms, backtracking searches, or processing nested structures (JSON, file systems). The recursive code mirrors the structure and is far clearer. Use a loop for simple linear processing, or when recursion depth could overflow the stack. Anything recursive can be written iteratively, so the choice is about clarity and stack safety, not capability.

What causes a stack overflow in recursion?

Each recursive call adds a frame to the call stack (holding local variables and the return address), and the stack has a finite size. If recursion goes too deep — either because of a missing/incorrect base case (infinite recursion) or legitimately deep recursion over a large input — the stack runs out of space and the program crashes with a stack overflow. Fix it by ensuring a correct base case, converting deep linear recursion to iteration, or (carefully) raising the recursion limit.

What's the difference between recursion and iteration?

Both repeat work, but differently. Iteration uses a loop and constant stack space, repeating until a condition is met. Recursion repeats by calling itself, with each call consuming a stack frame until base cases unwind. They're equivalent in power — any recursion can be rewritten as iteration with an explicit stack, and vice versa. Recursion is usually clearer for nested/branching problems; iteration is usually more memory-efficient and avoids stack-depth limits for linear work.

How does recursion relate to dynamic programming?

Dynamic programming is essentially recursion plus caching. Many DP solutions start as a recursive brute force with overlapping subproblems; adding memoization (a cache) turns the exponential recursion into efficient polynomial time. So recursion is the foundation — DP is what you get when the recursive subproblems repeat and you store their results to avoid recomputation. Learning recursion well is the prerequisite for dynamic programming.