A turn-based game's two phase functions each end by calling the other; what must decrease for the pair to terminate?

juniorshould knowfreq 46%

answer

two definitions, one cycle
what shrinks, not who calls
measure spans both argument lists
strict decrease on every crossing
tie-break with the phase component

basics

~20 s

Some measure defined over both functions' arguments must strictly decrease every time control crosses between them, drawn from an order with no infinite descent. Neither function shrinks anything on its own, so the argument covers the pair together.

solid answer

~40 s

Mutual recursion is two functions defined in terms of each other: the player phase ends by calling the enemy phase, which ends by calling the player phase. Termination is proved exactly as for a single recursive function, except the measure is defined over the whole cycle rather than one body. Pick a quantity that appears in the arguments of both — the remaining move budget, the size of the sub-structure being walked — show it comes from an order with no infinite descending chain, and show it strictly decreases on every crossing. When a crossing keeps the payload the same size, pair it with the phase itself and compare (payload, phase) left to right; the phase is then the component that decreases there.

Mutual recursion is two functions defined in terms of each other: the player phase ends by calling the enemy phase, which ends by calling the player phase. Termination is proved exactly as for a single recursive function, except the measure is defined over the whole cycle rather than one body. Pick a quantity that appears in the arguments of both — the remaining move budget, the size of the sub-structure being walked — show it comes from an order with no infinite descending chain, and show it strictly decreases on every crossing. When a crossing keeps the payload the same size, pair it with the phase itself and compare `(payload, phase)` left to right; the phase is then the component that decreases there.

code

pseudocode · 9 lines

pseudocode

function playerTurn(moves):
    if moves <= 0:
        return "draw"
    return enemyTurn(moves - 1)

function enemyTurn(moves):
    if moves <= 0:
        return "draw"
    return playerTurn(moves - 1)

go deeper

for a junior

Be able to say that two functions calling each other in a cycle is still recursion, and that something in the arguments has to get smaller on each lap.

for a middle

Explain the measure itself: name the quantity, show it lives in both argument lists, and show it strictly decreases every time control crosses between the functions.

for a senior

Know that the check is per call edge rather than per body, and that a cycle through three or more functions is where hand-verification quietly fails in review.

for a principal

Weigh whether a cycle of definitions is worth its reasoning cost, or whether the team should prefer shapes whose termination a reader can confirm without leaving the file.

Two definitions, one cycle

Mutual recursion is two or more functions defined in terms of each other, so the call graph holds a cycle that passes through all of them. A turn-based game loop is the clearest case: playerTurn ends by calling enemyTurn, and enemyTurn ends by calling playerTurn. Neither body contains a call to itself. A reader checking one function at a time sees two ordinary functions that delegate, and a check that looks only for self-calls finds no recursion — yet the cycle is there, and it brings the same obligation a self-recursive function brings.

That obligation is termination. For a single recursive function the argument is familiar: find a measure, a value drawn from an order with no infinite descending chain (a non-negative integer count, the size of a sub-structure), show it strictly decreases at every recursive call, and show the base case fires when it bottoms out. Mutual recursion needs the same argument with one change of scope: the measure is defined over the arguments of every function in the cycle, and it is checked on every call edge, not inside one body.

What you actually check

For the turn pair, the measure is the remaining move budget, and the checklist is short:

Name the quantity and say where it lives in each function's arguments. If you cannot point at it in both signatures, you do not yet have a measure for the cycle.
Show the order is well founded. Counts down to zero work; a value that can drift in both directions does not.
Check every edge. Player to enemy, and enemy to player. An edge that leaves the measure unchanged can be taken forever, so it needs its own justification.
Check the bottom. When the measure is at its floor, control must be in a body whose base case actually fires for that value — a test for exact equality can be stepped past if the floor is reached inside the other function and the value keeps falling.

When nothing shrinks at one crossing

Some pairs genuinely do not shrink their payload at one of the crossings. A validating phase may hand the very same record to a classifying phase, which only then recurses into one of the record's fields. The size argument fails on the first edge, and candidates often conclude the pair cannot be proved to terminate. It can: use a lexicographic measure, a pair compared left to right.

Take (size, phase rank) with the classifying phase ranked below the validating one. The validate-to-classify edge keeps size and moves to a strictly smaller rank, so the pair decreases. The classify-to-validate edge recurses into a field, so size strictly decreases and the rank may reset to the top. Pairs ordered this way have no infinite descending chain either, so the cycle must bottom out. The phase, in other words, is doing real work in the proof — which is a hint about what a merged single-function version of the pair would have to carry as an argument.

Self-recursive against mutually recursive

Question	One self-recursive function	A cycle through two functions
Where is the measure defined?	on this body's arguments	on the arguments of both bodies
Where is it checked?	at each recursive call	at each edge of the cycle
Where must a base case live?	in the one body	wherever the measure bottoms out
Can one body be read in isolation?	yes	no — the cycle is the unit
Does a self-call search find it?	yes	no; you have to follow the call graph

Where the argument usually breaks

Only one body gets read. In review, the natural move is to open playerTurn, see a smaller argument passed on, and approve. The decrease has to hold on the way back as well.
The base case sits in only one of the two. Every lap does pass through both functions, so a single check is reachable — but only fires if the measure is at the value it tests when control is in that body. Testing for having passed the floor rather than sitting exactly on it removes the trap.
The cycle grows a third member. A helper added later can close a shorter loop that skips the function carrying the decrease. Cycles of three or more are where hand-verification quietly fails, because two of the three edges usually do look right.

None of this makes mutual recursion exotic. It is the same proof obligation as ordinary recursion, relocated from a body to a cycle, and the cost of forgetting that relocation is a pair of functions that each look obviously fine.

## Two definitions, one cycle **Mutual recursion** is two or more functions defined in terms of each other, so the call graph holds a cycle that passes through all of them. A turn-based game loop is the clearest case: `playerTurn` ends by calling `enemyTurn`, and `enemyTurn` ends by calling `playerTurn`. Neither body contains a call to itself. A reader checking one function at a time sees two ordinary functions that delegate, and a check that looks only for self-calls finds no recursion — yet the cycle is there, and it brings the same obligation a self-recursive function brings. That obligation is **termination**. For a single recursive function the argument is familiar: find a **measure**, a value drawn from an order with no infinite descending chain (a non-negative integer count, the size of a sub-structure), show it strictly decreases at every recursive call, and show the base case fires when it bottoms out. Mutual recursion needs the same argument with one change of scope: the measure is defined over the arguments of **every** function in the cycle, and it is checked on **every call edge**, not inside one body. ## What you actually check For the turn pair, the measure is the remaining move budget, and the checklist is short: - **Name the quantity** and say where it lives in each function's arguments. If you cannot point at it in both signatures, you do not yet have a measure for the cycle. - **Show the order is well founded.** Counts down to zero work; a value that can drift in both directions does not. - **Check every edge.** Player to enemy, and enemy to player. An edge that leaves the measure unchanged can be taken forever, so it needs its own justification. - **Check the bottom.** When the measure is at its floor, control must be in a body whose base case actually fires for that value — a test for exact equality can be stepped past if the floor is reached inside the other function and the value keeps falling. ## When nothing shrinks at one crossing Some pairs genuinely do not shrink their payload at one of the crossings. A validating phase may hand the very same record to a classifying phase, which only then recurses into one of the record's fields. The size argument fails on the first edge, and candidates often conclude the pair cannot be proved to terminate. It can: use a **lexicographic measure**, a pair compared left to right. Take `(size, phase rank)` with the classifying phase ranked below the validating one. The validate-to-classify edge keeps `size` and moves to a strictly smaller rank, so the pair decreases. The classify-to-validate edge recurses into a field, so `size` strictly decreases and the rank may reset to the top. Pairs ordered this way have no infinite descending chain either, so the cycle must bottom out. The phase, in other words, is doing real work in the proof — which is a hint about what a merged single-function version of the pair would have to carry as an argument. ## Self-recursive against mutually recursive | Question | One self-recursive function | A cycle through two functions | |---|---|---| | Where is the measure defined? | on this body's arguments | on the arguments of both bodies | | Where is it checked? | at each recursive call | at each edge of the cycle | | Where must a base case live? | in the one body | wherever the measure bottoms out | | Can one body be read in isolation? | yes | no — the cycle is the unit | | Does a self-call search find it? | yes | no; you have to follow the call graph | ## Where the argument usually breaks 1. **Only one body gets read.** In review, the natural move is to open `playerTurn`, see a smaller argument passed on, and approve. The decrease has to hold on the way back as well. 2. **The base case sits in only one of the two.** Every lap does pass through both functions, so a single check is reachable — but only fires if the measure is at the value it tests when control is in that body. Testing for having passed the floor rather than sitting exactly on it removes the trap. 3. **The cycle grows a third member.** A helper added later can close a shorter loop that skips the function carrying the decrease. Cycles of three or more are where hand-verification quietly fails, because two of the three edges usually do look right. None of this makes mutual recursion exotic. It is the same proof obligation as ordinary recursion, relocated from a body to a cycle, and the cost of forgetting that relocation is a pair of functions that each look obviously fine.

Your pair keeps the payload the same size at the phase switch — how do you still get a termination argument?
Compare pairs instead of numbers: order `(payload, phase)` left to right. The switch keeps the payload and moves to a strictly smaller phase rank, and the edge that recurses into a part shrinks the payload and may reset the rank. That order has no infinite descending chain, so the cycle bottoms out.
A third function joins the cycle. What changes in the argument?
Nothing structural: the measure now has to be defined for three argument shapes and checked on every edge, including any shortcut that closes the loop early. Three-member cycles are where hand-checking fails, because verifying two edges feels like verifying the cycle.
How would you spot mutual recursion in code you did not write?
Follow the call graph rather than the bodies. A function with no self-call can still be recursive, and a search for self-calls reports nothing. Draw the edges between the functions you are reading and look for a cycle; the cycle, not the body, is the thing you have to reason about.

Two people passing a shrinking stack of cards back and forth. The game ends because the stack loses a card on every pass, not because the players take turns.

saying these in an interview costs you the question

Claims two functions calling each other is not really recursion.
Checks termination by reading only one of the two bodies.
Assumes a base case anywhere in the cycle protects the whole cycle.
Says a crossing that keeps the argument the same size cannot terminate.
Thinks which function runs first decides whether the pair terminates.

A turn-based game's two phase functions each end by calling the other; what must decrease for the pair to terminate?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Two definitions, one cycle

What you actually check

When nothing shrinks at one crossing

Self-recursive against mutually recursive

Where the argument usually breaks

▾common follow-ups3 questions

▾analogy~10 s

▾red flags5 flags

Two definitions, one cycle

What you actually check

When nothing shrinks at one crossing

Self-recursive against mutually recursive

Where the argument usually breaks

answer

go deeper