Recursion Space Complexity: Your Stack Only Holds One Path at a Time

Look at a DFS that visits every node in a million-node tree. A million frames of stack space, right? Not even close. The call stack only ever holds the frames for the path it is currently descending, and every frame along a completed branch gets popped before the next branch starts. That single fact is the key to recursion space complexity: it explains why DFS is O(h) and not O(n), why a balanced tree is radically cheaper to recurse than a skewed one, and why you can hit a stack overflow even when your algorithm is completely correct.

Each Call Hoards Its Own Private Frame

When your program calls a function, the runtime allocates a stack frame for that call. The frame is a small slab of memory containing everything the call needs to execute independently from every other invocation: the return address (where control jumps when the function finishes), the saved frame pointer that anchors the previous frame, local variables, and any arguments that did not fit in CPU registers.

On a 64-bit system, a minimal frame costs at least 16 bytes just for the return address and saved base pointer. Add local variables and the alignment padding the ABI requires (x86-64 demands 16-byte alignment, which is a bureaucratic overhead you never asked for but will get regardless), and a non-trivial function easily spends 64 to 128 bytes per frame. The frame is small, but you get one per active call, and "active" means "not yet returned."

The region of memory backing all of this is the call stack: a contiguous block the OS allocates when the thread starts. Linux and macOS give the main thread 8 MB. macOS non-main threads get 512 KB. Windows defaults to 1 MB. That sounds comfortable, until you realize a deeply nested recursion burns through it one frame at a time.

The call stack grows down; the heap grows up. The guard page between them is what turns a stack overflow into a crash rather than silent corruption.

Born on Call, Dead on Return

The call stack is LIFO in the most literal sense. When your function calls another, a new frame is pushed on top. When a function returns, its frame is popped and control jumps back to the return address stored in the frame below.

A frame occupies stack space from the moment its function is called until the moment that function returns. That is the whole rule, and it is why depth drives the space cost.

Look at this DFS:

def dfs(node):
    if node is None:
        return
    process(node)
    dfs(node.left)
    dfs(node.right)

When dfs(node.left) runs, there is a frame for the current call sitting on the stack waiting for it to finish. When the entire left subtree is explored, dfs(node.left) returns, its frame is gone, and only then does dfs(node.right) start pushing new frames. The right subtree's frames and the left subtree's frames never coexist on the stack. The left subtree tidies up after itself before the right subtree even gets to exist. Very considerate.

Each snapshot shows only the frames on the current active path. The right subtree's frames don't stack on top of the left's, they replace them.

The maximum number of frames alive at any one moment equals the deepest point reached so far. For a tree with height h, DFS never has more than h + 1 frames on the stack, regardless of how many nodes it will eventually visit.

That is the core result: recursion uses O(max depth) space, not O(total calls).

Three Space Classes, All Explained by Depth

With that principle in place, the common cases follow directly.

O(n): linear chains. Factorial is a chain where every call must wait for the next one before it can return. At the deepest point, factorial(n) has pushed n frames simultaneously.

def factorial(n):
    if n <= 0:
        return 1
    return n * factorial(n - 1)  # must wait for the result before multiplying

The multiplication n * factorial(n-1) is pending, so the frame cannot pop. Every frame from factorial(n) down to factorial(1) is alive at once. Full chain, full stack.

O(log n): halving at each level. Recursive binary search makes exactly one recursive call per level and each level cuts the search space in half. Depth is log₂ n. Binary search on a billion elements uses about 30 frames, not a billion.

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

Only one branch is ever active at a time, and each branch is half the previous problem.

O(h): tree DFS, where h is not fixed. For a balanced binary tree, h = O(log n), so DFS uses O(log n) space. For a skewed tree where every node has only one child (essentially a linked list), h = n so DFS uses O(n) space. The algorithm is identical; the tree shape determines the cost.

A skewed tree from a sorted insert sequence is all it takes to turn your O(log n) recursion into an O(n) stack hog.

This is why algorithm tables write O(h), not O(n), for DFS. O(n) is a valid upper bound, but O(h) is more informative when you care about the actual structure of the input.

Stack Overflow Is the OS Running Out of Patience

Stack overflow happens when the call chain pushes past the end of that fixed stack region. The thread's stack grows downward toward a guard page. When a frame writes into the guard page, the OS delivers a fault signal and the process crashes: segmentation fault on Linux, access violation on Windows. Not a graceful exit.

Python builds a software guard in front of that hardware one. The default recursion limit is 1000 frames. Exceed it and you get a clean RecursionError: maximum recursion depth exceeded rather than a raw segfault and a core dump. Python is polite about telling you that you have a problem. You can raise the limit with sys.setrecursionlimit, but raising the limit does not give you more stack space; it just delays the crash. You are not solving the problem. You are rescheduling it.

Stack Overflow (the website) and stack overflow (the crash) are two very different things. One will save you. The other will not.

The actual fix is to either reduce depth (use a balanced structure, or limit the recursion's reach) or move the bookkeeping off the call stack entirely.

Tail Calls: The Exit Nobody Built the Door For

The runtime only needs to keep a frame alive if there is pending work after the recursive call returns. When the recursive call is the very last thing a function does, there is nothing pending.

Compare the two factorial versions:

# Standard: the multiplication is PENDING after the recursive call returns
def factorial(n):
    if n <= 0:
        return 1
    return n * factorial(n - 1)

# Tail-recursive: accumulator carries the state, nothing pending after the call
def factorial_tail(n, acc=1):
    if n <= 0:
        return acc
    return factorial_tail(n - 1, n * acc)

In factorial_tail, the recursive call is the final action. The current frame has no unfinished business. A compiler that implements tail-call optimization (TCO) can reuse the current frame in place, turning O(n) stack space into O(1).

Python deliberately does not implement TCO. Guido van Rossum's position, stated on his Neopythonic blog, is that eliminating stack frames would corrupt tracebacks and confuse developers who rely on them for debugging. It is a defensible position. You are still allowed to be annoyed by it.

JavaScript's ES2015 specification requires TCO but only Safari's JavaScriptCore implements it in practice. Safari doing the responsible thing while everyone else ignores the spec is not the outcome anyone predicted. GCC and Clang apply TCO automatically at -O2. Kotlin exposes it with the tailrec keyword. The compiler transforms the function into an iterative loop at compile time, because the JVM has no general TCO guarantee.

If TCO is not available and your recursion is deep and tail-recursive, the pragmatic answer is iterative conversion.

Iterative Conversion Moves the Stack to the Heap

Any recursion can be rewritten with an explicit stack on the heap. The same DFS:

def dfs_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        process(node)
        stack.append(node.right)
        stack.append(node.left)

The space complexity does not change. This still uses O(h) memory. What changes is where that memory comes from. The heap can grow to gigabytes; the call stack is capped at a few megabytes. Moving the explicit stack to the heap gives you the same algorithmic behavior against a budget that is orders of magnitude larger. The heap will not ghost you at depth 512.

It often runs faster too. Function call overhead is not trivial, and a simple array-backed stack is more cache-friendly than a chain of heap-allocated frames.

Why Every Textbook Writes O(h) and What It's Hiding

Most algorithm space analyses split the cost into two parts: the data structure space and the recursion stack space. For DFS on a tree, you see O(n) + O(h), where O(n) covers the nodes stored in memory and O(h) covers the call stack. For a balanced tree these are O(n) + O(log n) = O(n). For a skewed tree they are both O(n).

Merge sort is O(n log n) time and O(n) space: O(n) for the scratch arrays used during merging, plus O(log n) for the recursion stack. The stack term is dominated by the arrays, so the total is O(n). People sometimes forget the stack term exists because it is usually dominated.

The O(log n) stack term is real. You just never feel it because O(n) is already bigger. Until you're on a skewed input and suddenly the "dominated" term is the one overflowing.

When the recursion is deep and per-call overhead is substantial, or when you are working within tight memory limits, it is the number that bites you. The call stack term is never free, even when it is small.

Build the mental model now and you will not be caught off guard when a theoretically O(log n) recursion hits the stack limit on a degenerate linear input.

Recap

• Every function call allocates a stack frame holding the return address, saved frame pointer, and local variables.
• Frames are pushed on call and popped on return. The stack holds only the frames on the current active call chain.
• Space complexity is O(max depth), not O(total calls). For DFS on a tree, max depth is the height h.
• O(h) equals O(log n) for balanced trees and O(n) for skewed ones.
• Stack overflow is the OS fault that fires when the stack region is exhausted. Python's RecursionError at depth 1000 is a software guard in front of that.
• Tail-call optimization reuses the current frame when the call is the last action. Python opts out deliberately. C compilers do it at -O2.
• Iterative conversion moves the explicit stack to the heap, trading call stack budget for heap budget with no change to asymptotic complexity.

---

Working through space complexity explanations out loud is harder than reading about them. If you want to practice articulating the O(h) vs O(n) distinction under interview pressure, SpaceComplexity runs voice-based mock interviews that push you to explain your reasoning in real time, then score you on whether the explanation would actually hold up with an interviewer.

---

The time complexity side of recursion, covering recursion trees and the Master Theorem, is in Recursion Time Complexity: The Tree, the Recurrence, and the Master Theorem. For how memoization reshapes both the time and space picture, see Memoization Time Complexity: One Formula for Every Top-Down DP. Backtracking adds an extra wrinkle where the call stack cost and the output-copying cost are separate terms; that breakdown is in Backtracking Time Complexity.

Further reading

• Call stack (Wikipedia)
• Tail call (Wikipedia)
• x86 Disassembly / Functions and Stack Frames (Wikibooks)
• Stack Frame Layout on x86-64 (Eli Bendersky)
• Python: Handling Recursion Limit (GeeksforGeeks)