Python Recursion Limit: The Interview Trap Nobody Mentions

You write an elegant recursive DFS. It passes every test case you throw at it locally. Then your interviewer says "let me try a larger input" and you get RecursionError: maximum recursion depth exceeded. The code was correct. The language mugged you in the hallway.

The Default Is 1,000. You Get Fewer.

Python's default recursion limit is 1,000 frames. Verify it yourself:

import sys
print(sys.getrecursionlimit())  # 1000

What Python doesn't put in the headline: that 1,000 counts every frame on the call stack, including the frames Python places there during startup and module loading before your function even runs. In practice, your recursive function will hit RecursionError somewhere around 993 to 997 levels deep, not 1,000.

Treat 993 as your real ceiling, not 1,000.

This matters in interviews. A balanced binary tree with 1,000 nodes has depth roughly 10. A skewed tree with 1,000 nodes has depth 1,000. When your interviewer says "what's the worst case here?" that skewed chain is exactly what they're picturing.

RecursionError Is a Feature, Not a Bug

When you exceed the limit, Python raises:

RecursionError: maximum recursion depth exceeded in comparison

The tail message varies: "in comparison," "while calling a Python object," or just the bare version. They all mean the same thing: your call stack hit Python's software limit.

Python catches this before the operating system does. On Linux and macOS, the main thread stack is typically 8 MB. A Python frame uses a few hundred bytes of C stack space, so you could theoretically fit far more frames before the OS killed your process with a segfault. Python's software limit exists to stop you before that happens. A RecursionError is recoverable and prints a useful message. A segfault gives you a core dump and a very quiet room.

In Python 2 this was RuntimeError. Python 3.5 introduced RecursionError as its own exception class, which makes it easier to catch specifically if you ever need to handle it programmatically.

Why Python Won't Fix This With Tail Calls

The obvious fix is tail-call optimization: when the last thing a function does is call itself, the runtime reuses the current frame instead of pushing a new one. Kotlin's tailrec, Scala, GCC-compiled C with -O2 all support this. Python doesn't.

Guido van Rossum explained this in 2009 and the position hasn't changed since. The core reason is tracebacks. Python's error output shows every frame that led to an exception. If the runtime collapses those frames, those tracebacks vanish and debugging gets much harder. Guido essentially said: I would rather show you exactly how you got here than save you a few thousand stack frames. Readability and debuggability win. The ceiling stays.

There is no syntactic or compiler-level escape hatch. You work around it. The deeper mechanics of why the call stack has this constraint are in what is the call stack, and TCO across languages is in tail-call optimization.

Two Ways Out

Raise the Limit (Use With Caution)

import sys
sys.setrecursionlimit(10_000)

This is the competitive programming default, and for online judges that guarantee input sizes it's completely reasonable. In an interview, it signals you know the limit exists. It's also a yellow flag if you reach for it without explaining why.

The question to ask first: is the recursion actually bounded? If your DFS on a graph with n nodes has depth at most n, and n could be 10,000, you're just pushing the problem one level deeper. You're not solving it. You're scheduling a slightly larger explosion for later.

Raise the limit only when you can bound the maximum depth and the new ceiling safely contains it. In an interview, make the reasoning explicit: "I'm setting the limit to 10,000 because the input constraints cap n at 5,000, so the maximum depth is at most 5,000." That's a complete answer. "I always put this at the top of my solution" is not.

Convert to Iteration (The Right Answer for Deep Inputs)

If depth could be O(n) and n is large, use an explicit stack on the heap. The pattern is the same for any DFS:

def dfs_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

The explicit stack lives on the heap. It can grow as large as available memory, which is orders of magnitude more than the call stack budget. You've moved from O(depth) call stack usage to O(depth) heap usage, and the heap doesn't care about Python's 993-frame limit.

For tree problems this conversion is almost always straightforward. For backtracking, you need to track undo state alongside each frame, which takes more thought. Any recursive solution can be converted mechanically. Convert recursion to iteration has the full walkthrough including backtracking examples.

The Three Cases That Get You

Skewed trees. A BST built by inserting a sorted list degrades to a linear chain of depth n. Mention this before your interviewer does. Ask: "What's the maximum depth we should expect?" That one question changes the conversation.

Graph DFS with depth O(n). Graphs have no natural depth guarantees. A path graph with n nodes has DFS depth n. If n is 10,000, you hit the default limit on the very first call. For graphs where depth could be O(n), iterative DFS is the safer default. Say it proactively before you write a single line.

Deep memoized recursion. Top-down dynamic programming with large inputs builds a long call chain before the cache fills in. A coin change problem with amount = 10000 has recursion depth up to 10,000 on the first traversal path, even with memoization. The cache helps with time. It does nothing for depth. This one catches people specifically because they added memoization, felt confident, and stopped thinking.

Python Recursion Limit: Quick Reference

Item	Value
Default limit	1,000 frames
Actual usable depth	~993 to 997 (context-dependent)
Error class	`RecursionError` (Python 3.5+)
Python 2 equivalent	`RuntimeError`
How to change	`sys.setrecursionlimit(n)`
TCO available	No. Deliberate.
Fix for deep recursion	Explicit stack on the heap
Thread stack size	`threading.stack_size()` (default: OS-dependent)

Surface This Before Your Interviewer Has To

You don't mention it for a balanced tree with depth log(n). You do for:

Any graph traversal where depth is unbounded
Generating all permutations or subsets of large inputs
DP where the recursion chain matches the problem size

When you bring it up, make the reasoning visible: "This DFS has depth O(n) in the worst case. Python's default limit is around 993 usable frames. If n could reach 10,000, I'd either increase the limit with an explicit bound argument or rewrite the traversal iteratively. Want me to show the iterative version?"

That one sentence signals three things at once: you know the limit exists, you know the actual number, and you're proposing the right fix for the right reason. That's the kind of sentence that ends up in the interviewer's write-up.

If you want to practice surfacing constraint analysis like this under interview pressure, SpaceComplexity runs voice-based mock interviews where the AI probes exactly these edge cases and gives you rubric-scored feedback on how clearly you communicated the tradeoff.

For a broader look at Python-specific traps in interview settings, Python coding interview gotchas covers the full list.