skip to content

In a comment thread walker, why is recursing on the thread minus one comment not structural?

level: middleimportance: should knowfreq 46%

answer

  1. selected out, or constructed from?
  2. a part, not a smaller cousin
  3. it still terminates - on what measure?
  4. the claim moved into the removal
  5. rebuild cost, once per round

basics

~20 s

The thread minus one comment is a new value built from the old one, not a part the old one carries. It may well shrink, but only on a size measure someone has to check by hand - the shape no longer guarantees anything.

solid answer

~40 s

Structural recursion recurses on **components** - the reply list a comment holds, the rest of the list it sits in. "The thread with that comment removed" is neither: it is a fresh value assembled by rebuilding the thread around a hole. Such a walker usually still terminates, because each round really does remove one comment, but the argument for that has moved out of the data and into a claim about a size measure that a reader must verify and a future edit can break - filter on the wrong predicate, or remove nothing when the comment is absent, and the walk spins. The structural version needs no such claim: a part is smaller because it is a part. This is the difference between structural recursion and general recursion that merely happens to terminate.

code

pseudocode · 6 lines
pseudocode
function scanThread(thread)
    if thread is empty
        return 0
    c       = pick the newest comment anywhere in thread
    smaller = thread with c removed          // rebuilt, not a part of thread
    return 1 + scanThread(smaller)

go deeper

for a junior

Know the test: is the recursive argument a piece the value already carries, or something the code just built? Only the first is structural recursion.

for a middle

Explain that the rebuilt version still terminates, but on a hand-checked size measure rather than on the data's shape, and name the removal behaviour that would break it.

for a senior

Point at the review and cost consequences: the guarantee is no longer local to the call site, and rebuilding once per round turns a single pass into repeated reconstruction.

for a principal

Decide when a team may write general recursion at all, and what it must supply when it does - an explicit termination argument in review, since the free one from the data is gone.

## Component versus rebuilt value The two walkers look similar and are not the same kind of thing. A **structural** call passes something the current value already contains. Handed a reply list, it passes that list's first comment's own replies, or the rest of the list. Those pieces existed before the call; the walker merely selected one. A call on "the thread with the newest comment removed" passes something that **did not exist until the walker made it**. The thread is rebuilt around a hole. The result may be smaller, may be the same size if the comment was not there, and is in any case a new value whose relation to the input is whatever the removal logic happens to implement. | | Recursing on a component | Recursing on a rebuilt value | |---|---|---| | Where the argument comes from | selected out of the input | constructed from the input | | Why it is smaller | it is a part - strictly fewer pieces | because a removal is claimed to always drop one | | Who checks that | the reader, by looking at the call site | the reader, by reasoning about the removal | | Cost per call | selecting a part | rebuilding the structure | | What a later edit can break | nothing about termination | the shrinking claim, silently | ## It terminates - that is not the objection This matters because the usual criticism is overstated. A walker that genuinely removes one comment per round on a finite thread **does** finish: the number of comments strictly decreases and cannot go below zero. Calling it broken is wrong. What it has lost is *where the guarantee lives*. Three consequences follow: 1. **The termination argument is now an obligation on the removal.** "Removes exactly one, always" is a claim about another function's behaviour. If the comment being removed is identified by a predicate that can match nothing, the round removes nothing, the next round is handed the same value, and the walk never ends. 2. **A reviewer has to leave the walker to check it.** Structural descent is checkable at the call site. Here the reader has to open the removal, confirm it shrinks in every branch, and confirm nothing downstream will change that. 3. **The cost profile changes.** Rebuilding the thread each round is work proportional to the thread, repeated once per comment, where the structural walk selects a part and moves on. ## The general shape of the mistake The same substitution shows up in several disguises, and all of them share one tell - the recursive argument is *computed* rather than *selected*: - passing the thread "after this comment" recomputed by searching for it, instead of the rest of the list the walker already holds; - passing a flattened copy of the thread, which throws away the very nesting the recursion was following; - passing the value re-read from its source with a different filter applied, so the code has no visible relation between call and caller at all; - passing the same value with an extra flag set, where shrinking is claimed for the flag rather than for the data. The cure is the same in every case: find the piece the current value already carries, and pass that. If no such piece exists, the function is not a structural recursion over this type, and it should be written and reviewed as ordinary recursion whose termination is argued explicitly - a legitimate thing to write, just not a thing that gets the shape's guarantee for free. ## Saying it precisely in an interview The answer that lands has three beats. First, name the relation: structural recursion recurses on *components*, and a rebuilt value is not a component. Second, refuse the overstatement: this particular walker probably does terminate, on a decreasing count of comments. Third, say what was traded: a guarantee readable at the call site has become a claim about another function that a reviewer must verify and a future change can quietly invalidate - plus a rebuild per round that the structural version never pays.

  • If it terminates anyway, what has actually been lost?
    Checkability and cost. Termination now depends on the removal shrinking the thread in every branch - a claim a reviewer must verify elsewhere and a later edit can break without touching the walker. And each round rebuilds the thread, so the same traversal costs far more than selecting a part.
  • What would make that walker fail to terminate?
    A removal that can drop nothing. If the comment is identified by a predicate that matches nothing - already deleted, or never present - the round returns an equally large thread, the next call sees the same value, and the descent never shrinks. The structural version cannot reach that state.
  • Is a recursion on a rebuilt value always the wrong choice?
    No. Some problems genuinely have no component to descend on, and ordinary recursion with an explicit termination argument is the honest way to write them. The mistake is believing such a function inherits the shape's guarantee; it needs its own argument, written down and reviewed.

saying these in an interview costs you the question

  • Says the rebuilt-argument walker cannot terminate at all
  • Treats "fewer comments" as the same thing as "a part of"
  • Thinks flattening the thread first keeps the recursion structural
  • Ignores that each round rebuilds the whole thread
  • Assumes any recursion that finishes is structural recursion