A strong answer
Every thread has a call stack, a fixed-size region of memory: typically 8 MB for the main thread on Linux, 1 MB on Windows, 512 KB for secondary threads on macOS. Each function call pushes a frame holding the return address, saved registers, arguments and locals, and each return pops it. A stack overflow happens when the frames that are active at the same time need more space than the region has. The usual cause is recursion whose depth grows with the input, such as recursing once per element of a long list or down a tree that has degenerated into a chain. Large local arrays can cause it too.
The symptoms depend on the language: a segmentation fault in C and C++, StackOverflowError in Java, "Maximum call stack size exceeded" in JavaScript, and a RecursionError in Python, which stops at a default depth of 1,000 well before the real limit.
Ways to avoid it:
- Use an explicit stack. Keep the pending work in a list on the heap and loop until it is empty. The heap can grow far larger than the call stack.
- Reduce the depth. Recurse into the smaller half first and loop on the larger (as quick sort implementations do, which bounds depth to O(log n)), or keep trees balanced so depth stays logarithmic.
- Use tail calls where they are guaranteed. Scheme guarantees tail-call elimination; Python, Java and most JavaScript engines don't, so a tail-recursive function still uses O(n) stack there.
- Raising the limit or the thread's stack size is a last resort, and in Python raising the limit too far can crash the interpreter itself.
What the interviewer is listening for
- What a frame holds and that the stack has a fixed size per thread.
- That depth, not total work, is what overflows.
- At least two concrete fixes, with the explicit stack first.
Common mistakes
- Blaming recursion itself; shallow recursion is safe.
- Assuming tail-call optimization in languages that don't do it.
- Thinking a larger recursion limit makes the problem go away.