Why can a recursive function with a correct base case still recurse forever?
answer
- the stopping condition is only half
- what must change on every call
- name the quantity that shrinks
- strictly decreasing, not merely different
- and it has to land on the base
basics
~20 sA base case only names where to stop; termination also requires every recursive call to move strictly closer to it. If the argument never shrinks, or steps past the base case without matching it, the recursion never ends.
solid answer
~50 sTermination is a two-part obligation. First there must be a base case: a condition under which the function returns without calling itself. Second, every recursive call must make progress — some measure computed from the arguments must strictly decrease, and it must decrease along a path that actually lands on the base condition. A function that recurses on the same value, or that shrinks the argument on one branch and passes it untouched on another, satisfies the first obligation and still runs forever. The subtler failure is a measure that decreases but skips the base: stepping by two toward an `n == 0` test never matches from an odd start. In review I say the measure out loud — "characters remaining strictly decreases, and every step lands on a value the base tests" — because if you cannot name it, it usually is not there.
go deeper
Be ready to state both obligations in one breath: a base case that returns without recursing, and a recursive call on a strictly smaller argument. Expect to be asked to point at both in a short fragment.
Explain progress as a named measure that strictly decreases and cannot descend forever, and show how an equality base condition gets stepped over when the measure moves in strides larger than one.
Show how you audit this in review: state the measure aloud, ask which inputs actually reach the base, and require the degenerate inputs — empty, single element, extreme value — as tests before approving.
Own the standard. Recursive code over untrusted or generated input deserves a written termination argument and degenerate-input tests, because one non-terminating branch discovered in production costs far more than the review minute spent naming the measure.
## Two obligations, not one A recursive function terminates only if two separate things hold, and answers routinely supply just the first. **1. A base case exists.** Somewhere there is a condition under which the function returns a value without calling itself. This is the exit. **2. Every recursive call makes progress toward that exit.** Progress is not vague. It means you can name a *measure* — a quantity computed from the arguments — such that: - it **strictly decreases** on every recursive call (not "usually", not "on most branches"), - it is drawn from a **well-founded** domain, one with no infinite descending chain (the non-negative integers, the number of remaining elements, the number of nodes in a subtree), and - the values it descends through actually **satisfy the base condition** at some point. Miss any of the three and the exit exists but is never taken. ## Why "the argument changes" is not progress Three classic ways a changing argument still fails to terminate: - **It changes without shrinking.** A function that alternates between two states visits a new argument on every call and revisits the same pair forever. - **It shrinks in a domain that is not well-founded.** Halving a positive fractional value gets smaller every time and never reaches zero: 1, 0.5, 0.25, … There is no smallest element to land on, so "it gets smaller" is not a termination argument. - **It shrinks on some paths only.** A branch you forgot passes the argument through unchanged. Typical inputs take the shrinking branch, and the bug hides until an input steers into the other one. ## Stepping over the base Even a strictly decreasing integer measure is not enough when the base case is an **equality** test and the step is larger than one. If the value moves in strides of two and the base tests `n == 0`, an odd start passes through 1 and goes negative, matching nothing. The measure decreased on every call, exactly as promised; the exit condition simply was never on the path. This is why base conditions are safer written as guards over a *region* ("stop while at or below the stride") than as a single point, and why a recursion whose step is bigger than one usually needs more than one base case. ## Measures for structures, not just numbers When the argument is a nested record rather than a counter, pick a numeric measure of it: the number of nodes remaining in the subtree, the size of the region still to process, the count of items not yet consumed. "The child is smaller than the parent" is a real measure because subtree node counts are non-negative integers. Where the data can contain a cycle, no such measure exists until you make one — for example by tracking visited items so the count of unvisited ones strictly decreases. ## Some languages check this for you; most do not This is a genuine design axis. Proof-oriented languages such as Agda and Coq reject a recursive definition outright unless a decreasing argument is evident to the compiler, so a non-terminating recursion cannot be written by accident. Mainstream languages such as Java, Go and Python accept any recursion at all and let it fail at runtime, which puts the entire termination argument in the reviewer's head. When the checker will not do it for you, saying the measure out loud in review is the substitute. ## The cost of getting it wrong Non-termination is a quiet defect. The typical input takes the shrinking path and the function returns fine, so tests pass and the reviewer sees a base case and moves on. It is the degenerate inputs — empty, single element, the extreme value, the odd length — that steer into the unguarded path. That is why the practical habit is worth more than the theory: name the measure, then ask which inputs reach the base, then write the degenerate inputs as tests.
- What makes a decreasing measure trustworthy rather than hand-waving?It has to be a concrete quantity computed from the arguments — remaining elements, subtree node count, magnitude of a counter — that strictly decreases on every recursive call and comes from a domain with no infinite descent, such as the non-negative integers. Naming it turns termination from a feeling into a claim a reviewer can check against each branch.
- Can the argument differ on every call and the recursion still never end?Yes. Alternating between two values changes the argument each time yet revisits the same states forever. Halving a positive fractional value strictly decreases and never reaches zero, because that domain has no least element. Both satisfy "the argument changed"; neither satisfies strict decrease within a well-founded domain that reaches the base.
- How do you argue termination when the argument is a nested structure rather than a number?Map the structure to a number and argue about that: nodes remaining in the subtree, items left to consume, size of the region still open. Show every recursive call reduces it. If the data may contain a cycle, no such measure exists until you add one — for instance a visited set, so the count of unvisited items strictly decreases.
A base case is the exit door. Progress is walking toward it. A room with a door you never step toward holds you just as well as a room with no door at all.
saying these in an interview costs you the question
- Claims a base case by itself guarantees termination
- Counts any change of argument as progress
- Says the input gets smaller eventually without naming a measure
- Assumes an equality base case is hit by any decreasing step
- Believes a non-terminating branch would always show up in testing