skip to content

What does merging two mutually recursive phase functions into a single tag-dispatched function actually buy you?

level: middleimportance: should knowfreq 42%

answer

  1. one body, one extra parameter
  2. tag replaces which function you called
  3. mutual call becomes self call
  4. signature is the union of both
  5. only helps if calls are tail

basics

~20 s

Every crossing becomes a self-call, so the cycle sits inside one body that a plain loop can replace. You pay for it with a widened parameter list and a branch on the tag chosen at run time.

solid answer

~40 s

You add one parameter — a tag naming which phase is running — and one body that branches on it; each former mutual call becomes a self-call carrying the other tag. The gain is that the cycle now lives inside a single function, so the ordinary tail-call-to-loop rewrite applies again and a reader follows the whole cycle without jumping between definitions. The costs are real: the merged signature is roughly the union of both phases' parameters, so each branch carries arguments that mean nothing to it; the phase is selected by a run-time branch rather than by which function you called; and two names that documented intent collapse into one. It only buys the loop if every call in the cycle was already in tail position.

code

pseudocode · 7 lines
pseudocode
function turn(phase, moves):
    if moves <= 0:
        return "draw"
    if phase == PLAYER:
        return turn(ENEMY, moves - 1)
    else:
        return turn(PLAYER, moves - 1)

go deeper

for a junior

Recognise the shape: one function with a phase argument and a branch on it expresses the same alternation as two functions calling each other.

for a middle

Perform the merge and name both sides of it — the self-call the loop rewrite needs, against a widened signature and a run-time branch on the tag.

for a senior

Judge when it earns its place in a real codebase: reach for it when depth is unbounded, not as a default style, and keep the number of phases small.

for a principal

Set the rule for the team: which cycles must be written in the merged, loop-safe form because the platform promises nothing, and which may stay as named pairs.

## The transformation, step by step Merging a mutually recursive pair into one self-recursive function is mechanical: 1. **Invent a tag** with one value per phase — `PLAYER` and `ENEMY` for the turn loop. 2. **Write one function** whose parameters are the tag plus what both phases needed. 3. **Branch on the tag** at the top and put each original body in its branch. 4. **Rewrite each crossing** as a call to this function carrying the *other* tag. What used to be encoded in *which function was running* is now an ordinary value travelling in an argument. That is the whole idea: the phase moves out of the program counter and into the data. ## What you get - **Every call in the cycle now names the enclosing function.** The local rewrite that flattens self-recursion — reassign the parameters, jump to the top — has a target again, so the merged body can become a loop by hand or by an optimisation that only recognises self-calls. - **One place to read.** The cycle no longer spans two definitions that may sit far apart, and the termination measure is now visibly one function's argument. - **One place to instrument.** A counter, a trace, a guard on the tag sequence goes in once instead of twice. ## What you pay - **A widened signature.** If the phases took different data, the merged function takes the union, and every call site fills in slots the branch it targets will ignore. - **A run-time branch.** Which body runs was previously decided by the call site; now it is decided by comparing a value. - **Lost names.** `walkContainer` and `walkEntry` told a reader what each half was for; `walk(kind, node)` does not. - **A branch that grows.** Two phases read fine. Five phases in one body, each with its own base case, is the shape people mean when they complain about state machines written as one function. | | the mutually recursive pair | the merged tag-dispatched function | |---|---|---| | How is the phase chosen? | by which function the call names | by a branch on the tag value | | Parameters | each phase declares only its own | the union, partly unused per branch | | Base cases | one per function | one per branch, in one body | | Local loop rewrite | does not apply | applies, if every call is in tail position | | Reads as | two named steps | one step with a mode | ## When it is worth it The merge is a fix for a specific problem — an unbounded cycle whose depth is not bounded by the data and whose platform makes no promise about frames across function boundaries. Reach for it when that is the problem you have. Two signs it is not: - **Depth is bounded by the data.** A turn count capped by the rules, a structure that is shallow by construction. Then the pair costs nothing and says more. - **The phases differ substantially.** If the union signature would be mostly-unused slots and the branch would be two unrelated bodies, the merge trades clarity for a property you do not need. One way to soften that is to carry a single tagged payload instead of a wide argument list, so each phase's data travels with its own tag. ## The two ways the merge disappoints The first is expecting it to fix a cycle that was never made of tail calls. If one branch adds to the result of its recursive call, the merge changes nothing about that branch: work is still pending when it returns, and a loop rewrite is not available for it. The merge is a packaging change; it does not remove pending work. The second is expecting it to change which inputs terminate. It does not. The measure that decreased across the crossing now decreases across a self-call, and the tag is precisely the phase component you would have used as a tie-break in the lexicographic argument. If merging appeared to change termination, the cycle itself was changed, not just its packaging — usually because a base case that fired in one function's branch now sits behind a tag test that the other phase does not reach. It is also worth being clear about what the merge does **not** claim. It does not say the paired form was wrong: a great deal of code is more readable as two named mutually recursive functions, and the merge is best understood as the shape you move to when depth, not readability, is the constraint that binds.

  • When would you refuse the merge?
    When depth is already bounded by the data, so there is no problem to fix, or when the two phases take genuinely different inputs and the merged signature becomes a union nobody can read. The merge buys a loop-safe shape; if you do not need that shape, two named functions communicate more.
  • The merged function now takes arguments only one branch uses. What can you do about that?
    Carry one tagged payload rather than a wide argument list, so each phase's data travels with its own tag and the branch destructures a single value. Adding a phase then adds a variant instead of another mostly-unused parameter.
  • Does the merge change which inputs terminate?
    No. The decrease that held across the crossing now holds across a self-call, and the tag is the phase component a lexicographic measure would have used anyway. If termination appears to change, a base case moved behind a tag test that some phase no longer reaches — the cycle changed, not just its packaging.

saying these in an interview costs you the question

  • Claims the merge removes frames even when a call is not in tail position.
  • Ignores the widened, partly meaningless parameter list the merge creates.
  • Merges five phases into one branching body and calls it readable.
  • Says the merged function is no longer recursive because one name remains.
  • Presents the merge as a pure win with no readability or typing cost.