Space Complexity and the Call Stack

Time complexity asks “how much work?” Space complexity asks “how much extra memory?” — and recursion is the single most common way beginners accidentally pay for memory they didn’t know they were spending.

What you’ll learn

The difference between input space and auxiliary space.
How every recursive call pushes a stack frame, and why depth costs memory.
Python’s default recursion limit, and sys.setrecursionlimit.
In-place vs extra-space techniques, with a runnable comparison.

What counts as space complexity

Total memory used by a running program has two parts:

Input space — memory to hold the input itself. Usually not counted, since you can’t avoid it.
Auxiliary space — everything extra your algorithm allocates: new lists, hash sets, and (often forgotten) the call stack used by recursion.

When people say an algorithm is ” $O(1)$ space,” they mean $O(1)$ auxiliary space — the input itself doesn’t count against that budget.

The call stack, frame by frame

Every function call — recursive or not — pushes a stack frame holding its local variables and where to return to. A recursive call doesn’t share a frame with its caller; it gets a brand-new one stacked on top. So a recursive function that goes n levels deep uses $O(n)$ auxiliary space just for frames, even if it never allocates a single list.

sketch Call stack for factorial(5) p5.js

Frames push as the recursion goes deeper, then pop and multiply on the way back up. Each frame is real memory the recursive call is holding onto.

stack_depth.py

import sys
 
def factorial(n, depth=1):
    print("  " * depth + f"factorial({n}) called at depth {depth}")
    if n <= 1:
        return 1
    return n * factorial(n - 1, depth + 1)
 
print("current recursion limit:", sys.getrecursionlimit())
print("result:", factorial(5))

Python’s recursion limit

CPython caps recursion depth (1000 by default) to protect the real process stack from overflowing and crashing. Go past it and Python raises a clean RecursionError instead. You can raise the cap with sys.setrecursionlimit, but that doesn’t grow the underlying OS stack — it just changes when Python’s own counter gives up.

recursion_limit.py

import sys
 
def count_down(n):
    if n == 0:
        return 0
    return 1 + count_down(n - 1)
 
sys.setrecursionlimit(3000)
print("new limit:", sys.getrecursionlimit())
print("depth reached:", count_down(2000))

Dry run

The stack, frame by frame

sum_to(3) with the naive recursion return n + sum_to(n - 1):

Event	Frames live	Deepest frame
`sum_to(3)` enters	1	`n = 3`, waiting on `sum_to(2)`
`sum_to(2)` enters	2	`n = 2`, waiting on `sum_to(1)`
`sum_to(1)` enters	3	`n = 1`, waiting on `sum_to(0)`
`sum_to(0)` enters	4	base case, returns 0
unwinding	3, 2, 1, 0	each frame adds its `n` and returns

Nothing is computed on the way down. All four frames sit waiting simultaneously, each holding its own n, and the additions only happen during the unwind. That is why the space is $O(n)$ even though the function allocates no data structure at all — the frames are the allocation.

Contrast the loop: one accumulator, one counter, no frames. $O(1)$ . Same $O(n)$ time, and the entire difference is invisible in a complexity annotation that only mentions time.

Where the limit actually bites

Measured on this interpreter:

Quantity	Value
`sys.getrecursionlimit()`	1000
Frames actually reached before `RecursionError`	998

The two differ because the measuring function’s own frames count too — the limit is on total stack depth, not on your function’s depth. So “I have 1000 frames of headroom” is already slightly wrong, and any wrapper, decorator, or comprehension in the chain eats into it.

What this means in practice: a linked list of 10,000 nodes, a path-shaped tree, a 200x200 grid flood-fill in the worst case — all legal inputs, all past the limit. The failure is a RecursionError mid-traversal, not a slow answer, and it will not show up on the small test cases.

sys.setrecursionlimit(300000) raises the Python-level guard but not the operating system’s actual stack, so a deep enough recursion segfaults the interpreter instead of raising. The safe version raises the limit and runs the work on a thread with a large threading.stack_size(). The better version converts to an explicit stack.

In-place vs extra space

The same operation can cost $O(1)$ or $O(n)$ auxiliary space depending on whether you build a new structure or modify the existing one:

in_place_vs_extra.py

def reverse_extra_space(nums):
    # O(n) auxiliary space: builds a brand-new list
    return nums[::-1]
 
def reverse_in_place(nums):
    # O(1) auxiliary space: swaps within the same list
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums
 
data = [1, 2, 3, 4, 5]
print("extra space:", reverse_extra_space(data))
print("in place   :", reverse_in_place(data))

Practice

Drill 1 — in-place swap. Complete the classic two-pointer in-place reversal.

Drill 2 — classify the space cost. Given a function’s name, decide whether it’s one of the extra-space (non-in-place) ones.

Drill 3 — measure recursion depth. Complete a function that reports how many stack frames a recursive call chain would use.

Complexity

Space complexity has three sources, and only the first is usually noticed.

Source	Cost	Example
Data you allocate	$O(\text{size})$	a `visited` set, a DP table, a result list
Call-stack frames	$O(\text{depth})$	any recursion — invisible in the source
Interpreter overhead per object	large constant	a Python `int` is ~28 bytes; a `list` of `n` ints is `n` pointers plus `n` objects

Structure	Time	Space
Recursive tree walk	$O(n)$	$O(h)$ — $O(\log n)$ balanced, $O(n)$ degenerate
Iterative walk with an explicit stack	$O(n)$	$O(h)$ heap-allocated — no frame limit
Morris traversal	$O(n)$	$O(1)$ — rewires and restores the tree
BFS over a tree	$O(n)$	$O(w)$ , the widest level — up to $n/2$
Two-pointer array rearrangement	$O(n)$	$O(1)$
Building a result list	$O(n)$	$O(n)$ — conventionally not counted as extra space

Three conventions worth stating out loud rather than assuming:

The output does not count as extra space, by convention. So “reverse an array in $O(1)$ space” means “beyond the array itself”. Say which convention you are using and the ambiguity disappears.
$O(h)$ is not $O(\log n)$ . It is $O(\log n)$ only when balanced, and the degenerate case is $O(n)$ — which in CPython is a crash rather than a slowdown.
A generator is $O(1)$ where a comprehension is $O(n)$ . sum(x*x for x in data) allocates nothing; sum([x*x for x in data]) materialises the whole list first. One character.

Interview follow-ups

They ask	What they’re checking	The answer
“What is the space complexity?”	Whether you count the stack	Name both parts: allocated data plus $O(\text{depth})$ of frames for any recursion. Most candidates report only the first
“Your solution is recursive — what does that cost?”	The invisible allocation	$O(h)$ stack frames, $O(\log n)$ balanced and $O(n)$ degenerate. In CPython the degenerate case is a `RecursionError` at ~1,000 frames, so it is a correctness problem, not a performance one
“Make it $O(1)$ space”	Knowing the escape routes	Convert to iteration (moves the stack to the heap — still $O(h)$ , but no frame limit), or use a technique that needs no stack at all: two pointers on an array, Morris traversal on a tree
“Does the output array count?”	Whether you state conventions	Conventionally no — “extra” space excludes the required output. Worth saying explicitly rather than assuming you agree
“Why is BFS more space than DFS on a tree?”	Precision	BFS holds the widest level, about $n/2$ for a complete tree, so $O(n)$ ; recursive DFS holds one root-to-leaf path, $O(\log n)$ balanced. You pay space for the level structure
“Can you just raise the recursion limit?”	Whether you know it is a half-fix	It raises Python’s guard but not the OS stack, so a deep enough recursion segfaults instead of raising. The safe form combines `setrecursionlimit` with a thread that has a larger `threading.stack_size()`; the better form converts to an explicit stack
“How much memory does a list of a million ints use?”	The constant factor	Far more than 4 MB. The list holds a million pointers (~8 MB) and each `int` is a separate ~28-byte object — so tens of MB. `array.array('i')` or `numpy` stores them unboxed
“What is $O(h)$ for a linked list?”	Whether you notice the shape	$O(n)$ — a list is a maximally degenerate tree. Which is why recursive linked-list solutions break on the large tests and iterative ones do not

Self-check

pch.quizTag pch.quizDefaultTitle

A recursive sum over n elements allocates no data structure. What is its space complexity?

pch.quizShowAnswer

B — O(n) -- the call frames are the allocation, and all n sit live simultaneously before any unwinding — Nothing is computed on the way down: every frame holds its own n and waits for the one below it, so all n frames coexist before the first addition happens. The frames are invisible in the source, which is exactly why this is the most commonly missed part of a space analysis.
`sys.getrecursionlimit()` returns 1000, but measuring how deep you can actually go gives 998. Why the gap?

pch.quizShowAnswer

B — The limit is on total stack depth, so the measuring function's own frames count too -- and any decorator or wrapper in the chain eats into your headroom — Measured 998 against a stated 1000. The practical consequence is that "I have 1000 frames" is already optimistic, and it shrinks further inside a comprehension, a decorator, or a nested call. It is also why the limit is best treated as "about a thousand" rather than an exact budget.
Is `sys.setrecursionlimit(300000)` a complete fix for deep recursion?

pch.quizShowAnswer

B — No -- it raises Python's guard but not the OS stack, so a deep enough recursion segfaults instead of raising a catchable error — The guard exists to turn a hard crash into a catchable exception; removing it removes the safety net, not the underlying limit. A segfault is strictly worse than a RecursionError -- no traceback, no cleanup. The safe workaround pairs it with a thread created after threading.stack_size() is increased; the better answer is an explicit stack.
Which traversal achieves O(1) space on a binary tree?

pch.quizShowAnswer

B — Morris traversal -- it temporarily rewires child pointers and restores them — Morris threading uses the tree's own null right-pointers as temporary breadcrumbs, so it needs no stack or queue at all. Recursive in-order is O(h) frames; an explicit stack is O(h) on the heap -- better, because there is no frame limit, but not constant. BFS is O(w), the widest level, which can be n/2.
Does the returned result array count toward "extra" space?

pch.quizShowAnswer

B — Conventionally no -- extra space excludes the required output, but it is worth stating the convention rather than assuming agreement — This is a convention, not a theorem, which is exactly why naming it is useful. "Reverse the array in O(1) space" clearly means beyond the array; "return the products in O(1) extra space" (LC 238) relies on the same reading. Saying which convention you are using removes an ambiguity the interviewer would otherwise have to raise.
`sum(x*x for x in data)` versus `sum([x*x for x in data])`. What is the difference?

pch.quizShowAnswer

B — The generator streams and is O(1) extra space; the list comprehension materialises all n values first, O(n) — One character changes the memory profile from constant to linear. The list version is marginally faster for small n because generator resumption has overhead, but on large data the allocation dominates and the generator wins on both axes. It is the cheapest space optimisation available in Python.

Recall card

Space has three sources: data you allocate, call-stack frames, and Python’s per-object overhead. The middle one is invisible in the source and the most often missed.
Any recursion costs $O(\text{depth})$ frames. All of them are live simultaneously — nothing is computed on the way down.
$O(h)$ is $O(\log n)$ only when balanced; degenerate is $O(n)$ , and in CPython that is a RecursionError, not a slowdown.
The limit is ~1,000 and you get less: measured 998 against a stated 1000, because every frame in the chain counts.
setrecursionlimit is a half-fix — it removes Python’s guard, not the OS stack, so deep enough recursion segfaults. Pair it with a bigger threading.stack_size(), or convert to an explicit stack.
Escape routes to $O(1)$ : two pointers on an array, Morris traversal on a tree. An explicit stack is still $O(h)$ but heap-allocated, so no frame limit.
BFS is $O(w)$ (widest level, up to $n/2$ ); recursive DFS is $O(h)$ . BFS buys level structure with space.
The output conventionally does not count as extra space — say so rather than assume it.
A generator is $O(1)$ where a comprehension is $O(n)$ . One character.
A linked list is a degenerate tree, so $O(h) = O(n)$ — which is why recursive list solutions fail the large tests.

Recap

Total memory = input space + auxiliary space; auxiliary space is what Big-O space complexity actually measures.
Recursion’s auxiliary cost is its stack frames — $O(\text{depth})$ , even if no extra data structure is ever built.
Python’s default recursion limit is ~1000; sys.setrecursionlimit raises it but does not grow the real OS stack.
In-place techniques trade a bit of code complexity for $O(1)$ auxiliary space instead of $O(n)$ .

Next: Python Recursion and Iterative Conversion — turning recursive calls into explicit loops and stacks.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading