Why does a comment walker that recurses only into each comment's own replies need no depth counter?

## Termination that you read off the call sites A walker over a nested comment thread recurses into two places: the reply list a comment carries, and the rest of the list the comment sits in. Both are **parts of the value the call was given**. Neither is the value itself, and neither is a new value assembled from it. That single property is the whole termination argument. A part of a finite value is strictly smaller than the whole in a sense nobody has to compute: it has strictly fewer constructors in it. Each call therefore works on a strictly smaller value than its caller, and a finite thread contains only finitely many parts, so no chain of calls can go on forever - every path down the thread runs out of structure and lands on the empty list. The important word is **read**. The argument is checked by looking at what is passed at each recursive call site and asking one question: *is this something the current value already carries?* If the answer is yes everywhere, the descent terminates, and no one has to simulate the walk or reason about how deep real threads get. ## What a depth counter is, and what it is not A counter threaded through the calls and decremented each time is a different kind of guarantee entirely: | | Recursing on parts | Recursing with a depth budget | |---|---|---| | Where the guarantee lives | in the shape of the value | in a number someone chose | | What a reviewer checks | that each argument is a part | that the number is large enough for real data | | Behaviour on unusually deep data | walks all of it | stops early and returns a partial answer | | Effect if the argument was not shrinking | not applicable - it is | hides the bug: the walk stops but the answer is wrong | | Cost of changing the data | none | the number has to be revisited | The last two rows are the ones that matter in review. A budget makes a non-terminating walk *look* fine, because it stops. It converts a control-flow bug into a silently truncated result, which is strictly harder to notice than a hang. And the number is a standing liability: it encodes an assumption about the data that nothing in the code enforces and nothing tells you when it becomes false. That is not an argument that guards are never justified. A thread arriving from outside the system might not be a finite tree at all - a value that refers back to itself is not a value the inductive definition describes, and a walker written against that definition inherits its assumption. The point is where the guard belongs: at the boundary that validates the input, once, rather than smeared across every recursive function that touches the data. ## The property, stated precisely Three conditions do the work together, and it is worth separating them: 1. **The value is finite and built from the listed ways.** No value contains itself, directly or through a chain. 2. **Every recursive argument is a proper part of the current argument.** Not equal to it, not derived from it - contained in it. 3. **Every way of building the value has a case**, including the way that carries no parts. Drop the first and there is nothing to descend through. Drop the second and the descent may never shrink. Drop the third and the descent shrinks to something the walker cannot answer for. With all three, termination is not a property anyone has to test for; it follows from how the value was built. ## Where engineers get this wrong - **Treating "smaller" as "smaller in some number I can measure".** A value with fewer comments in it is not automatically a part of the original. Size and containment are different relations, and only containment is free to check. - **Believing the counter is the safety net.** If both recursive arguments are parts, the counter is dead weight; if one of them is not, the counter changes a hang into a wrong answer. - **Reaching for a budget after one production incident on cyclic input.** The right response is to establish at the boundary that the input really is the finite shape the definition promises, so every walker downstream inherits it. - **Assuming termination implies cheapness.** The walk finishes, but it still visits every comment, and the frames it stacks up follow the thread's nesting depth. Termination is one property; cost and depth are others.