Recursion limits in every runtime, and the fix

Every runtime caps how deep recursion can go, because each call that has not returned keeps a frame, and frames live on a stack of fixed size. CPython counts its frames and stops at its recursion limit, 1,000 by default, with RecursionError. Node.js and Java run until the thread’s stack is nearly full and then throw an error; a C++ program writes past the end of its stack and crashes. Go grows each goroutine’s stack until it reaches 1 GB. None of them turns a tail call into a loop for you. So when the depth can reach about 10,000, as it does with a long linked list, a path-shaped graph or a deeply nested input, the fix is to write the loop yourself, with an explicit stack. This lesson measures the recursion limits in every runtime this track uses, then builds the fix in Python.

Why a runtime limits recursion

A frame holds a call’s arguments, its local variables and the point where it carries on, and it stays on the stack until the call returns. A thread’s stack is memory reserved when the thread starts: 8,176 KiB for a program’s first thread on the Mac that recorded these runs (ulimit -s shows it), and 1 MB by default for a Windows program built with Microsoft’s linker. If frames fill it, the next call writes past the end, and POSIX says the thread then receives SIGSEGV: a segmentation fault, with no word about recursion.

Managed runtimes check first. CPython raises RecursionError when its count of Python frames reaches sys.getrecursionlimit(), a limit its documentation says exists to keep infinite recursion from overflowing the C stack. Node.js and Java watch the stack that is left and throw RangeError or StackOverflowError. Go grows each goroutine’s stack by copying it to a larger one, up to runtime/debug.SetMaxStack, 1 GB on 64-bit systems.

The limits, measured

The probe is one function that calls itself, one level deeper each time, until something stops it. In Python:

import sys


def deepest():
    """How many nested calls of a one-argument function start before RecursionError."""

    def down(n):
        try:
            return down(n + 1)
        except RecursionError:  # the call to down(n + 1) could not start
            return n

    return down(1)


print(f"limit {sys.getrecursionlimit():>7,}: deepest call {deepest():>7,}")
for limit in (10_000, 100_000):
    sys.setrecursionlimit(limit)
    print(f"limit {limit:>7,}: deepest call {deepest():>7,}")

limit   1,000: deepest call     998
limit  10,000: deepest call   9,998
limit 100,000: deepest call  99,998

limit   1,000: deepest call     993
limit  10,000: deepest call   9,993
limit 100,000: deepest call  99,993

The limit is a counter, not a measure of memory: 998 calls fit under the default of 1,000, since the module and the function that starts the probe hold two frames, and 99,998 once the limit is 100,000. Written in each language, the same probe gives the recursion limits in every runtime of this track:

The browser rows were measured with the runners themselves under Node.js 24.21.0; a browser gives its worker a stack of its own choosing, so treat them as upper bounds.

The fix: an explicit stack

Deep recursion usually comes from a chain: a linked list, a path-shaped graph, a list nested inside itself. Here is a search of a path of 100,000 vertices, both ways:

def path_graph(n):
    """n vertices in a line, each joined to the next: 0-1, 1-2, ..., (n-2)-(n-1)."""
    adj = [[] for _ in range(n)]
    for v in range(n - 1):
        adj[v].append(v + 1)
        adj[v + 1].append(v)
    return adj


def reach_recursive(adj, start):
    seen = set()

    def visit(v):
        seen.add(v)
        for w in adj[v]:
            if w not in seen:
                visit(w)  # one frame per vertex on the current path

    visit(start)
    return len(seen)


def reach_with_stack(adj, start):
    seen = {start}
    stack = [start]  # vertices found but not expanded yet
    tallest = 1
    while stack:
        v = stack.pop()
        for w in adj[v]:
            if w not in seen:
                seen.add(w)
                stack.append(w)
        tallest = max(tallest, len(stack))
    return len(seen), tallest


for n in (500, 100_000):
    adj = path_graph(n)
    try:
        rec = f"{reach_recursive(adj, 0):,} reached"
    except RecursionError:
        rec = "RecursionError"
    found, tallest = reach_with_stack(adj, 0)
    print(f"path of {n:,} vertices: recursive {rec}; explicit stack {found:,} reached, never more than {tallest} waiting")

path of 500 vertices: recursive 500 reached; explicit stack 500 reached, never more than 1 waiting
path of 100,000 vertices: recursive RecursionError; explicit stack 100,000 reached, never more than 1 waiting

The recursive search keeps a frame for every vertex on the current path, because each call is still inside its loop over neighbours when it makes the next call: 100,000 frames, far past the limit. The loop keeps only the vertices found but not yet expanded, in an ordinary list on the heap, where no frame limit applies; on a path that list never holds more than one vertex. Both do O(V + E) work for V vertices and E edges. The fix moves the pending work; it adds none.

The loop expands vertices in another order than the recursion, which is fine for reachability. When the work after each call matters, as for subtree sizes, each stack entry holds a vertex and the index of its next child, exactly what a frame remembers, and the recursive order is kept step for step.

Exercise

def nested_sum(nested):
    """The sum of every integer in a list nested to any depth."""
    # One call per level of nesting: fails at a depth of about 1,000. Rewrite it with an explicit stack.
    total = 0
    for item in nested:
        if isinstance(item, list):
            total += nested_sum(item)
        else:
            total += item
    return total

import copy

from nested_sum import nested_sum


def deep_list(levels):
    """[1, [2, [3, ... [levels, []] ... ]]], built with a loop."""
    nested = []
    for value in range(levels, 0, -1):
        nested = [value, nested]
    return nested


def test_small_lists():
    """flat and nested lists of a few integers"""
    assert nested_sum([4, 5, 6]) == 15
    assert nested_sum([1, [2, [3]], 4]) == 10


def test_empty_lists():
    """empty lists add nothing, at any depth"""
    assert nested_sum([]) == 0
    assert nested_sum([[], [[]], [[], [9]]]) == 9


def test_lists_side_by_side():
    """many inner lists next to each other, and negative numbers"""
    assert nested_sum([[1, 2], [3, [4, -10]], [[5], 6]]) == 11


def test_three_thousand_levels():
    """a list nested 3,000 levels deep, three times the default recursion limit"""
    assert nested_sum(deep_list(3_000)) == 3_000 * 3_001 // 2


def test_input_left_alone():
    """the list it is given is not changed"""
    data = [1, [2, [3, []]], [4]]
    before = copy.deepcopy(data)
    assert nested_sum(data) == 10
    assert data == before

The same probe in five languages, measured Pro: opens with a Pro, Premium or Ultimate pass

Rewriting any recursion with an explicit stack, checked Pro: opens with a Pro, Premium or Ultimate pass

Safe depths for browser-run code, and raising a limit Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Every unfinished call keeps a frame on a fixed-size stack, so every runtime limits depth; only CPython’s limit is a counter.
• One probe: CPython about 1,000 calls, Node.js about 10,400; unoptimised C++ crashed between 250,000 and 270,000.
• The fix that works everywhere is an explicit stack: the pending work in a list on the heap.
• The browser runners are the tightest place: keep their recursion shallow, or write the loop.