Base Case and Recursive Case: The Two-Part Contract

"Recursion feels like magic or madness until you see it's just two promises: 'here's a case I can answer outright,' and 'every other case, I'll shrink toward that one.' Hold both and recursion is safe; drop either and it spirals."

A Function That Calls Itself

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It sounds circular, and it would be — except for a piece that breaks the circle. Every correct recursion has exactly two parts:

Base case: a problem small enough to answer immediately, with no further recursion. This is the floor that stops the descent.
Recursive case: solve a smaller version (by calling yourself), then build this answer from it — always moving toward the base case.

Factorial is the classic: factorial(0) = 1 (base case), and factorial(n) = n × factorial(n−1) (recursive case, shrinking n toward 0). Each call peels off one layer until it hits the base, then the answers multiply back up.

The Two Ways It Breaks

Recursion fails in exactly two ways, and both are failures of the contract. No base case: the function never stops calling itself, the call stack fills, and Python raises RecursionError. No progress toward the base case: even with a base case, if the recursive call isn't actually smaller (you call f(n) instead of f(n−1)), you never reach the floor — same crash. So the contract is two-sided: there must be a base case, AND every recursive call must move measurably closer to it.

Every recursion needs a base case (answer directly, stop) and a recursive case (shrink toward the base, then combine). Miss the base case OR fail to shrink toward it, and the call stack overflows. Both halves are mandatory.

Recursion Is Induction, Running

If you've seen mathematical induction, recursion will feel familiar — they're the same idea. Induction proves a statement by establishing a base case (it holds for n=0) and an inductive step (if it holds for n−1, it holds for n). Recursion computes the same way: base case + 'assume the smaller call is correct, build on it.' That assumption is the leap of faith from the Trees track: when writing the recursive case, trust that factorial(n−1) already returns the right answer, and only worry about combining it. Don't trace the whole stack in your head — the base case and induction guarantee correctness.

Pippa's Confession

My first recursions either crashed instantly (no base case) or ran forever (I recursed on n instead of n−1 — no progress). Dad gave me a checklist I still run: "Point at your base case. Now point at the line that makes the input smaller." If I can't point at both, it's broken. Those two questions turned recursion from a source of mysterious crashes into something I could verify in five seconds.

Code

Base case + recursive case (and two ways to break it)·python

def factorial(n):
    if n == 0:               # BASE CASE: answer directly, stop recursing
        return 1
    return n * factorial(n - 1)   # RECURSIVE CASE: shrink toward 0, then combine

print(factorial(5))          # 120  (5*4*3*2*1)

def sum_list(items):
    if not items:            # BASE CASE: empty list sums to 0
        return 0
    return items[0] + sum_list(items[1:])   # first + sum of the rest (smaller)

print(sum_list([1, 2, 3, 4]))   # 10

# BROKEN: no base case -> infinite recursion -> RecursionError.
# def bad(n): return n + bad(n - 1)   # never stops; nothing says 'enough'

# BROKEN: base case exists but no PROGRESS toward it -> also crashes.
# def stuck(n):
#     if n == 0: return 1
#     return stuck(n)      # calls itself on the SAME n — never shrinks

Exercise

Write a recursive function that counts down from n to 1 and then prints 'liftoff'. Clearly identify your base case and your recursive case. Then sabotage it two ways — once by removing the base case, once by recursing on n instead of n−1 — and predict what error each version produces and why.

Hint

Base case: when n == 0, print 'liftoff' and return. Recursive case: print n, then recurse on n−1. Removing the base case → it counts into negatives forever → RecursionError. Recursing on n (not n−1) → never shrinks → also RecursionError. Both break the 'progress toward base' half of the contract.

A Function That Calls Itself

The Two Ways It Breaks

Recursion Is Induction, Running

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0