A recursive DFS labeling pixel regions crashes on a large scan — how do you diagnose and fix it?

## Diagnosing it, before changing anything The crash is not "the image is too big". Correlate failures against the size of the largest **connected** region: - A large scan covered in many small separate marks labels fine, however many pixels it has in total, because each traversal only descends through one region. - A small scan containing one big connected blob crashes, even though total pixel count is modest. That correlation is the fingerprint of recursion depth, not of memory pressure in general. A second confirmation is the failure's determinism: the same input fails at the same point every time, and it fails deeper on inputs with larger regions. ## Why the depth is so large The intuition that trips people up is geometric: "neighbouring pixels are one step apart, so surely the depth is about the region's width". It is not. Depth-first search commits to one neighbour and keeps going, only unwinding when it hits a dead end. On a grid of same-coloured pixels it snakes through the region, and the current path can cover nearly every pixel in it before the first return. So the recursion depth is bounded above by the number of pixels in the region, and in practice it approaches that bound for compact blobs as well as for long thin ones. A worst case is easy to see with a single-pixel-wide winding path: the depth is then exactly the region's size, with no branching at all. Against that, a call stack is a fixed-size allocation. Its capacity is measured in thousands to tens of thousands of frames — the exact figure varies by platform and by frame size, but it is nowhere near a million. Adding a bigger stack to the process buys one order of magnitude and moves the failure to a slightly larger image; it does not remove it. The review-time framing matters more than the fix. This is an **input-controlled depth**: whoever supplies the image chooses how deep the recursion goes. An unbounded recursive walk over user-supplied data is a defect on its own terms, before anyone measures a limit. ## The fix: pending work in a structure you own Move the pending vertices out of call frames and into an explicit stack that you allocate and can grow. Two details decide whether the rewrite is correct. **Where you mark.** The straightforward version marks a pixel when it is popped, which means the same pixel may sit on the stack several times — pushed once by each already-processed neighbour. That is why the loop needs a skip test immediately after the pop. Without it, pixels are processed more than once and the labeling can double-count. The alternative is to mark at push time, which keeps at most one entry per pixel and bounds the stack at the region's vertex count; the cost is that the visit sequence is no longer the same order the recursive version produced. **How much it holds.** With mark-on-pop, peak stack entries are bounded by the number of edges considered — for four-neighbour adjacency, at most about four entries per pixel. This is not free, but it is ordinary growable memory rather than a fixed-size call stack, so it degrades into a memory-pressure question you can measure instead of an abrupt crash. ## What you give up, and when it matters For region labeling, visit order is irrelevant: every pixel of the region gets the same label, and any order that reaches all of them is correct. That is why mark-on-push is perfectly acceptable here and is usually the better choice — one entry per pixel, no skip test needed on pop. It stops being acceptable when the traversal's *order* is load-bearing — when you need the entry sequence the recursive version produced, or a finish time per vertex. Reproducing those with an explicit stack means keeping per-vertex iteration state (which neighbour comes next) so a vertex can be re-visited on the way back out, rather than pushing all neighbours at once. That is a genuinely more intricate loop and is worth writing only when the ordering is actually required. ## The alternatives worth naming Before rewriting, ask whether the depth can simply be capped. Some labeling problems admit a scanline approach that processes whole runs of pixels at a time and never recurses per pixel; some tolerate a hybrid that recurses to a bounded depth and pushes the remainder. But when the requirement really is "label arbitrary connected regions in an arbitrary image", the explicit stack is the answer, and it is a small, mechanical, reviewable change. ## Complexity, unchanged Neither version changes the asymptotics: each pixel is processed once and each adjacency inspected once, so the pass stays linear in the number of pixels. What changes is which memory the pending work occupies and, therefore, whether the program survives its input.