skip to content

Walking a structure whose levels alternate between container and entry, why write two mutually recursive functions instead of one?

level: seniorimportance: nice to knowfreq 32%

answer

  1. alternation is in the data
  2. call graph mirrors the levels
  3. one kind per function
  4. no run-time re-check of level
  5. measure still spans both bodies

basics

~20 s

Because the alternation is a fact about the data, and two functions put it in the call graph: each receives exactly one kind of level, carries its own termination condition, and never has to re-establish where in the structure it is.

solid answer

~40 s

A container holds entries; an entry may hold a container. Written as a mutually recursive pair, `walkContainer` and `walkEntry` each take one kind of level, so each has one set of preconditions and one termination condition, and the legal transitions between levels are simply the call edges — a container directly inside a container is a shape for which no call exists. A single function taking either kind must branch on what it received, and that branch is reachable for inputs the format forbids, so the impossible case has to be handled, ignored or asserted away somewhere. What the pair costs is two entry points, some shared logic to factor out, and a termination argument that spans both bodies instead of one.

code

pseudocode · 8 lines
pseudocode
function walkContainer(container):
    for each entry in container.entries:
        walkEntry(entry)

function walkEntry(entry):
    record(entry.value)
    if entry.child is present:
        walkContainer(entry.child)

go deeper

for a junior

Notice that a function can be recursive without calling itself: follow the calls between the two walkers and the cycle appears.

for a middle

Explain what one input kind per function buys: its own termination condition, and transitions expressed as calls rather than as branches inside one body.

for a senior

Argue the trade in review — a call graph that mirrors the format, against two entry points and a termination argument that no longer fits in one body.

for a principal

Decide the house shape for traversals over alternating formats, since whoever adds the next level kind will copy whatever pattern is already in the file.

## The data alternates, so the code can too Some structures alternate by construction: a container level whose children are entries, and an entry level whose child, if any, is another container. Configuration trees, tabular documents with grouped rows, menu structures and record formats with repeated groups all have this shape. The alternation is not incidental — it is part of what makes the format well formed. Two containers cannot nest directly, and an entry cannot hold an entry. A **mutually recursive pair** expresses that directly: one function per level kind, and a call from each into the other. `walkContainer` iterates entries and calls `walkEntry`; `walkEntry` records the entry and, when it has a child, calls `walkContainer`. Neither calls itself, and together they walk arbitrarily deep alternating structure. ## What the pair puts in the call graph - **Each function has one input kind.** Its preconditions are about that kind only, and a reader opening it does not have to ask which level it might be on. - **Each function has its own termination condition.** For the container walker it is an entry list with nothing in it; for the entry walker it is an entry with no child. Neither needs to know about the other's. - **The legal transitions are the edges.** Container to entry and entry to container are written; container to container is not written, so it cannot be taken. - **The impossible case is absent rather than handled.** There is no branch for it to hide in, no unreachable arm to keep correct as the code changes. ## The single-function alternative One function taking either kind of node has to open with a test on what it got, then do one of two things. That works, and it is shorter. What it changes is where the alternation lives: | | one function per level kind | one function with a kind test | |---|---|---| | Where the alternation is stated | in the call graph | in a branch inside the body | | What each entry point accepts | one kind | either kind, at any level | | Impossible nesting | has no call edge | reaches a branch that must do something | | Termination condition | one per function | both, side by side in one body | | Cost of adding a level kind | a function and its edges | another arm and another test | Neither column is wrong. The judgment is about which one you want a future reader — and a future contributor adding a level kind — to meet first. ## What the pair costs Be honest about the other side. Two entry points mean a caller has to pick the right one, and calling the entry walker with a container is a mistake the pair does not prevent by itself. Logic the two halves share has to be factored into a helper both call, or it gets duplicated. And the **termination argument now spans both bodies**: you need a measure that shrinks along every edge, typically the size of the sub-structure being passed down, and you have to check the container-to-entry edge as carefully as the entry-to-container one. A single self-recursive walk needs that same proof with one edge instead of two, which is genuinely less work. There is also a limit to what the split buys on input you did not build. If the structure arrives from outside — parsed, deserialised, supplied by a caller — something still has to establish that it really does alternate. The pair keeps that check at the boundary instead of repeating it at every level, which is the benefit; it does not make the check unnecessary. ## Choosing in review A few rules of thumb that hold up: 1. **Split when the levels genuinely differ** — different fields, different results, different termination conditions. Then each function is small and total over its own input. 2. **Keep one function when the levels barely differ.** If the two arms would be near-identical, the alternation was not carrying much information, and one function over a tagged value reads better. 3. **Factor shared work into a plain helper**, not into a merge. Merging the pair only to share code trades a clear call graph for a branch. 4. **Write the termination argument down somewhere** — a comment naming the measure is cheap, and it is the part of the pair that a later reader is least likely to reconstruct. The deeper point is that mutual recursion is not only a stack-shape curiosity. It is the natural code shape for data whose kinds alternate, and choosing it is a modelling decision: you are saying that the alternation is real enough to be worth encoding in which function gets called.

  • The structure grows a third alternating level kind. Does the shape still hold?
    It scales the same way: one function per kind, with a call edge only where the format allows that transition. The cost is more entry points and a termination argument spanning a longer cycle, so past three or four kinds a single function over a tagged value usually reads better — especially once the kinds share most of their logic.
  • How does the termination argument differ from a single self-recursive walk?
    It has to cover both bodies. Pick a measure — usually the size of the sub-structure passed down — and show it strictly decreases on the container-to-entry edge as well as on the entry-to-container one, or tie-break on the level kind. The self-recursive walk needs the same proof over one edge.
  • The two walkers turn out to share most of their work. What now?
    Pull the shared part into a helper both call and keep the alternation in the pair. If almost everything is shared, that is evidence the alternation was not carrying much, and one function over a tagged value is the more honest shape.

saying these in an interview costs you the question

  • Says two functions are always more code, so one with a flag is simpler.
  • Claims the pair removes every run-time kind check, even on input you did not build.
  • Assumes the pair terminates because each function is short.
  • Treats the two entry points as interchangeable for any level.
  • Forgets the termination measure must hold on both edges of the cycle.