What Is the Python Recursion Limit? Stack Depth, Errors, and How to Fix Them
- Python's recursion limit defaults to 1,000 frames; raise it with
sys.setrecursionlimit(), but that buys rope, not a real fix. - Stack frames (64–128 bytes each) pile onto a fixed OS stack (8 MB on Linux/macOS, 1 MB on Windows); the software guard fires before the hardware does.
- Every language draws its own line: Python raises
RecursionError, Java throwsStackOverflowError, JavaScript raisesRangeError, C/C++ segfaults. - Go is the outlier: goroutine stacks start at 8 KB and grow dynamically, so Go handles far deeper recursion before hitting a wall.
- The real fix is iterative DFS: an explicit stack on the heap has no practical depth limit and handles millions of nodes without complaint.
- In coding interviews, always note that recursive DFS uses O(depth) call-stack space and can hit the recursion limit on unbalanced trees or deep graphs.
- Python's 1,000-frame limit is intentional: Guido declined tail-call optimization to keep stack traces readable, and the guard fires before the OS segfault can.
Your recursive function works perfectly. You tested it. You ran it on the example input, then the edge case, then that weird empty case. It passed all three. Then you run it on a tree with 10,000 nodes and Python immediately loses its mind: RecursionError: maximum recursion depth exceeded. Java would say StackOverflowError. Node.js contributes RangeError: Maximum call stack size exceeded.
Same root cause. Every language draws a line. This is what that line is and why it exists.
The Stack Has a Finite Budget
Every function call costs you a stack frame: a small block of memory holding the return address, local variables, and a pointer back to the caller's frame. Each frame runs about 64 to 128 bytes, sometimes more if the function has a lot of locals.
Stack frames live on the call stack, a region of memory fixed in size at process startup. On Linux and macOS the main thread gets 8 MB. On Windows it gets 1 MB. When you recurse, you pile frames on top of each other. At some depth, you run out of room.
The recursion limit is the runtime's way of stopping you before you exhaust the stack entirely. Without a guard, deep recursion triggers a real segfault. A clean exception beats a silent crash.
Every Language Picks a Different Cliff Edge
| Language | Default limit | Error thrown | Configurable? |
|---|---|---|---|
| Python | 1,000 frames | RecursionError | Yes (sys.setrecursionlimit) |
| Java | ~500 to 1,000 (stack-size dependent) | StackOverflowError | Yes (-Xss JVM flag) |
| JavaScript (V8) | ~10,000 to 15,000 calls | RangeError: Maximum call stack size exceeded | No public API |
| C / C++ | Stack size dependent | Segfault (undefined behavior) | Compile-time / linker flags |
| Go | Goroutine stacks start at 8 KB and grow dynamically | runtime: goroutine stack exceeds limit (default 1 GB) | debug.SetMaxStack |
| Rust | Default 8 MB thread stack | thread 'main' has overflowed its stack | Builder::stack_size |
Go is the interesting outlier. Goroutine stacks grow on demand by copying themselves to a larger allocation. You can recurse much deeper before hitting a wall, though you will still eventually hit one. JavaScript gives you a generous 10,000 to 15,000 calls. C gives you a segfault. Pick your poison.
Python is the strictest and the one most interviewers test for. Its limit is low (1,000) and its standard library data structures favor recursion, which is a fun combination.
What the Error Actually Looks Like
Here is a recursive DFS on a chain-shaped graph in Python. A chain of 2,000 nodes is enough to blow through the default limit. Just 2,000.
import sys def dfs(node, visited, graph): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, visited, graph) # build a chain: 0 -> 1 -> 2 -> ... -> 1999 graph = {i: [i + 1] for i in range(1999)} graph[1999] = [] dfs(0, set(), graph) # RecursionError: maximum recursion depth exceeded
Python's soft limit fires at 1,000 frames. The call to dfs(0) calls dfs(1) calls dfs(2), and so on until the guard trips and your program stops pretending everything is fine.
In Java the same pattern throws StackOverflowError, which is an Error not an Exception. That distinction matters. You almost never want to catch it. It signals that your memory model is broken, not that some value was invalid.
public static void dfs(int node, boolean[] visited, List<List<Integer>> graph) { visited[node] = true; for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { dfs(neighbor, visited, graph); // StackOverflowError on deep chains } } }
How to Buy Yourself More Rope (And Why You Shouldn't)
Python exposes two functions in the sys module.
import sys print(sys.getrecursionlimit()) # 1000 by default sys.setrecursionlimit(10000) # raise the ceiling print(sys.getrecursionlimit()) # 10000
Raising the limit is a patch, not a fix. You are buying yourself more rope. The OS stack is still finite. If you set the limit to 100,000 and your input can produce chains of 200,000, you have moved the crash, not eliminated it. At extreme depths, Python also needs stack space to print the traceback, so you can end up crashing in a way that won't even tell you it crashed.
If you must raise it, set it slightly above your known worst-case depth. For a binary tree with n nodes, the worst case is n (a fully unbalanced tree), so sys.setrecursionlimit(n + 100) keeps the ceiling tight.
Why Python Chose 1,000
Guido van Rossum deliberately declined to implement tail-call optimization (see the Neopythonic post) on the grounds that Python values readable stack traces over stack efficiency. Without TCO, every tail call still allocates a new frame. There is no "smart" recursion to save you.
The 1,000-frame guard sits well below the stack ceiling so Python can print a full traceback and raise a clean exception before the OS segfaults. The OS stack on Linux is 8 MB. Python stops you at 1,000 frames. That gap exists so your program fails with a message you can read, rather than disappearing silently into undefined behavior. CPython 3.12 and 3.13 revised how the limit is enforced internally, but the default of 1,000 stayed.
Why This Bites You in Interviews
Interviewers rarely ask about the recursion limit directly. But it bites in two specific ways.
First, your recursive solution can silently fail on the large test case the interviewer provides. Tree and graph problems are the usual trigger. An unbalanced BST of 10,000 nodes blows the Python limit. A grid DFS on a 100x100 grid where the path snakes through every cell approaches 10,000 frames. Know your input constraints and verify they fit, or convert to an iterative approach before you're watching the interviewer's face as your function crashes on a graph that is, frankly, not even that large.
Second, when the interviewer asks about space complexity, the call stack counts. Recursive DFS on a graph of depth d uses O(d) stack space even if you never explicitly create a stack data structure. A confident answer includes: "the call stack can grow to O(V) in the worst case, which means this could hit the recursion limit on an unbalanced input." That sentence earns signal. See Recursion Space Complexity: Your Stack Only Holds One Path at a Time for the full breakdown.
For practice saying this out loud under pressure, SpaceComplexity runs voice-based mock interviews with rubric scoring so you can work through flagging edge cases before the real thing.
The Actual Fix: Move the Stack to the Heap
The real solution is to convert the recursive DFS to an iterative one using an explicit stack. You move the call stack budget from the OS stack (tiny, fixed) to the heap (much larger, dynamic).
def dfs_iterative(start, graph): visited = set() stack = [start] while stack: node = stack.pop() if node in visited: continue visited.add(node) for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor) return visited
This handles a chain of 1,000,000 nodes without complaint. The heap can hold the equivalent of millions of frames in a Python list. You are doing exactly the same work. You just stopped asking the OS stack to track it.
See The Stack Has a Budget. Here's When to Convert Recursion to Iteration. for a systematic approach to this conversion.
Another option is tail recursion. A recursive function is tail-recursive when the recursive call is the very last thing it does and its return value is used directly. GCC and Clang at -O2, Kotlin's tailrec keyword, and Scala's @tailrec annotation will optimize these into loops, giving you O(1) stack usage regardless of depth. Python deliberately does not do this. See Tail-Call Optimization: How Recursion Escapes the Stack Limit for implementation details.
What Happens If You Ignore All This
When you exceed the OS-level stack space rather than the software guard, the CPU writes into memory outside the stack region. Modern operating systems place a guard page at the boundary. Writing to that page raises a hardware exception (SIGSEGV on Unix, a structured exception on Windows), which the OS catches and turns into a segfault.
Python's 1,000-frame limit exists to raise a Python-level exception before the hardware page fault fires. Java's JVM does the same with StackOverflowError. The software guard fires first, you get a clean message, and your program can recover if it wants to. Go deeper than both layers and you get a real crash: no traceback, no message, no clean exception. Just gone. What Causes a Stack Overflow covers the hardware mechanics if you want the full picture.