What Causes a Stack Overflow (and What It Means for Interviews)

You've seen it. RecursionError: maximum recursion depth exceeded. Or StackOverflowError. Or, in C++, a segmentation fault with no helpful message at all, because the universe owes you nothing.

That last one is my favorite. Your program just dies. A thousand beautiful recursive calls, silently eaten by the void.

A stack overflow happens when too many function calls pile up before any of them return, exhausting a fixed block of memory the OS reserved for this purpose. That's the entire mechanism. One sentence. And yet most developers either don't know it or know it abstractly and still get blindsided by it in interviews. This post is about not being that person.

What Actually Lives on the Call Stack

Every function call needs somewhere to stash its local state while it's running. That place is the stack frame: a small block of memory holding the function's local variables, the return address (where execution jumps when the function finishes), and a handful of saved registers.

The stack is not heap memory. It's a fixed-size block allocated when the thread starts, and it does not grow.

On x86-64, a minimal frame is 64-128 bytes. A function with several local variables might use 400-500 bytes. Now call it 10,000 times without returning and do the math. You're not running out of RAM. You're running out of a specific, bounded region of memory reserved for one particular job.

Default limits, because they matter more than you think:

Language / Runtime	Default stack limit
Python 3	~1,000 frames (software limit via sys.getrecursionlimit())
Java (HotSpot)	512 KB to 1 MB per thread (set with -Xss)
Node.js (V8)	984 KiB (Windows: 1 MiB)
C / C++ (Linux, main thread)	8 MB
C / C++ (macOS, pthreads)	512 KB
Rust (spawned thread)	2 MB
Go goroutine	Adaptive (starts 2 to 8 KB, grows to 1 GB on 64-bit)

Python's 1,000-frame limit is a software guard that Python enforces before the OS would crash the process. You can raise it with sys.setrecursionlimit(n), but as of Python 3.12 this only controls Python-level recursion. C extension calls have a separate hardcoded limit. So "just set the limit higher" is less of a real escape hatch than it sounds.

Go is the outlier. Goroutine stacks start tiny and grow on demand, which means stack overflows from deep recursion are rare in Go. The runtime dynamically allocates and relocates stack memory as needed. It's the reasonable one at the table.

Each frame is 64-128 bytes. A balanced tree with a million nodes needs ~20 frames. A skewed tree needs a million.

Five Things That Cause Stack Overflows

1. Missing base case. The recursion never terminates. This one is fast and obvious.

def factorial(n):
    return n * factorial(n - 1)  # no base case

Python hits 1,000 frames and raises RecursionError. You ran factorial(5) and got a wall of traceback. Classic.

2. Base case that can't be reached. The function has a base case. The code looks plausible. The recursion never arrives.

def countdown(n):
    if n == 0:
        return
    countdown(n + 1)  # going up, not down

This one is subtler and more embarrassing. You wrote a base case. You feel good about it. Python disagrees.

3. Recursion depth proportional to input size. Everything is correct, but on large inputs the recursion exceeds the stack limit before finishing.

def sum_list(lst, i=0):
    if i == len(lst):
        return 0
    return lst[i] + sum_list(lst, i + 1)

sum_list(list(range(2000)))  # RecursionError in Python

Correct algorithm. Wrong runtime behavior for large inputs. This is the hardest category to catch in review because the code works fine on small test cases. You test it with 10 elements, ship it, and then a user comes along with a list of 5,000 items.

The base case was unreachable all along.

4. Mutual recursion. Two functions call each other. Each pair adds two frames before either returns, burning through the stack twice as fast.

def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0: return False
    return is_even(n - 1)

is_even(10000)  # RecursionError

Two functions, each perfectly reasonable. Together, they conspire against you.

5. DFS on a degenerate or very deep structure. A tree with 100,000 nodes in a skewed (linked-list-like) shape has depth 100,000. Recursive DFS crashes. This is not a contrived case. Interviewers build test cases like this deliberately.

def dfs(node):
    if not node:
        return
    dfs(node.left)   # depth = tree height in worst case
    dfs(node.right)

For a balanced BST with a million nodes, height is about 20 frames. Fine. For a fully skewed tree, height is a million frames. Your interviewer is watching you run this and nodding slowly.

How to Read a Stack Overflow Traceback

When Python raises RecursionError, the traceback repeats the same frames hundreds of times. Most developers scroll down, get vertigo, and close the terminal.

Don't do that. The useful information is near the top of the output, not buried in the repetition.

Look for two patterns:

• The same single frame repeating means infinite recursion. Base case is missing or unreachable.
• Two or three frames alternating means mutual recursion.

In Java, StackOverflowError shows the same method repeated in the stack trace. In C/C++, you get a segfault with no message, but a debugger (gdb) can walk the blown-out call stack for you. At that point you're essentially an archaeologist sifting through rubble.

How to Fix It

Fix the recursion logic first

Check three things before reaching for any other tool:

1. Does the base case exist?
2. Does every recursive call move toward the base case?
3. Can any input value skip the base case entirely (off-by-one, wrong type, empty input)?

Trace three iterations by hand before running the code. Most base-case bugs are visible in two minutes of manual tracing. Two minutes. Not a profiler, not a debugger. A pencil.

Convert to iteration with an explicit stack

Any recursive algorithm can be rewritten as a loop that manages an explicit stack on the heap. You trade the 8 MB call stack for the heap, which scales to gigabytes.

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

Same traversal order. No recursion depth limit. For any input where recursion depth could exceed a few thousand, iterative is the correct choice. The iterative tree traversal guide has patterns for preorder, inorder, and postorder.

Use tail-call optimization where it exists

A tail call is a recursive call where the call is the very last thing the function does, with no work left after it returns. Compilers and runtimes that support tail-call optimization (TCO) can reuse the current stack frame for the recursive call, flattening O(n) stack depth to O(1).

# Standard: builds n frames
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Tail-recursive: only the last call matters
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)  # nothing happens after this returns

The catch: Python deliberately does not implement TCO. Guido van Rossum wrote about this decision explicitly. Python's design values readable stack traces over TCO. So the tail-recursive form above crashes just as fast as the standard form. You rewrote your function and accomplished nothing. Fun.

TCO does exist in:

• GCC / Clang at -O2 and above (look for jmp instead of call in the assembly)
• Kotlin with the tailrec modifier (compile-time transformation to a loop)
• Scala with the @tailrec annotation
• Haskell by default for tail calls

For full details on which languages implement it and how to verify, see the tail-call optimization guide.

Why Stack Overflows Change Your Space Complexity Answer

Here's where interview candidates lose points without realizing it.

Every recursive algorithm's space complexity includes the call stack. The call stack is O(maximum recursion depth) space. This isn't a minor footnote you can wave away. It's part of the answer.

Take recursive binary search:

def binary_search(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

Time complexity: O(log n). Space complexity of the iterative version: O(1). Space complexity of this recursive version: O(log n), because there are O(log n) stack frames open at any moment.

Both are "binary search." Different space complexities. If an interviewer asks for O(1) space, they want the iterative version. "Binary search" as an answer is incomplete.

The same accounting applies across the board:

Algorithm	Recursion depth	Space from call stack
Recursive factorial	O(n)	O(n)
Recursive binary search	O(log n)	O(log n)
DFS on balanced binary tree	O(log n)	O(log n)
DFS on skewed binary tree	O(n)	O(n)
Merge sort	O(log n)	O(n) from merge + O(log n) from stack
Quicksort (average case)	O(log n)	O(log n)
Quicksort (worst case)	O(n)	O(n)

The rule: any time you claim O(1) space for a recursive algorithm, you are wrong.

There's one exception worth knowing: Go. Because goroutine stacks grow dynamically, deep recursion in Go doesn't necessarily overflow. It just uses more memory. You still need to account for that memory in your space analysis, but you won't see a hard crash at frame 1,000.

For a deeper look at the call stack's role in recursion space analysis, see Recursion Space Complexity.

The Interview Move When Your Solution Could Overflow

If your recursive solution has O(n) stack depth and the problem constraints allow n up to 10^5 or 10^6, say something out loud. Don't just code it and hope the interviewer doesn't notice.

"This recursive solution is O(log n) space for a balanced input, but degenerates to O(n) for a skewed tree. If the input can be arbitrarily deep, I'd convert this to an iterative DFS with an explicit stack to avoid hitting the platform's recursion limit."

That one sentence does three things. It shows you understand the stack's role in space complexity. It shows you're thinking about edge cases. And it positions the iterative version as a deliberate engineering choice rather than a fallback because the recursive version broke.

SpaceComplexity runs mock interviews that probe exactly this. After you code a recursive solution, expect a follow-up: "What's the space complexity? What happens on a worst-case input?" Practicing your answer out loud before an interview is the only way to stop stumbling on it when it counts.

Key Takeaways

• A stack overflow happens when the call stack exhausts its fixed memory budget. Five main causes: missing base case, unreachable base case, depth proportional to input size, mutual recursion, and deep DFS on a skewed structure
• Python crashes at ~1,000 frames by default; C/C++ at ~8 MB on Linux; Go goroutines grow dynamically and rarely overflow
• Every recursive algorithm uses O(recursion depth) stack space. Recursive binary search is O(log n) space, not O(1)
• Convert O(n)-depth recursion to an iterative explicit stack for large inputs. TCO eliminates the cost in GCC/Clang, Kotlin, and Scala, but Python deliberately skips it
• In an interview, say out loud when your recursive solution could overflow on the given constraints, then offer the iterative alternative

Further Reading

• Python sys.setrecursionlimit documentation
• Wikipedia: Call stack
• Guido van Rossum: Tail Recursion Elimination (2009)
• GCC Optimize Options: -foptimize-sibling-calls
• Cloudflare Blog: How Stacks Are Handled in Go