Recursive definitions: base cases, smaller selves, and the contract behind the leap of faith

Two parts: a floor, and a rule that climbs down to it.

A recursive definition defines a thing in terms of a smaller version of itself. It always has exactly two kinds of parts:

• Base case(s) — inputs answered outright, with no reference to the thing being defined. The floor.
• Recursive rule — a recipe that builds the answer for a bigger input out of the answer for a strictly smaller one.

The classic example is the factorial of a number, written n! — the product of all whole numbers from 1 to n:

• Base case: 0! = 1
• Rule: n! = n · (n-1)! for every n ≥ 1

Watch the definition compute 4! all by itself. Each step replaces a factorial with what the rule says, until the base case stops the chain:

4! = 4 · 3!
   = 4 · (3 · 2!)
   = 4 · (3 · (2 · 1!))
   = 4 · (3 · (2 · (1 · 0!)))
   = 4 · (3 · (2 · (1 · 1)))    ← base case: 0! = 1, no further reference
   = 24

Nothing circular happened. The rule for 4! never mentioned 4! — it mentioned 3!, a strictly smaller problem. The chain 4 → 3 → 2 → 1 → 0 had to end, because each step went down and there was a floor at 0.

The factorial example traced through the call stack.

Translate the two-part definition directly into code, base case first:

function factorial(n) {
  if (n === 0) return 1;        // base case FIRST: the floor answers outright
  return n * factorial(n - 1);  // rule: one layer of work · a smaller self
}

factorial(4); // 24

Now trace factorial(4) the way the machine does it. Every call that cannot answer yet waits, and the runtime keeps each waiting call alive as a frame on the call stack:

factorial(4) → needs 4 * factorial(3)   …waits
  factorial(3) → needs 3 * factorial(2)   …waits
    factorial(2) → needs 2 * factorial(1)   …waits
      factorial(1) → needs 1 * factorial(0)   …waits
        factorial(0) → base case → returns 1   (no waiting!)
      factorial(1) resumes: 1 * 1 = 1
    factorial(2) resumes: 2 * 1 = 2
  factorial(3) resumes: 3 * 2 = 6
factorial(4) resumes: 4 * 6 = 24

Five frames going down, five answers cascading back up. The deepest moment holds all five frames at once.

Data structures are defined recursively too.

The pattern is not just for numbers. The most useful data shapes in programming are recursive definitions:

• A list is either empty, or a first element (the head) followed by a smaller list (the tail).
• A directory tree is some files, plus some directories — each of which is a smaller directory tree.

You have already run a recursive definition in anger: every du -sh node_modules, every “calculate folder size” in a file manager, is the directory definition executed. The structure of the code matches the structure of the definition line for line:

function dirSize(dir) {
  let total = 0;
  for (const entry of entriesOf(dir)) {
    if (entry.isFile) total += entry.size;   // base ingredient: a file has a size
    else              total += dirSize(entry); // a directory is a SMALLER tree
  }
  return total;
}

Where is the base case? Hidden in plain sight: an empty directory has no entries, the loop body never runs, and the function returns 0 without calling itself. Base cases do not always wear an if — sometimes they are the branch where the recursive call simply never happens. Every leaf of the file system is a floor.

Here is a second definition built the same way, with no formula in sight. The staircase numbers: S(n) counts the ways to climb a staircase of n steps if each stride covers 1 or 2 steps.

• Base cases: S(1) = 1 (one single stride), S(2) = 2 (1+1, or one double)
• Rule: S(n) = S(n-1) + S(n-2) — your first stride is either a single (leaving a staircase of n−1) or a double (leaving n−2)

The rule lets you compute values you have never seen: S(3) = S(2) + S(1) = 3, then S(4) = S(3) + S(2) = 5. The definition is the algorithm.

The two laws — and what breaks when you violate them.

Every legitimate recursive definition (and every recursive function) obeys two laws:

1. Every recursive step must move toward a base case. The input of the inner call must be strictly smaller by some honest measure: a smaller number, a shorter list, a subtree.
2. A base case must exist on every path. Whatever input you start from, the shrinking chain must actually land on a floor.

Delete the base case and run it:

def factorial(n):
    return n * factorial(n - 1)   # no floor

factorial(4)
# RecursionError: maximum recursion depth exceeded

Nothing mystical happens — follow the frames. factorial(4) waits on factorial(3), which waits on factorial(2), then 1, then 0, then −1, then −2… No call ever returns, because returning requires a base case and there is none. Every unfinished call sits waiting on the stack, frame upon frame, and the stack is a finite strip of memory. Python gives up around a thousand frames with RecursionError; JavaScript throws RangeError: Maximum call stack size exceeded. A “stack overflow” is not the machine getting confused by self-reference — it is the machine faithfully storing thousands of IOUs that nobody will ever pay.

Law 2 is subtler than it looks: the base case must be reachable from every starting input. factorial(4.5) steps 4.5 → 3.5 → 2.5 → … and hops right over n === 0 without ever hitting it — the chain moves toward the floor and misses it. Real code guards for this (if (!Number.isInteger(n) || n < 0) throw …); real definitions state their domain (“for whole numbers n ≥ 0”).

The misconception: recursion is not circular magic.

The junior from the prologue is owed an answer. Calling factorial(n - 1) inside factorial feels like using a thing before it exists. It is not. It is using the definition: (n-1)! is a defined, fixed value — the definition pins it down completely, the way 0! pins down 1. The function body does not need factorial to be “finished”; it needs the equation to be true, and the equation stands on its own.

So here is the working contract, the thing seniors actually do in their heads:

• Handle one layer yourself. Your code is responsible for combining the head with the tail result, the current directory with its subtrees — one layer, nothing more.
• Trust the smaller call completely. Assume factorial(n - 1) returns exactly (n-1)!. Do not mentally re-trace it.
• Check the two laws. Smaller every step; floor on every path.

People call step two the leap of faith, but the name oversells the risk: you are not trusting luck, you are trusting a definition that is anchored to a base case and shrinks toward it. In the next lessons this trust gets a price tag (how much work do all those calls add up to?) and a warranty (a proof technique that turns the leap into a theorem).