Recursion versus iteration: stack depth, limits and when to convert

What it is

A recursive function solves a problem by calling itself on smaller instances; every unfinished call holds a frame on the call stack. The stack is finite. Python enforces a recursion limit, readable with sys.getrecursionlimit(), which the documentation describes as preventing infinite recursion from overflowing the C stack and crashing the interpreter; exceeding it raises RecursionError. Native code is bounded by the thread's stack size (the main thread's limit is RLIMIT_STACK in getrlimit(2)); overflowing it is a segmentation fault, not an exception. Iteration keeps state in variables or in an explicit stack or queue on the heap, whose size is limited by memory rather than by a fixed stack.

Why it matters

Recursion whose depth follows the input is a denial-of-service surface: deeply nested JSON, a directory tree with thousands of levels, a long linked structure or a parser for nested brackets can be crashed by a crafted input. Do not assume tail-call elimination unless the language specification promises it; most mainstream languages do not, so a "tail-recursive loop" still consumes a frame per iteration.

How to apply

• Keep recursion for problems whose depth is bounded by structure, not by input size: balanced trees, syntax trees from a size-limited parser, divide-and-conquer over halves (depth is logarithmic).
• Convert when depth is linear in input: walk a tree with an explicit stack (depth-first) or queue (breadth-first); replace linear recursion with an accumulator loop.
• Where recursion stays, pass a depth parameter and fail cleanly at a documented maximum before the runtime's limit hits, with an error that names the limit.
• Treat raising the recursion limit as a stopgap: it trades a RecursionError for a possible C-stack overflow, and the stack size of other threads is set separately from the main thread's.
• Memoise recursive functions with overlapping subproblems (see dynamic programming); memoisation reduces work, not depth.

Pitfalls

Converting to iteration changes the visiting order unless children are pushed in reverse. Mutual recursion hides depth across several functions. Deep chains of delegating generators (yield from) are traversed on every resumption; treat their depth like recursion depth. Exceptions unwinding a deep stack are slow and produce huge tracebacks. Recursive __eq__, __repr__ or serialisers on cyclic data never terminate; track visited objects.

The depth cap applies to the iterative form too

Replacing recursion with an explicit stack does not bound the depth; it moves the bound from the call stack to the heap, where the failure is an out-of-memory kill of the whole process instead of a catchable RecursionError. For input-controlled nesting (JSON, brackets, directory trees), keep a documented maximum depth in both forms: check the recursion depth parameter in the recursive version, and check the explicit stack's length in the iterative version, failing with an error that names the limit. Parsers commonly ship such a cap (for example serde_json refuses documents nested deeper than 128 levels by default). With a cap in place, the choice between recursion and iteration is one of clarity and of the runtime's frame cost, not of safety.