The short answer
Quick answer: Every function call uses a little memory on the call stack to hold its local variables and the place to return to. A recursive function calls itself, so each level adds another frame. The stack has a fixed, fairly small size. If the recursion goes too deep, or never stops because the base case is wrong, the stack runs out of space and the program fails with a stack overflow: RecursionError in Python, StackOverflowError in Java, "Maximum call stack size exceeded" in JavaScript, or a segmentation fault in C.
How recursion works
A recursive function solves a problem by solving a smaller version of the same problem. It needs two parts:
- A base case: an input small enough to answer directly.
- A recursive case: reduce the problem and call yourself.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
Calling factorial(4) builds up a chain of unfinished calls:
factorial(4) waiting for factorial(3)
factorial(3) waiting for factorial(2)
factorial(2) waiting for factorial(1)
factorial(1) returns 1
returns 2
returns 6
returns 24
Each waiting call occupies a stack frame. The frames are only released as the calls return, from the innermost outward. The layout of those frames is described in stack vs heap.
Why the stack runs out
The stack is a region of memory set aside when a thread starts. Typical sizes are around 1 MB on Windows and 8 MB on Linux for the main thread, and often less for extra threads. It does not grow without limit.
Two things cause an overflow:
1. Infinite recursion
The base case is missing, wrong, or never reached.
def countdown(n):
print(n)
countdown(n - 1) # no base case: never stops
Other common versions: the recursive call does not make the problem smaller, or the base case tests n == 0 and the function is called with a negative or fractional number that skips past it.
2. Legitimately deep recursion
The logic is correct, but the input is big. factorial(100000) needs 100,000 frames. Walking a linked list recursively, or traversing a badly unbalanced tree, has the same problem.
Languages react differently:
| Language | Behaviour |
|---|---|
| Python | Raises RecursionError at a configurable depth limit (1,000 by default) |
| JavaScript | Throws RangeError: Maximum call stack size exceeded |
| Java | Throws StackOverflowError |
| C, C++ | Undefined behaviour, usually a crash (segmentation fault) |
| Go | Stacks grow dynamically up to a large limit, then the program aborts |
Python's limit is a safety net. You can raise it with sys.setrecursionlimit, but go too high and the interpreter itself crashes.
Fix 1: Get the base case right
Check three things:
- Is there a base case?
- Does every recursive call move towards it?
- Does it cover edge cases such as zero, negative numbers and empty inputs?
Fix 2: Use iteration
Any recursion can be rewritten as a loop. For simple cases the loop is obvious:
def factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
This uses one stack frame no matter how large n is.
Fix 3: Use your own stack
For tree and graph traversal, replace the call stack with an explicit stack on the heap, which is limited only by available memory:
def depth_first(root):
stack = [root]
while stack:
node = stack.pop()
visit(node)
stack.extend(node.children)
Fix 4: Tail calls, where supported
A tail call is a call that is the very last thing a function does. Nothing remains to be done afterwards, so in principle the current frame can be reused instead of adding a new one. This is called tail call optimisation (TCO).
def factorial(n, acc=1):
if n <= 1:
return acc
return factorial(n - 1, acc * n) # tail call
Whether this helps depends on the language. As the Wikipedia article on tail calls explains, Scheme guarantees it, and functional languages such as Haskell, Elixir and Scala (with an annotation) support it. Python does not, by design, and most JavaScript engines do not either. C and C++ compilers may do it as an optimisation but make no promise. Do not rely on it unless your language guarantees it.
Fix 5: Memoisation for exploding recursion
Sometimes the problem is not depth but repeated work:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(40) makes hundreds of millions of calls, because it recomputes the same values again and again. Caching results fixes it:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Each value is now computed once. The cache is a hash map from arguments to results. Going one step further and filling a table from the bottom up removes the recursion altogether; that is the heart of dynamic programming.
When recursion is the right tool
Recursion is not something to avoid. It is the clearest way to express problems that are naturally recursive:
- Walking trees: file systems, JSON, the DOM, syntax trees in a compiler.
- Divide-and-conquer algorithms such as merge sort and quicksort.
- Backtracking: puzzles, permutations, path finding.
The safe cases are those where depth grows slowly. A balanced binary tree with a billion nodes is only about 30 levels deep, so recursion over it is fine. The dangerous cases are those where depth grows in step with input size, such as recursing once per list element.
A security angle
If recursion depth depends on user input, an attacker can crash your service with deeply nested data, for example JSON with tens of thousands of nested brackets. Parsers for untrusted input should enforce a maximum depth.
Frequently asked questions
What is a stack overflow?
An error that occurs when a program uses more call stack space than is available, almost always because of recursion that is too deep or never ends.
Is recursion slower than a loop?
Usually slightly, because each call has overhead. The difference rarely matters; choose the clearer option unless depth or speed is a real concern.
Can I just make the stack bigger?
You can, with thread options or system settings, but it only postpones the problem. For unbounded depth, convert to iteration.
Why is the stack so small compared with the heap?
Every thread needs its own stack, and a fixed, contiguous region is what makes stack allocation so fast. Large or long-lived data belongs on the heap.
Conclusion
Recursion crashes programs for a simple reason: each call needs stack space, and the stack is finite. Make sure every recursion has a reachable base case, keep an eye on how depth grows with input size, and switch to a loop or an explicit stack when it could grow without bound.
Related articles
- Stack vs Heap: Where Your Variables Actually Live
- How a Compiler Turns Your Code Into Machine Instructions
- What Actually Happens When You Run a Program
- How Hash Maps Achieve O(1) Lookups
Sources and further reading
