Both phase functions of a turn loop end in a tail call to each other — why does the usual tail-call-to-loop rewrite not fire?
answer
- tail call versus tail-call elimination
- the rewrite is a local jump
- jump target is another body
- self-call optimisation does not fire
- merge the bodies under a tag
basics
~20 sThat rewrite is local: it turns a call to the enclosing function into reassigned parameters and a jump to the top of the same body. A mutual call's target is a different body, so no such jump exists.
solid answer
~40 sThe calls really are tail calls — being one is a property of the call site, and nothing remains to do after either returns. What is missing is the elimination. The classic rewrite recognises a call to the *enclosing* function: the next body is the body you are already in, so the frame can be reused by assigning the new argument values to the current parameters and jumping to the top. Cross a function boundary and that shortcut has no target — the next body is somewhere else, with its own parameter list. Whether the running platform reuses a frame for a call that leaves the function is a property of that platform, not something a local rewrite of either body can give you.
code
pseudocode · 11 lines// self tail call: the rewrite is local
function countdown(n):
if n <= 0:
return "done"
return countdown(n - 1) // jump to the top of THIS body
// mutual tail call: the target is elsewhere
function playerTurn(n):
if n <= 0:
return "draw"
return enemyTurn(n - 1) // no top of this body to jump togo deeper
Know the term: a call is in tail position when nothing is left to do once it returns, and both phase functions here qualify.
Explain the gap between being a tail call and having the frame eliminated, and why the local self-call rewrite has no jump target across two bodies.
Say what you would rely on in production: check whether the guarantee is actually stated, and choose a shape that does not depend on it when it is not.
Decide whether correctness may rest on a platform property at all, or whether cycles should be written in a form that is safe on every target you ship to.
## A tail call and a tail-call elimination are two different things A call is **in tail position** when nothing remains to be done in the caller once it returns: its result is the caller's result, with no arithmetic, no wrapping, no cleanup waiting. That is a property of the call site, readable from the source. Both phase functions of the turn loop qualify — `return enemyTurn(n - 1)` leaves nothing pending. **Tail-call elimination** is what happens to that fact: the current frame is reused instead of a new one being pushed. That is a property of whatever runs the code, or of a rewrite you perform by hand. Most of the confusion in this area comes from collapsing the two, and mutual recursion is precisely where they come apart: the calls are unimpeachable tail calls, and the familiar rewrite still does not apply. ## Why the self case is a local rewrite When a tail call names the enclosing function, the next body to run is the body already executing. Reusing the frame is then indistinguishable from a two-step edit anyone can perform on the source: 1. Assign the new argument values to the current parameters. 2. Jump back to the top of this body. Nothing outside the function is consulted, no other signature is involved, and the result is an ordinary loop. This is why a single tail-recursive function is such a well-behaved shape, and why a check attached to a declaration can verify it: everything it needs to see is inside one body. ## What the mutual case asks for instead Now the target is the other function. Three things the self case relied on are gone at once: - **There is no top of this body to jump to.** The next instruction lives in a different body. - **The parameter lists differ.** "Reassign the parameters" has no meaning when the next body's parameters are not these parameters. - **The phase is held in the program counter.** Which function you are in *is* the state that says whose turn it is, and a loop over one body has nowhere to keep that except an explicit value. | | tail call to the enclosing function | tail call to the other function in the cycle | |---|---|---| | Is it a tail call? | yes | yes | | Where does control go next? | the top of this body | another body entirely | | Reusable by a local source rewrite? | yes — reassign and jump | no — the jump target is elsewhere | | What can remove the frame? | the rewrite, or a self-call optimisation | only general elimination by the platform | | What you can do in the source | write the loop | merge the bodies under a phase tag | ## What this leaves you at the source level The practical consequence is that you cannot fix the cycle by editing either body in isolation, and you cannot infer from "these are tail calls" that the cycle runs flat. Three source-level moves remain open, and they differ in what they cost: 1. **Merge the cycle into one body** that self-calls with a phase tag naming which half runs next. Every crossing becomes a self-call, so the local rewrite applies again and the merged body flattens to a loop. 2. **Return a description of the next step to a driver loop** rather than calling it. That is a distinct technique with its own trade-offs. 3. **Establish that depth is bounded by the data** — a turn budget capped by the rules, a structure of known shallow depth — and leave the pair alone. Option 3 is the one teams skip and then regret; it is also the cheapest when it holds, because it is an argument rather than a rewrite. ## Two traps worth naming The first is reading "tail call" as "free". The property is necessary for elimination and not sufficient for it; what it guarantees is that nothing in *your* code needs the frame, not that the frame goes away. The second is expecting a declaration-site tail-recursion check to cover the pair. Such a check reasons about the marked function's own calls, so a cycle that leaves the function is outside what it can rewrite — it may simply report that the function is not self-tail-recursive, which reads as a false alarm until you notice it is telling the truth. And a prerequisite worth re-checking before any of this: if one call in the cycle is **not** in tail position — a score is added to its result, a log line runs after it — then that lap keeps work pending no matter what anything else does. Elimination talk applies to calls in tail position only, and a cycle is only as flat as its worst edge.
- If the platform does eliminate every tail call whatever the target, does the mutual pair behave like a loop?For frame growth, yes: each crossing reuses the frame and depth stays flat. The source still shows two functions and control still jumps between two bodies; what disappears is the accumulation, not the cycle. You cannot assume it, so where the guarantee is not stated, write the shape that does not need it.
- One of the two calls is not in tail position. What does that change?That lap keeps work pending after the call returns, so a frame is needed for it regardless of any elimination. No merge and no platform feature removes it; you either restructure that body so nothing waits on the call, or you accept the depth and bound the input.
- Why does merging the two bodies bring the loop rewrite back?Because it restores the condition the rewrite needs: after the merge, every call in the cycle names the enclosing function, so the next body is the current body. The phase that used to be encoded in which function was running becomes an ordinary argument, which is exactly what a single loop can carry.
saying these in an interview costs you the question
- Says the mutual calls are not tail calls at all.
- Assumes any call in tail position costs no frame, whatever the target.
- Believes reordering or renaming the two functions makes it a loop.
- Expects a declaration-site tail-recursion check to accept the pair.
- Claims the shape never matters because tail calls are always eliminated.