How do you decide whether a recursive parser over user-supplied nested data must be rewritten iteratively?

## Reframe it as a budget, not a taste Arguments about recursion versus iteration usually get conducted as style debates. At the level where you set policy for a codebase, the question is narrower and answerable: **is the recursion depth bounded by something I control?** Recursion depth is space — one frame per call in progress — and the number of calls in progress equals the nesting depth of the structure being walked. So the depth of your recursion is a property of the *input*, not of your code. That gives a clean test: - The depth is bounded by a structure you maintain (a balanced index whose height is logarithmic, a schema with a fixed number of levels, a fan-out you generate): recursion is safe and readable, keep it, and write the bound down next to the code. - The depth is set by data that crosses a trust boundary (a document a client uploads, a configuration file, a comment thread users nest themselves, a graph imported from elsewhere): the depth is unbounded by construction, and the fixed stack ceiling becomes something an outside party can reach on demand. The second case is a memory-safety and availability question. A stack overflow is not a graceful degradation: it terminates the thread, often the process, and it does so in the middle of whatever else that worker was doing. ## The three mitigations, and what each costs **1. Bound the input.** Publish a maximum nesting depth, validate it before parsing, and reject beyond it. This is the cheapest option by a wide margin: the recursive code stays as readable as it was, the failure becomes a clear validation error attributable to the caller, and the depth limit is a documented part of the contract rather than an emergent property of a thread's stack size. It requires that you are allowed to set that contract — which for an internal service or a public API you version is usually true, and for "we must ingest whatever the partner sends" is usually not. **2. Move the pending work to the heap.** Keep the same traversal, but hold the not-yet-processed nodes in a data structure you allocate rather than in call frames. This does **not** reduce the space complexity — it is still O(depth) — and that is the point people miss. What changes is which region pays: the fixed per-thread stack, typically about a megabyte, versus the general heap, which is usually gigabytes and shared. Practically, the depth you survive rises by two or three orders of magnitude, and exhaustion becomes a memory error you can observe and turn into a failed request instead of a dead worker. The cost is real: the rewritten walk is harder to read, easier to get subtly wrong, and every future maintainer pays a small tax. Budget for tests that pin the traversal order. **3. Give the thread a bigger stack.** Tempting because it is a one-line configuration change. It multiplies: stack is reserved per thread, so a fleet running hundreds of concurrent workers multiplies the increase by the concurrency, and it competes with the heap for the same machine. And it does not remove the cliff — it moves it, so an adversary or an unlucky document simply nests deeper. Legitimate as a stopgap for one known workload with bounded concurrency; not a policy. ## The organisational call Decide with four questions, in this order: 1. **Who sets the depth?** If it is you, option 1 and stop. This is the answer most of the time and teams skip past it because rewriting feels more like engineering than validating does. 2. **What is the blast radius?** One failed request is very different from a worker that dies mid-batch, and different again from a process whose crash restarts a stateful component. The worse the blast radius, the more the rewrite is worth. 3. **What is the concurrency multiplier?** A cost paid per worker on a large fleet is a fleet-sized cost. This is what disqualifies option 3 in most services. 4. **Who maintains this in a year?** The clever iterative walk is a permanent tax on the team; the depth cap is a line of validation. If the recursive version is being read weekly by people who did not write it, that weighs against option 2 and toward option 1. ## What to say when you are challenged If someone argues the recursion is fine because "real documents are never that deep", the answer is that the depth is not a statistical property of typical traffic — it is a choice available to whoever sends the input. Everyday inputs being shallow is exactly why the failure only shows up under an unusual or hostile one, and why it shows up in production rather than in tests. If someone argues the rewrite is always right, the answer is that it is still O(depth) space, it merely relocates it, and paying permanent readability cost to relocate a cost you could have simply refused to accept is a bad trade. The rule worth writing down: recursive walks are allowed over structures whose depth your system bounds; anything walking externally-shaped data either validates a depth limit up front or keeps its pending work off the call stack.