What Is a Stack Overflow? Why Your Recursion Runs Out of Room
- Stack overflow error occurs when recursive calls push more frames than the call stack's fixed memory budget (8 MB on Linux/macOS, 1 MB on Windows).
- Missing base case is the most common cause; confirm every recursive call moves toward termination on all inputs.
- Python's 1,000-frame RecursionError is a software guard, not a hardware limit;
sys.setrecursionlimit()delays the crash but doesn't fix the root cause. - Call stack depth equals O(depth) space; always state this when analyzing recursive algorithms in a coding interview.
- Convert recursion to iteration using an explicit heap-allocated stack to eliminate overflow risk entirely.
- Go is the outlier: goroutine stacks grow dynamically from 2 KB, making deep recursion far safer than in Python, Java, or C.
- Narrate the space cost in interviews: "O(h) stack space, worst case O(n) for a skewed tree" is the kind of analysis that ends up in a write-up.
You're confident. You've written the recursion. It's elegant. It handles the base case. Probably.
Then: RecursionError: maximum recursion depth exceeded in Python. StackOverflowError in Java. A segfault in C with nothing but a memory address and some deeply regrettable call depth. They all mean the same thing: your program pushed more function calls onto the call stack than it had room for, and the OS finally said no.
Why this happens in exactly the way it does, and what it signals in a coding interview, is worth understanding once.
The Call Stack Has a Fixed Budget
When your program starts, the OS allocates a fixed block of memory for the call stack. Every function call pushes a stack frame onto that block. The frame holds the return address, local variables, and saved registers. When the function returns, that frame is popped. (If you want the full mechanical picture, The Call Stack: What Really Happens When You Call a Function covers the x86-64 call / ret sequence in detail.)
The call stack is not heap memory. It doesn't grow on demand. Default sizes: 8 MB on Linux and macOS for the main thread, 512 KB for macOS non-main threads, 1 MB on Windows. That's the whole budget. Not a guideline. A hard ceiling. Stack overflow isn't a warning you can dismiss. It's the OS saying the tab is closed.
Under normal conditions this is plenty. Most programs have call chains three or four levels deep. Recursion changes the math entirely.
How Frames Stack Up
Left: five frames, ~500 bytes, totally fine. Right: one hundred thousand frames, ten megabytes, not fine.
Take the classic factorial:
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)
Call factorial(5) and you get five frames live at once:
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1) ← base case, start unwinding
A typical frame is 64 to 128 bytes (return address, saved frame pointer, locals). Five frames at 100 bytes is 500 bytes. Essentially nothing.
Now call factorial(100000). That's 100,000 frames at ~100 bytes each. Around 10 MB. You just exceeded the stack limit. The stack pointer walks into protected memory, the OS raises a signal, and your program's last moments are spent printing an error message it didn't write. The name of that error depends on the language. The cause is always the same: too many frames, not enough stack.
The Missing Base Case Is the Most Common Cause
Most stack overflows in interview settings come from one source: a base case that never fires. The recursion sets off with total confidence and never looks back.
def count_down(n): print(n) return count_down(n - 1) # no base case
count_down(10) will recurse until the stack fills. In Python, that happens around frame 1000 because Python installs a software-level guard before you hit the OS limit. You get RecursionError: maximum recursion depth exceeded in comparison.
The fix looks obvious in this example. Real code is less cooperative. The base case might exist but fire on the wrong condition. You might be passing a mutable list and modifying it in-place instead of shrinking it, so the depth never decreases. You might have two mutually recursive functions that cheerfully hand off to each other while jointly agreeing that termination is someone else's problem.
If you see a stack overflow, your first question is: does this recursion actually terminate on all inputs? Work backward from the base case. Confirm every recursive call moves toward it.
Every Runtime Sets Its Own Limit
Different runtimes handle the limit differently. Worth knowing.
| Language | Default limit | Error type |
|---|---|---|
| Python | 1,000 frames (software guard) | RecursionError |
| Java | ~10,000 to 20,000 frames (depends on frame size, configurable with -Xss) | StackOverflowError |
| JavaScript (V8) | ~10,000 to 30,000 frames (engine-dependent) | RangeError: Maximum call stack size exceeded |
| C / C++ | OS limit (~8 MB on Linux) | Segmentation fault |
| Go | Goroutine stacks start at 2 KB, grow dynamically, cap at ~1 GB | Panic: runtime: goroutine stack exceeds limit |
| Rust | OS limit (~8 MB on Linux) | Stack overflow (signal) |
Python's 1,000-frame ceiling is artificial, not a hardware constraint. You can raise it with sys.setrecursionlimit(). The real OS stack is 8 MB and could hold tens of thousands of Python frames. Python installs the software guard because a RecursionError with a traceback is a much better experience than a segfault with nothing, which is what C gives you and what you deserve for not having a base case.
Go is the interesting outlier, and honestly it deserves credit. Goroutine stacks start at 2 KB and double as needed, up to a default cap of 1 GB. Go's ability to grow stacks on demand is one reason it handles deep recursion more gracefully than most runtimes. Truly unbounded recursion will still crash it eventually, but you'll get a lot farther before you do.
Stack Overflow Is a Space Complexity Problem
A stack overflow is what a space complexity bug looks like at runtime. When you recurse to depth n, you hold n frames in memory simultaneously. That's O(n) space on the call stack.
This matters for understanding which recursive algorithms are dangerous on large inputs:
- Factorial, linear search, iterating a linked list: O(n) depth. Dangerous for large n.
- Binary search: O(log n) depth. Fine.
- Merge sort: O(log n) depth for the call tree. The O(n) space is in the merge buffers on the heap, not the stack.
- DFS on a tree of height h: O(h) depth. Fine for balanced trees (O(log n)), dangerous for skewed trees (O(n)).
The call stack depth equals the length of the longest chain of active frames, not the total number of recursive calls. Recursion Space Complexity works through this in detail with several examples.
Merge sort calls itself O(n log n) times across its entire execution, but at most O(log n) frames are live at any moment. That's why merge sort doesn't overflow on large arrays. A naive recursive Fibonacci, on the other hand, generates an exponential call tree while keeping the current path (O(n) deep) on the stack.
The Fix: Move the Stack to the Heap
Three options, roughly in order of how often you should reach for them.
Convert to iteration. Any recursive algorithm can be rewritten using an explicit stack that you manage yourself. The Stack Has a Budget covers the general technique and when it's worth the code complexity. This moves the memory from the OS stack to the heap. The heap is much larger and grows dynamically.
# Recursive DFS: O(h) call stack def dfs(node): if node is None: return process(node) dfs(node.left) dfs(node.right) # Iterative DFS: same algorithm, O(h) heap stack def dfs(root): stack = [root] while stack: node = stack.pop() if node is None: continue process(node) stack.append(node.right) stack.append(node.left)
The iterative version pushes the same nodes. It just uses a Python list instead of the call stack.
Use tail call optimization if your runtime supports it. A tail-recursive call is one where the recursive call is the very last operation before returning, with no pending work left in the current frame. Some languages (Scheme, Haskell, Kotlin with tailrec) can rewrite these into loops, eliminating the frame push entirely. Python and Java do not do this. Guido van Rossum has written about why Python deliberately skips TCO, and his reasoning is worth a read. Don't assume TCO unless you've confirmed your runtime supports it.
Raise the limit. sys.setrecursionlimit() in Python. -Xss in Java. This delays the crash without addressing anything underlying. Fine for a debugging session at midnight when you just need to see if the algorithm converges. Not something you ship.
For interviews, option one is almost always the right answer when asked about stack overflow risk.
Why This Comes Up in Interviews
Stack overflow is a proxy for three things interviewers actually care about.
Space complexity awareness. Do you know recursion has a space cost? Can you state the call stack depth when you analyze a recursive solution? Writing recursive DFS on a tree without noting "this is O(h) space, worst case O(n) for a skewed tree" is a missed signal. The interviewer notices. The write-up will say "candidate did not address space."
Iterative conversion. Translating recursion to iteration shows you understand both models at the level of what the machine is actually doing. Some problems are cleaner recursive. Some need to be iterative for memory reasons. Knowing the difference, and demonstrating it when asked, is a genuine skill.
Base case correctness. Interviewers hand candidates edge cases to watch whether the recursion unravels. If your base case fires on n == 0 but you never verify the recursion terminates on negative inputs, that gap will surface.
The narration matters as much as the code. "My base case fires when the node is null, the recursion depth is O(h), and in the worst case on a skewed tree that's O(n) stack space" is the kind of sentence that ends up quoted in the write-up. "Candidate proactively addressed space complexity." That sentence has gotten people hired.
Practicing that narration out loud under pressure is different from writing it at your desk. SpaceComplexity runs voice-based mock interviews where you explain decisions like these in real time and get rubric feedback on what you said, what you glossed over, and what your interviewer would have written down.
Key Takeaways
- The call stack is a fixed block of OS memory: ~8 MB on Linux and macOS, ~1 MB on Windows.
- Stack overflow means you pushed more frames than fit. Recursion depth exceeded the budget.
- Python's 1,000-frame limit is a software guard. Raising it with
sys.setrecursionlimit()is usually the wrong fix. - Recursive algorithms use O(depth) stack space. Name it when analyzing complexity.
- Converting recursion to iteration moves the stack to the heap. Same algorithm, much larger budget.
- In interviews: state the call stack depth as part of your space complexity analysis. It shows you understand what's actually happening.