A recursive directory-tree walker overflows the stack on one customer's deeply nested tree - how do you tell unbounded recursion from legitimately deep recursion, and what do you change?
answer
- read the repeating pattern first
- same arguments means no progress
- a cycle in the data is unbounded
- deep input versus missing base case
- explicit work list, then bound the depth
basics
~20 sRead the failing stack. A short cycle of frames repeated to the limit, with arguments that never progress, means the recursion has no reachable base case - fix the termination or the cycle in the data. Many distinct frames tracking real input depth means the input is genuinely deep, so move the pending work into a heap-held work list and bound the depth explicitly.
solid answer
~50 sBoth failures raise the same fault, so start with the evidence. Unbounded recursion shows a short cycle of the same frames repeated all the way to the limit, with arguments that do not converge - often because the data has a link back to an ancestor, so no depth is ever enough. Legitimately deep recursion shows thousands of distinct frames whose arguments march through the input, and it fails only on the deep inputs. The fixes are different in kind. For the unbounded case, repair the termination condition or detect the cycle by remembering the nodes on the current path; a bigger stack only delays the crash. For the deep case, stop using call frames as storage: keep an explicit work list of pending nodes, which lives in a far larger budget and can be measured, and add an explicit depth limit that fails with a clear message rather than a fault.
code
pseudocode · 15 lineswork_list <- new stack // pending nodes live as data, not as frames
push(work_list, (root, 0))
while work_list is not empty:
(node, depth) <- pop(work_list)
if depth > MAX_DEPTH:
report_too_deep(path_of(node)) // explicit, catchable, names the input
continue
if node is a directory:
for each child in children_of(node) in reverse order:
push(work_list, (child, depth + 1))
else:
visit(node)go deeper
Know that an overflow has two possible causes - a recursion that never stops, or an input deeper than the stack allows - and that the failing stack tells you which.
Explain the discriminator: repeated frames with unchanging arguments mean no progress toward a base case, while distinct frames tracking the input mean the depth is real.
Drive the whole diagnosis in an incident: read the stack, reproduce the cheap case, then apply the matching fix - cycle detection for unbounded walks, an explicit work list with a depth limit for deep ones.
Decide the policy: which inputs may set recursion depth at all, where those limits are declared and reported, and when a clearer recursive form is worth keeping because the arithmetic already clears the accepted worst case.
## Two different failures, one symptom A stack overflow is a symptom, not a diagnosis. Two unrelated defects produce it: - **Unbounded recursion**: the base case is never reached. Either the termination condition is wrong, or the data contains a cycle - a link in the tree that points back at one of its own ancestors - so the walk descends forever through a structure that is not really a tree. - **Legitimately deep recursion**: the code is correct and the input genuinely nests deeper than the thread's frame budget allows. They feel similar in an incident and they are fixed in opposite directions, so the diagnosis has to come first. ## Reading the failing stack | | unbounded recursion | legitimately deep recursion | |---|---|---| | frame pattern | a short cycle repeated to the limit | thousands of distinct frames | | arguments | unchanged, or not converging on a base case | progressing through the input | | input dependence | fails on one input class, however small | fails only on the deep inputs | | reproducibility | reproduces on a tiny cyclic example | needs an input of roughly the observed depth | | what a bigger stack buys | nothing; it crashes later at the same place | a constant factor, not a guarantee | The fastest discriminator is the argument at each level. If the node being visited at level 900 is the same node that was visited at level 3, the structure has a cycle and the recursion is unbounded. If each level names a different child of the previous one, the walk is doing exactly what it was asked to do against an input nobody sized for. ## Fixing the unbounded case 1. **Repair the termination condition** if the bug is in the code - a decrement that does not happen, a branch that recurses on the same value it was given. 2. **Detect cycles in the data** if the bug is in the input: keep the identity of the nodes on the current path, refuse to descend into one already there, and report it as bad input rather than crashing. 3. **Never treat the stack size as the fix.** It converts an immediate crash into a later one and hides the defect behind a configuration value. ## Fixing the deep case The move is to stop using call frames as the storage for pending work. An explicit **work list** - a stack of nodes still to visit - holds exactly the same information, but as data rather than as frames: - It draws on a much larger and separately managed budget instead of a small fixed per-thread one. - Its size is a number you can read, log and limit, whereas frame usage is invisible until it faults. - The depth limit becomes an ordinary comparison that can fail with a message naming the offending path, instead of a fault at an arbitrary instruction. - The traversal order changes unless you are careful: popping from a stack visits the most recently pushed child first, so push children in reverse if the original order mattered. What the rewrite does **not** do is make the memory free. A million pending nodes is a million entries somewhere; you have moved the cost to a budget that can absorb it and that you can observe, which is the point. And the rewrite is not automatically warranted: if the arithmetic says the recursive form clears the worst input you accept by a wide margin, recursion is clearer and should stay. ## Why catching the fault is not a strategy The fault arrives at whatever instruction happened to push past the limit, which may be in the middle of updating a structure that is now half-modified. Any handler also needs stack space of its own, on a stack that just ran out. Treat the overflow as fatal for that unit of work, fail it cleanly, and fix the bound - retrying the same call on the same input simply reproduces it.
- The tree turns out to contain a link pointing back at one of its own ancestors. Which category is that, and what fixes it?Unbounded: the structure is a graph, not a tree, so no depth is ever sufficient and no stack size helps. Track the identity of the nodes on the current path, refuse to descend into one already present, and surface it as invalid input naming the offending link.
- Why is catching the overflow and retrying a poor recovery strategy?The fault lands at an arbitrary instruction, so whatever the thread was updating may be half-written, and any handler needs stack space on a stack that has just run out. Fail the unit of work cleanly and fix the bound; a retry on the same input reproduces the same crash.
- Does converting the walk to an explicit work list remove the memory cost?No - it relocates it. The pending nodes still occupy memory, but in a budget that is far larger, separately managed, and measurable, and the limit becomes an ordinary comparison you can fail on with a clear message instead of a fault you cannot control.
saying these in an interview costs you the question
- Raises the thread stack size as the first and only response to any overflow
- Assumes every overflow means a missing base case, never a legitimately deep input
- Thinks an iterative rewrite removes the memory cost rather than relocating it
- Treats a caught stack-overflow fault as a condition to retry and continue
- Cannot say what a short repeating cycle of frames reveals about the cause