vault

Recursion Depth Limits

27 min read

Recursion Depth Limits

Every recursive function call costs a stack frame, and stacks are finite. Exceed the limit and your program crashes — Python raises RecursionError, the JVM raises StackOverflowError, C/C++ executes a segmentation fault. The limits are smaller than most people think: Python’s default sys.getrecursionlimit() == 1000; HotSpot’s default thread stack is 1 MB (1024 KB) on 64-bit Linux/macOS/Solaris (java tool reference, JDK 17), which yields roughly 10⁴–10⁵ frames depending on frame size; the OS-level C stack on Linux is typically 8 MB by default (ulimit -s reports 8192 KB) which permits up to ~10⁵–10⁶ frames for trivial functions but far fewer once you allocate buffers on the stack. This note catalogs the per-language ceilings, the common interview problems where they bite, and the four standard escape hatches: raise the limit (band-aid), convert to iteration with an explicit stack (real fix), convert non-tail recursion to tail recursion via accumulator (only useful in TCO languages), and trampolining (Python’s CPS-equivalent hack). A subtlety this note treats carefully: CPython changed how the recursion limit relates to the C stack in 3.12, so most pre-3.12 advice about “raise the limit and you’ll segfault” is now version-dependent. For interviews, the rule is: any recursion whose depth could exceed ~1000 in Python or ~10^4 in Java must be rewritten iteratively, full stop. Knowing the exact ceiling and how to convert is what separates senior candidates from juniors.

1. Intuition — The Stack Is a Finite Resource

When a function calls itself recursively, the runtime allocates a stack frame — a chunk of memory holding the function’s local variables, parameters, return address, and bookkeeping. Frames are pushed onto the call stack on entry and popped on return. The call stack grows downward in memory toward a fixed limit; cross that limit and you’ve overflowed the stack.

The fundamental tension: an algorithm whose recursion depth is n (e.g., descending a linked list of length n recursively) needs n stack frames simultaneously alive. If n is 10^4 and each frame is ~500 bytes, that’s 5 MB of stack. If n is 10^6, that’s 500 MB — far beyond any default. The recursion crashes.

A real-world analogy: imagine a stack of paper trays on your desk that can hold 1000 trays before tipping over. Each function call places a new tray on top with a sticky-note about what to do next. Each return removes a tray. As long as your call chains are shallow, the stack stays manageable. But if you call yourself 1500 times deep before any returns, the trays tip over and everything spills — the program’s stack-overflow crash. The trays can’t be made arbitrarily tall because the desk has a finite height; that’s the OS / language stack limit.

This is qualitatively different from ordinary memory allocation. The heap (where malloc, new, Python lists, Java objects live) is large — gigabytes. The stack is small — typically megabytes — and the limit cannot be raised arbitrarily even if you have RAM to spare because the OS reserves a virtual-memory region of fixed size for each thread’s stack.

2. Per-Language Ceiling Reference

This is the critical reference table for interviews. Memorize the orders of magnitude.

Language / runtimeDefault recursion depthWhere it livesHow to inspectHow to raise
Python (CPython)1000 function-call framessys.getrecursionlimit()sys.getrecursionlimit()sys.setrecursionlimit(N) — capped softly by C stack
CPython C stack~8 MB on Linux (ulimit -s)OS process stackresource.getrlimit(RLIMIT_STACK)ulimit -s unlimited (shell)
Java (HotSpot)~10⁴–10⁵ framesthread stack-Xss JVM flagjava -Xss8m MyClass (set 8 MB)
Java default thread stack1024 KB (1 MB) on 64-bit Linux/macOS/Solaris; 320 KB on the historic 32-bit VMper-threadjava -XX:+PrintFlagsFinal -version | grep ThreadStackSize-Xss / -XX:ThreadStackSize
C / C++~10⁵–10⁶ framesprocess main stackulimit -sulimit -s unlimited or setrlimit()
Gostarts at 2 KB (stackMin = 2048, since Go 1.4), grows by copy-on-grow up to 1 GB on 64-bit / 250 MB on 32-bitgoroutine stackruntime-managedruntime/debug.SetMaxStack
Rusttypically 8 MB main thread, 2 MB othersOS thread stackplatform-dependentstd::thread::Builder::new().stack_size(N)
JavaScript (V8/Node)~10⁴–10⁵ framesengine-managedRangeError: Maximum call stack size exceedednode --stack-size=N (KiB, default ~984)
Scheme / Racket / OCaml / Haskell / Luaeffectively unlimited via TCOonly non-tail-recursive frames consume stackn/an/a — write tail-recursively
Embedded (ARM Cortex-M)1–8 KB stackdedicated SRAM regionlinker scriptarchitecturally fixed

The interview takeaway. A recursion of depth ~1000 is fine in Python, fine in Java, fine in C/C++. A recursion of depth ~10⁵ is borderline in Java/C/C++ (depends on per-frame size and stack allocations within the function), fatal in Python unless you raise the limit, and impossible in embedded environments. A recursion of depth ~10⁶ is fatal essentially everywhere except Go and TCO-optimized functional languages. If your interview problem might recurse deeper than ~10³ in Python or ~10⁴–10⁵ in Java/C, you must convert to iteration.

3. Tiny Worked Example — Crashing Python at Depth 1000

import sys
 
def descend(n):
    if n == 0:
        return "bottom"
    return descend(n - 1)
 
print(sys.getrecursionlimit())   # 1000
 
descend(900)                     # works: returns "bottom"
descend(1000)                    # RecursionError: maximum recursion depth exceeded

The exact crash threshold is not 1000 — it’s 1000 - (frames already in use when descend was called). CPython’s interactive prompt typically uses ~10–20 frames before your code runs, so the practical ceiling is ~980–990. The RecursionError is raised before the C stack actually overflows, as a defensive Python-level guard.

sys.setrecursionlimit(2_000_000)
descend(50_000)                  # works fine
descend(500_000)                 # CPython <=3.11: may segfault (C stack exhausted)
                                 # CPython 3.12+: pure-Python recursion no longer
                                 #   recurses in C, so this is far more likely to
                                 #   complete (limited by the data stack, not the
                                 #   8 MB C stack) — but it is still slow and a
                                 #   design smell

The version distinction matters (see §4). On CPython ≤3.11 the C stack was the real ceiling: setrecursionlimit removed Python’s internal guard but could not enlarge the OS-allocated C stack region, so a too-high limit traded RecursionError (recoverable) for a segfault (unrecoverable, possibly a core dump). On CPython 3.12+ Python-to-Python recursion no longer consumes C-stack frames, so this particular foot-gun is largely gone for pure-Python recursion — though recursion that passes through C is still capped by the hardcoded C-recursion limit, and deep recursion remains a design smell regardless. Raising the limit is still a band-aid, not a fix: it does nothing for an algorithm whose depth scales with input size.

3.1 What Causes the Bug to Surface

Common interview problems that recurse linearly on input size:

# Recursive linked-list reversal — O(n) recursion depth
def reverse_list(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

Pass it a linked list of 10,000 nodes: RecursionError. Pass 100,000 nodes: even a raised limit may segfault. The iterative version uses constant stack space and works for arbitrarily long lists.

# Recursive DFS on a 1000-node skewed tree
class Node:
    def __init__(self, val): self.val = val; self.left = None; self.right = None
 
# Build a left-skewed tree of 1500 nodes
root = Node(0)
curr = root
for i in range(1, 1500):
    curr.left = Node(i)
    curr = curr.left
 
def dfs(node):
    if node is None: return
    dfs(node.left)
    dfs(node.right)
 
dfs(root)   # RecursionError on most defaults

Skewed trees and linked lists are the canonical scenarios where recursion depth equals input size — the worst case for stack pressure.

4. The CPython Recursion Limit — How It Actually Works (and How 3.12 Changed It)

CPython’s sys.setrecursionlimit(N) sets a Python-level counter that increments on every Python call and decrements on every return. When the counter reaches N, Python raises RecursionError. The default value is 1000, returned by sys.getrecursionlimit(). The official documentation describes its purpose as preventing “infinite recursion from causing an overflow of the C stack and crashing Python” and notes that “if the new limit is too low at the current recursion depth, a RecursionError exception is raised” (changed in 3.5.1) (sys.setrecursionlimit docs).

The default is kept small deliberately:

  1. Most algorithms don’t need more. A binary-tree DFS on a balanced tree of 10^6 nodes has depth ~log_2(10^6) ≈ 20.
  2. It’s a forcing function to write iterative versions when the recursion depth could be linear.

4.1 The Pre-3.12 Model — Python Limit Guards the C Stack

Through CPython 3.11, every Python-to-Python call also pushed a frame onto the underlying C call stack, because the bytecode evaluation loop (_PyEval_EvalFrameDefault) re-entered itself recursively in C for each Python call. The setrecursionlimit counter therefore acted as a guard rail: it fired RecursionError (a catchable exception) before the C stack overflowed (an uncatchable segfault). Raise the limit too high — sys.setrecursionlimit(10**8) — and you removed the guard while the C stack was still only ~8 MB, trading a clean exception for a process crash. This is the model nearly all pre-2023 write-ups describe, and it is the source of the perennial “raising the limit can segfault you” warning.

4.2 The 3.12 Model — C Stack Decoupled From the Python Limit

CPython 3.12 changed this (CPython issue GH-91079, informed by the rejected but influential PEP 651, “Robust Stack Overflow Handling”). Python-to-Python calls no longer recurse in C: when a Python function calls another Python function, the interpreter now sets up the callee’s frame and continues the same _PyEval_EvalFrameDefault loop rather than making a fresh C call. The What’s New document states it plainly: “The recursion limit now applies only to Python code. Builtin functions do not use the recursion limit, but are protected by a different mechanism that prevents recursion from causing a virtual machine crash” (What’s New in Python 3.12).

Two consequences:

  • Pure Python recursion (Python function calling Python function) is now limited only by the setrecursionlimit counter and a contiguous data stack, not by the C stack. Raising the limit is materially safer than it was on 3.11.
  • C-mediated recursion — recursion that passes through builtins or C extensions (the regex engine, __del__/__repr__, JSON decoding, lru_cache’s C wrapper, etc.) — is policed by a separate, hardcoded C-recursion limit that setrecursionlimit does not control.

Uncertain

Verify: the exact numeric value of CPython’s hardcoded C-recursion limit (the Py_C_RECURSION_LIMIT macro) and whether it varies by platform/build. Reason: the value is an internal implementation detail set in CPython’s headers and has been adjusted across point releases; the searches consulted confirmed the macro exists and governs C-stack recursion since 3.12 but did not pin a stable number. To resolve: read Include/cpython/pystate.h (or Include/internal/pycore_*) in the CPython source for the target version. uncertain

A real, documented breaking change came with this: code that combined @lru_cache (whose call path touches C) with a raised sys.setrecursionlimit and worked on 3.11 can now fail on 3.12, because the C-recursion guard fires independently of the Python limit (CPython issue #112282, which also flags the sys.setrecursionlimit docstring as now-inaccurate — the docs still say the limit guards the C stack, which is no longer the whole story).

4.3 Per-Frame Size

Per-call memory cost in CPython is implementation-defined and has shrunk over time. Through 3.10 each call heap-allocated a full frame object; since 3.11 the interpreter uses a leaner internal _PyInterpreterFrame laid out on a contiguous data stack rather than a per-call heap object (PEP 659 “Specializing Adaptive Interpreter”; CPython interpreter internals doc). The exact byte count is not part of the language contract and changes between releases — treat it as “low hundreds of bytes, version-dependent, smaller on 3.11+.” What is contractual and worth memorizing is the count: the default Python recursion limit is 1000 calls.

4.4 Using resource Module to Check the C Stack

import resource
 
soft, hard = resource.getrlimit(resource.RLIMIT_STACK)
print(f"C stack soft limit: {soft} bytes (~{soft // 1024} KB)")
# Typical Linux: 8388608 bytes = 8 MB
 
# Raise within hard limit
resource.setrlimit(resource.RLIMIT_STACK, (hard, hard))

The hard limit is set by the kernel and (for unprivileged users) cannot be raised. The soft limit can be raised up to the hard limit. To raise the hard limit, a privileged process must call setrlimit or the user must ulimit -s unlimited from a shell with appropriate privileges.

4.5 The Go Counter-Example — Growable Goroutine Stacks

Go is the headline exception to “the stack is a small fixed region,” and it is why the table above lists Go’s depth as effectively bounded by 1 GB rather than by a megabyte-scale OS stack. A goroutine does not run on an OS thread stack; the Go runtime gives each goroutine its own small, growable stack and manages growth itself.

Initial size. A new goroutine starts with a tiny stack. The runtime constant is stackMin = 2048 (“the minimum size of stack used by Go code”) in runtime/stack.go — i.e. 2 KB, not the 8 KB many older write-ups still quote. The 8 KB figure was correct only before Go 1.4: the release notes for Go 1.4 record that switching from segmented to contiguous stacks let “the default starting size for a goroutine’s stack… be reduced from 8192 bytes to 2048 bytes” (Go 1.4 release notes). Starting at 2 KB is what makes spawning hundreds of thousands of goroutines cheap.

Copy-on-grow, not segmented. When a function prologue detects that the current stack cannot hold the new frame (the compiler inserts a per-function stack-bounds check against the g’s stack guard), the runtime triggers a stack growth: it allocates a new stack of roughly double the size, copies all live frames from the old stack to the new one, adjusts every pointer that referenced the old stack to point into the new stack, frees the old stack, and resumes. The Go 1.4 notes describe exactly this: “When a stack limit is reached, a new, larger stack is allocated, all active frames for the goroutine are copied there, and any pointers into the stack are updated.” This replaced the pre-1.4 segmented stacks, which chained discontiguous segments and suffered the “hot split” problem — a tight loop straddling a segment boundary would repeatedly allocate and free a segment on every iteration, a pathological performance cliff. Contiguous copy-on-grow eliminates that.

The ceiling. Growth is not unlimited. runtime/debug.SetMaxStack caps a single goroutine’s stack; its documentation states the default is 1 GB on 64-bit systems and 250 MB on 32-bit systems, and “if any goroutine exceeds this limit while growing its stack, the program crashes” (runtime/debug.SetMaxStack). The doc notes the function is “useful mainly for limiting the damage done by goroutines that enter an infinite recursion.” So unbounded recursion in Go does not silently corrupt memory or segfault the way a C overflow can — it grows the stack until it hits maxstacksize and then aborts the program with a “goroutine stack exceeds … limit” fatal error.

Consequences for recursion depth. A linear recursion that would overflow an 8 MB C stack at ~10⁵–10⁶ frames can run far deeper in Go because the stack simply grows. The cost is not free: each growth event copies the entire live stack (an O(current stack size) operation) and must rewrite interior pointers, so a recursion that grows monotonically pays amortized copy cost, and the peak memory is real. Go also has no tail-call optimization — like Python and Java, a tail-recursive Go function consumes a frame per call; it just tolerates far more of them before the 1 GB cap. The idiom in Go is still to bound or iterativize genuinely deep recursion, but the failure mode (graceful runtime abort at a 1 GB cap) is gentler than C’s segfault.

// Deep linear recursion in Go: tolerated to a far greater depth than in C/Python,
// because the goroutine stack grows by copy-on-grow up to the SetMaxStack cap.
func descend(n int) int {
    if n == 0 {
        return 0
    }
    return descend(n - 1) // NOT tail-call-optimized: one frame per call
}
 
func main() {
    // debug.SetMaxStack(64 << 20) // optionally lower the 1 GB default to fail faster
    _ = descend(10_000_000) // grows the stack repeatedly; completes if under the cap
}

5. Conversion Strategies — The Four Standard Escapes

5.1 Strategy 1 — Raise the Limit (Band-Aid)

import sys
sys.setrecursionlimit(10_000)

Use sparingly. The downsides:

  1. Risk of segfault on CPython ≤3.11 if you push the limit past what the C stack holds — the OS kills your process and you cannot catch it. On 3.12+ this risk is largely confined to recursion routed through C (builtins, the re engine), which is guarded by a separate hardcoded limit setrecursionlimit does not raise; either way, “set it huge and forget it” is unsafe.
  2. Slower — every recursive call increments the Python counter.
  3. Hides the real issue. If your problem allows depth n, your algorithm is O(n)-recursion-deep, and any larger input scales the same way. Raising the limit doesn’t help on n = 10^6.

When is it acceptable? In interview pseudocode and quick prototypes, sometimes. In production, almost never.

5.2 Strategy 2 — Convert to Iteration with an Explicit Stack

The general theorem (Church-Turing-style): every recursive algorithm can be made iterative by simulating the call stack with an explicit data structure. See Recursion vs Iteration for the deep treatment. The key transformations:

Tail recursion → simple loop.

# Tail-recursive
def sum_tail(n, acc=0):
    if n == 0: return acc
    return sum_tail(n - 1, acc + n)
 
# Iterative
def sum_iter(n):
    acc = 0
    while n > 0:
        acc += n
        n -= 1
    return acc

Tree DFS → explicit-stack iteration.

# Recursive DFS
def dfs_rec(node):
    if node is None: return
    process(node)
    dfs_rec(node.left)
    dfs_rec(node.right)
 
# Iterative — explicit stack, push children in reverse for pre-order match
def dfs_iter(root):
    if root is None: return
    stack = [root]
    while stack:
        node = stack.pop()
        process(node)
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)

The iterative version uses heap memory (the stack list), which is much larger than the OS stack. For a Python list, you can comfortably push 10⁷ items.

Linked-list traversal → loop.

# Recursive
def length_rec(head):
    if head is None: return 0
    return 1 + length_rec(head.next)
 
# Iterative
def length_iter(head):
    count = 0
    while head is not None:
        count += 1
        head = head.next
    return count

The iterative version uses O(1) stack and O(1) heap. The recursive version uses O(n) stack — fatal for n > 1000.

5.3 Strategy 3 — Tail Recursion (Only Useful in TCO Languages)

In Scheme, OCaml, Haskell, Erlang, Standard ML, Lua, the compiler optimizes tail calls into loops, so a tail-recursive function uses O(1) stack space regardless of recursion depth. Idiomatic Scheme uses recursion as the loop construct.

In Python, however, TCO is not implemented and never will be. Guido van Rossum’s 2009 blog post “Tail Recursion Elimination” explicitly rejected the proposal. The reasons:

  1. Tracebacks are valuable. Optimizing away the call frames means Python’s traceback won’t show the chain of calls — debugging suffers.
  2. The win is small. Most Python code is not deeply tail-recursive; for loops are idiomatic.
  3. It’s a slippery slope to other functional optimizations Python doesn’t want.

PEP 666 (a joke proposal “Reject foolish indentation”) later codified the philosophy: Python is not a functional language and won’t grow features that obscure its execution model.

The implication: if you write a tail-recursive function in Python expecting it to be efficient, you have a bug. A tail-recursive factorial(10_000) crashes with RecursionError exactly like a non-tail one would.

Same applies to Java, JavaScript (V8 doesn’t implement the ES6 TCO spec), and C# (no TCO by default).

5.4 Strategy 4 — Trampolining (Python’s CPS Hack)

If you insist on recursion-style code in Python without blowing the stack, you can use a trampoline: a function returns a thunk (a zero-argument callable) representing “continue with this”, and an outer loop repeatedly calls thunks until the result is a non-thunk.

def trampoline(f, *args):
    """Drive a tail-recursive function via a trampoline loop."""
    result = f(*args)
    while callable(result):
        result = result()
    return result
 
def factorial_thunked(n, acc=1):
    if n <= 1:
        return acc
    return lambda: factorial_thunked(n - 1, acc * n)
 
print(trampoline(factorial_thunked, 10_000))   # works! O(1) stack

The recursion is replaced by a loop. Each “recursive call” returns a thunk that the trampoline then invokes. The control flow is converted to continuation-passing style (CPS) — a real technique from compiler theory, used by every Scheme implementation.

The downside: ugly, slower (lambda allocation per call), and not idiomatic Python. Almost never the right choice; just write a loop. Trampolining shows up in:

  • Theoretical / research code
  • Generators and coroutines (Python’s yield is essentially trampolining built into the language)
  • Continuation-heavy concurrency libraries

6. Pseudocode — The General Conversion Recipe

recursive_to_iterative(rec_func):
    if rec_func is tail-recursive:
        replace recursive call with loop variable update
        return as while/for loop

    elif rec_func is linear-recursive (calls itself once per invocation):
        introduce accumulator parameter
        rewrite as tail-recursive with accumulator
        then apply tail → loop transformation

    else (tree-recursive: multiple recursive calls per invocation):
        introduce explicit stack
        each recursive call → push state onto stack
        each return → pop and process
        outer loop until stack is empty

The “explicit stack” pattern requires capturing all local state at the point of the recursive call: parameter values, local variables, and a “phase” indicator (am I before or after the recursive sub-call?). For non-tail tree recursion (e.g., post-order traversal), the phase indicator is necessary — you need to know whether you’re descending or ascending. See Tree Traversals for the iterative post-order details.

7. Python Implementation — Inspecting and Manipulating Stack

import sys
import resource
import threading
 
# Inspect default
print(sys.getrecursionlimit())                        # 1000
 
# Inspect C stack
soft, hard = resource.getrlimit(resource.RLIMIT_STACK)
print(f"C stack: {soft // 1024} KB soft, {hard // 1024 if hard != -1 else 'unlimited'} KB hard")
 
# Raise Python limit
sys.setrecursionlimit(10_000)
# WARNING: don't go beyond what C stack supports
 
# Run on a larger stack via threading.Thread with explicit stack_size
def deep_recursion():
    sys.setrecursionlimit(100_000)
    def f(n):
        if n == 0: return "done"
        return f(n - 1)
    print(f(50_000))
 
# Thread with 64 MB stack
threading.stack_size(64 * 1024 * 1024)
t = threading.Thread(target=deep_recursion)
t.start()
t.join()
# Useful when your main thread's stack is small but you need
# deep recursion in a one-off computation

7.1 The Iterative-DFS Workhorse

def deep_skewed_tree_dfs(root):
    """Iterative pre-order DFS, safe for arbitrarily skewed trees."""
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        # process(node)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

For a 10⁶-node left-skewed tree (linked-list-shaped), this version runs in O(n) time and O(n) heap memory. The recursive version would crash. The lesson: tree algorithms in Python must be iterative if the tree could be skewed.

7.2 Decorator to Detect Excessive Depth

import functools
 
def depth_guarded(max_depth):
    def decorator(f):
        f._depth = 0
        @functools.wraps(f)
        def wrapper(*args, **kwargs):
            f._depth += 1
            if f._depth > max_depth:
                f._depth -= 1
                raise RecursionError(f"{f.__name__} exceeded {max_depth} depth")
            try:
                return f(*args, **kwargs)
            finally:
                f._depth -= 1
        return wrapper
    return decorator
 
@depth_guarded(500)
def my_recursive_function(n):
    if n == 0: return
    my_recursive_function(n - 1)
 
my_recursive_function(400)    # OK
my_recursive_function(600)    # raises depth-guard RecursionError

Useful for testing whether your algorithm respects an intended depth bound.

8. Diagram — Stack Frames vs Heap Stack

flowchart LR
    subgraph "Recursive: System call stack"
      direction TB
      F1["frame 1 (main)"]
      F2["frame 2 (rec_func)"]
      F3["frame 3 (rec_func)"]
      F4["frame 4 (rec_func)"]
      Fdots["..."]
      Fmax["frame N (limit reached)"]
      F1 --> F2 --> F3 --> F4 --> Fdots --> Fmax
      Boundary1["Stack region:<br/>~1000 frames Python<br/>~10^4 frames Java<br/>~10^5 frames C"]
      Fmax -.->|"crosses boundary"| Boundary1
      Crash["RecursionError /<br/>StackOverflowError /<br/>SIGSEGV"]
      Boundary1 --> Crash
    end

    subgraph "Iterative: Heap-allocated stack"
      direction TB
      H1["main"]
      Hstack["explicit stack (list/Vec/Stack):<br/>[node1, node2, ..., node_N]"]
      H1 --> Hstack
      Boundary2["Heap: gigabytes available;<br/>no fixed-size bound"]
      Hstack -.->|"sized by RAM"| Boundary2
    end

What this diagram shows. Two ways to traverse a deep tree or list. On the left, the recursive version: every call adds a frame to the OS-managed call stack. The stack region is fixed-size (~1000 Python frames, ~10⁴ Java frames, ~10⁵ C frames at default settings); exceeding the boundary crashes the program with RecursionError (Python), StackOverflowError (Java), or a segfault (C). On the right, the iterative version: a Python list / Java ArrayDeque / C++ std::stack lives in the heap, which is gigabytes large. The same Θ(n) total space is used in both cases, but heap-stack iteration has no fixed-size ceiling and works for inputs orders of magnitude larger. The takeaway: for any recursion whose depth could exceed ~1000 in Python or ~10⁴ in Java, convert to iteration with an explicit heap-allocated stack, or you risk crashes on adversarial inputs.

9. Common Interview Problems Where Depth Limits Bite

ProblemDepthRecursive crash?Fix
Linked List ReversalO(n)Yes for n > 1000 PythonIterative reversal
Tree DFS on skewed treeO(n)YesExplicit stack
Tree DFS on balanced treeO(log n)No (depth ~20 for n = 10^6)Either
Recursive Fibonacci (naive)O(n)Yes for n > 1000Memoization or iteration
Compute factorial recursivelyO(n)Yes for n > 1000 PythonIterative product
Sudoku solver (backtracking)O(81) typicallyNo (bounded by board size)Recursive is fine
N-QueensO(n)No (board size limited)Recursive is fine
PermutationsO(n)No (n is small)Recursive is fine
Subarray problems via D&CO(log n)NoRecursive is fine
Quicksort worst case (sorted input)O(n) worstYesTail-call elimination on the larger half, iterate the smaller
Merge SortO(log n)NoRecursive is fine
DFS on arbitrary graphO(V)Yes for sparse / chain graphsExplicit stack
Recursive descent parserO(d) where d is grammar nestingMaybe — pathological JSON [[[[...]]]]Iterative parsing
BFS with recursion (anti-pattern)variesDon’t recurse for BFSUse a queue
Deeply nested JSONO(d)Yes for malicious inputsIterative parser; cap depth
File-system traversal (recursive)O(d)Yes for symlink loops or deeply nested directoriesIterative walk; use os.walk-style

The recognition signal: whenever recursion depth correlates with input size linearly, you’re at risk.

10. Variants and Sub-Patterns

10.1 Quicksort Stack Optimization

Naive recursive quicksort recurses on both halves: qs(left); qs(right). On a worst-case sorted input, the unbalanced partition gives O(n) recursion depth. The Sedgewick optimization: recurse on the smaller partition, iterate over the larger — guarantees O(log n) stack depth even in the worst case. See Quicksort §11.

def quicksort(arr, lo, hi):
    while lo < hi:
        p = partition(arr, lo, hi)
        if p - lo < hi - p:
            quicksort(arr, lo, p - 1)
            lo = p + 1                # iterate on the larger half
        else:
            quicksort(arr, p + 1, hi)
            hi = p - 1

This is the technique used by every production quicksort.

10.2 Fork-Join Recursion

In Java, the ForkJoinPool framework uses work-stealing and lets each task have its own (small) stack. Deep fork-join hierarchies can exhaust per-task stacks even when the algorithm is logarithmic-depth, because each branch’s sub-tasks share the parent’s continuation.

10.3 Mutual Recursion

Two functions calling each other (even(n) → odd(n-1) → even(n-2) → ...) consumes stack frames just as fast as direct recursion. The standard transformation: merge the two functions into one with an extra “which function am I” parameter, then convert to iteration.

10.4 Iterative Deepening DFS

For game search and puzzle problems, Iterative Deepening DFS uses recursive DFS with a depth bound, repeated at increasing bounds. The depth is known and bounded, so recursion is safe — but be aware that re-running shallow searches contributes constant-factor overhead.

10.5 Tail-Recursion via Continuations

In Scheme, the canonical functional language with TCO, call-with-current-continuation (call/cc) lets you escape arbitrary control structures. In Python, you can simulate continuations with generators (yield) — Python’s coroutines essentially trampoline to a generator-driver loop, sidestepping the recursion limit. PEP 380 (yield from) and asyncio build on this.

11. Pitfalls

11.1 Assuming Python Has TCO

It does not, and never will. Don’t write tail-recursive Python expecting O(1) stack. See Recursion vs Iteration §4.

11.2 Setting the Limit Too High

sys.setrecursionlimit(10**9) does not give you 10⁹ usable frames — it just lifts Python’s call-count guard. On CPython ≤3.11 the C stack was still ~8 MB on Linux, and exceeding it segfaulted the process, so the limit must stay below what the underlying C stack can hold. On 3.12+ pure-Python recursion is decoupled from the C stack (see §4.2), so a high limit is safer for pure-Python call chains — but recursion that touches C is still bounded by the hardcoded C-recursion limit, and you can still exhaust memory (the data stack grows) or simply hang. Don’t treat a large setrecursionlimit as a substitute for an iterative algorithm.

11.3 Forgetting Per-Thread Stack

threading.stack_size(N) sets the stack for new threads; the main thread’s stack is set at process start. To get a deep stack in the main thread, raise ulimit -s before launching Python — once the process is running, you cannot enlarge the main thread’s stack.

11.4 Off-By-One in the Recursion Limit

sys.setrecursionlimit(N) sets a soft limit. The actual recursion depth you can reach is N - (frames already in use). If your code is invoked from a deep callable chain (test framework, decorator stack), the effective depth is less than N. Always measure.

11.5 Using lru_cache Doesn’t Save You

Memoization speeds up repeated calls but doesn’t reduce the current call chain’s depth:

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)
 
fib(2000)   # RecursionError, even though fib(2000) is now O(n) time after memoization

The recursion depth on the first call to fib(2000) is still 2000. Memoization caches results, not call frames. The fix is iterative bottom-up DP. See Memoization vs Tabulation.

11.6 Implicit Recursion in Library Calls

Some library calls recurse internally. re.match(r'(a+)+$', 'a' * 30 + '!') triggers catastrophic backtracking with deep recursion in the regex engine. This is C-level recursion: sys.setrecursionlimit (the Python call-count limit) does not govern it. On older CPython this could segfault the interpreter; since 3.12 such C-stack recursion is policed by the separate hardcoded C-recursion limit (§4.2), so you are more likely to get a RecursionError than a hard crash — but the underlying performance pathology (exponential backtracking) is still there. Validate input length / regex complexity for any input you cannot trust, and prefer regex-module or RE2-style linear engines for untrusted patterns.

11.7 Recursion in __del__ and __repr__

Python invokes __del__ (destructor) and __repr__ automatically. If your __del__ recurses through the object graph and the graph is deep, you get RecursionError from inside garbage collection — sometimes silently swallowed. Defensive iteration is mandatory in __del__.

11.8 Forgetting Sedgewick’s Quicksort Optimization

Naive recursive quicksort on sorted input has O(n) depth. With n = 10^4 and Python default limit 1000, the recursion crashes. The fix (Sedgewick): always recurse on the smaller partition, iterate over the larger. Reduces worst-case depth to O(log n).

11.9 Converting Wrong Direction

A common trap: converting a correct recursive algorithm to iteration but introducing a bug in the explicit-stack version. The recursive version’s exit conditions are implicit; the iterative version makes them explicit, and getting them wrong is easy. Always test the iterative conversion against the recursive reference on small inputs.

11.10 Underestimating Frame Size

Some functions stack-allocate large local arrays:

void foo(int n) {
    int buf[1000];
    foo(n - 1);
}

Each frame is 4 KB (for int buf[1000]) plus overhead. A 1000-deep recursion needs 4 MB of stack — already half the Linux default. Adding more locals or larger buffers makes the depth ceiling drop fast.

12. Open Questions

  • Why doesn’t Python adopt TCO? Answer: explicit philosophical decision by Guido. The technical case for/against is complex; the practical case is “Python’s debugger and tracebacks would lose information.” Probably will never change.
  • Could CPython’s specializing interpreter (3.11+) eventually shrink frames enough to make the default limit obsolete? Frames are already much smaller in 3.12 than in 3.10. The Python community’s stance is that the limit is a forcing function, not a constraint — keep it small to push toward iterative solutions.
  • Do JIT-compiled languages (PyPy, V8, GraalVM) handle tail recursion better? PyPy still inherits CPython’s limit. V8 doesn’t implement ES6 TCO. GraalVM can sometimes optimize tail calls if asked. None of them give “infinite tail recursion for free” the way Scheme does.
  • How do async def coroutines interact with the recursion limit? await does not consume a stack frame in the same way. asyncio.gather of deeply chained coroutines can exceed the limit because Python’s event loop trampolines them — but a recursive async def calling itself synchronously does consume frames.

13. See Also

Graph View

Backlinks