Recursion Explained: How to Actually Think Recursively

Recursion is when a function solves a problem by calling itself on a smaller version of that same problem, repeating until it hits a case simple enough to answer outright. It feels circular at first, but it rests on two parts you can always name: a base case (when to stop) and a recursive step (how to shrink the problem).

Recursion is famous for being counterintuitive, and it is a staple of coding interviews — it is the natural way to walk trees and graphs and the engine behind divide-and-conquer and backtracking. Once you trust the two parts, it stops feeling like a magic trick.

The two parts of every recursive function

1. Base case — the smallest input you can answer directly, with no further calls. This is the brake.
2. Recursive step — do a little work, then call the function again on a smaller input, trusting it to handle the rest.

function factorial(n) {
  if (n <= 1) return 1;          // base case: stop here
  return n * factorial(n - 1);   // recursive step: shrink toward the base
}
factorial(4); // 4 * 3 * 2 * 1 = 24

The leap of faith is the recursive step: you assume factorial(n - 1) already works, and you just combine its answer with n. You do not trace the whole thing in your head — you trust the smaller call.

What’s really happening: the call stack

Each call waits for its inner call to finish before it can complete. Those paused calls pile up on the call stack — itself a stack data structure — and unwind in reverse:

factorial(4)
└─ 4 * factorial(3)
       └─ 3 * factorial(2)
              └─ 2 * factorial(1)
                     └─ returns 1      ← base case
              └─ returns 2 * 1 = 2
       └─ returns 3 * 2 = 6
└─ returns 4 * 6 = 24

Calls go down until the base case, then results bubble up. This is also why recursion has a memory cost: every pending call occupies a stack frame, so the space complexity is O(depth). Recurse too deep — tens of thousands of calls — and you overflow the stack.

Tree recursion, and why naïve Fibonacci is a trap

When a function calls itself more than once, it branches into a tree of calls. Fibonacci is the classic:

function fib(n) {
  if (n < 2) return n;            // base case
  return fib(n - 1) + fib(n - 2); // two calls → branches
}

This is correct but disastrously slow: it recomputes the same values again and again, giving O(2ⁿ) growth (see Big O). fib(40) makes over a billion calls.

The fix is memoization — cache each result so it is computed once:

function fib(n, memo = {}) {
  if (n < 2) return n;
  if (n in memo) return memo[n];          // reuse
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

That single cache turns O(2ⁿ) into O(n). Recognising “I’m recomputing subproblems” and adding a cache is the gateway to dynamic programming.

Recursion vs iteration

Anything recursive can be written with a loop, and vice versa. Choose by clarity and cost.

A rule of thumb: if the data is nested (a tree, nested folders, a maze), recursion mirrors its shape and reads cleanly. If the data is flat (a list to sum), a loop is simpler and cheaper.

When to reach for recursion

• Trees and graphs — depth-first traversal is naturally recursive.
• Divide and conquer — merge sort, quick sort, binary search: split, solve halves, combine.
• Backtracking — permutations, subsets, N-Queens, Sudoku: try a choice, recurse, undo if it fails.
• Nested/self-similar structures — JSON, file systems, expression parsing.

Common mistakes

• Missing or wrong base case → infinite recursion → stack overflow. Write it first.
• Not shrinking the input → the recursive call must move toward the base case every time.
• Re-deriving subproblems → add memoization when calls overlap (Fibonacci, grid paths).
• Recursing too deep on huge inputs → for very deep problems, an explicit stack or a loop avoids overflow.

Where this fits

Recursion, Big O, and data structures are the three pillars of interview prep — and they interlock: recursion walks the data structures, and Big O measures the cost (including the call-stack space).

The call-stack diagrams, the recursion-to-memoization-to-DP progression, and backtracking templates are worked through in our job-ready tier: JavaScript in Three Months, Python in Three Months, and Java in Three Months. The harder dynamic-programming and backtracking problems that surface in senior and staff interviews get the full treatment in the for Staff Engineers tier: JavaScript, Python, and Java.

Stop trying to trace every call in your head. Name the base case, trust the smaller call, and recursion becomes a tool instead of a riddle.