Recursion overflows on deeply skewed input: how do you choose between an explicit stack, reshaping the data, or capping depth?

## Frame the decision before comparing the options The engineering question is not "which technique is best" but "which property do we want to own". Three questions decide it: 1. **Is depth bounded by anything we control?** If chain length or skew is dictated by data we accept from outside, any option that leaves depth proportional to input is a threshold, not a fix. 2. **What is the blast radius of a failure?** Losing one record's parse is annoying; losing the execution context that was doing unrelated in-flight work is an outage. That difference changes how much you will pay for a real fix. 3. **Who maintains this in two years?** A clever structure that only its author can modify is a liability priced in future incidents, not in this quarter's effort. ## Option 1 — reshape the data so depth stops tracking input Make the structure or the traversal unable to go deep: segment a long chain into bounded runs processed in sequence with an accumulator, keep the structure balanced at write time, or split oversized units at ingest so nothing downstream ever sees the pathological shape. - **Strength:** this is the only option that *retires the failure class*. Afterwards, no input size produces the crash, and depth stops being a thing anyone must remember to check. - **Cost:** it usually touches the data contract, which means producers, stored data and possibly a migration. If writes cannot pause, that migration is a dual-write-and-backfill exercise with its own risk, and it will not land this week. - **Choose it when** the data path is yours, the skew is not exotic, and the component is long-lived enough to be worth the migration. ## Option 2 — move the pending state off the call stack Keep the algorithm and hold the pending work explicitly in a heap-allocated structure instead of in activation records. - **Strength:** behaviour is preserved, no producer is affected, and the linear state moves to a region orders of magnitude larger whose exhaustion is a far more manageable condition than an aborted execution context. It is entirely under your team's control and ships without coordination. - **Cost:** it does not reduce the asymptotic space — O(n) state is still O(n), just somewhere else. And it converts control flow the reader used to get for free into control flow that must be written, reviewed and understood. Every future change to the traversal now costs more, and reviewers who are not fluent in it will approve subtly wrong versions. - **Choose it when** the data shape is genuinely out of your control, the traversal is stable and unlikely to churn, and the team has the depth to maintain it. ## Option 3 — cap the input and reject beyond it Enforce an explicit limit and refuse work above it with a clear, attributable error. - **Strength:** cheapest by a wide margin, ships today, converts an unrecoverable crash into a handled rejection, and closes the availability risk if outsiders can influence the shape. It also forces a valuable conversation nobody has had: *what size do we actually promise to support?* - **Cost:** it pushes the problem to callers and can silently drop legitimate work if the limit was picked from yesterday's traffic rather than from a real requirement. It is a policy, and policies need an owner and a review date. - **Choose it when** you need safety now, or as the permanent guard rail underneath whichever structural option you also pick. ## The non-option: enlarge the region and move on A bigger stack region multiplies the tolerable depth by a constant. Against input that grows without bound, a constant factor is a delay, not a solution — and it is the most dangerous choice politically, because it closes the incident while leaving the property intact. Everyone stops worrying, the alarm nobody added never fires, and the next crossing arrives with less institutional memory than the last. Use it overnight, attach a depth alarm, and give it an expiry date in the same ticket. ## Sequencing beats purity Mature answers usually stage the work rather than choosing one option forever: cap and reject immediately to stop the bleeding, add a peak-depth metric so the risk becomes visible, then decide between relocating the state and reshaping the data based on how much of the pipeline you own. Say that sequence out loud — an interviewer at this level is listening for whether you can protect production this week and still fix the class this quarter. ## What you owe the team regardless of the choice Whatever you pick, leave behind three artifacts: a **stated bound** (the maximum depth or size this component supports), a **test that actually exercises it**, and a **metric with an alarm** below the ceiling. Without those, the next person cannot tell whether the current headroom is deliberate or accidental — and an invariant nobody can verify is not a fix, it is a belief.