Space Complexity Analysis of Recursive Algorithm

Space Complexity Analysis of Recursive Algorithm

When you call a function, the machine does not forget where it was. It writes down a note: "I'm paused here; when the called function returns, resume at this line with these local variables." That note is a stack frame, and it lives in a region of memory called the call stack. A recursive function calls itself before it finishes, so each call stacks a fresh note on top of the previous one. Nothing is freed until a call actually returns. That pile of pending notes is the hidden memory cost of recursion, and it is exactly what space-complexity analysis is trying to measure.

The key insight: even if a recursive function allocates no arrays and no extra data structures, it still consumes memory proportional to how deep the recursion goes. The stack itself is the cost.

Precise definition

The space complexity of an algorithm is the total auxiliary memory it needs as a function of input size n, measured at the moment of peak usage. "Auxiliary" means memory beyond the input itself. For a recursive algorithm this splits into two parts that you add together:

• Call-stack space = (maximum recursion depth) × (space used by a single frame). A frame holds the function's parameters, local variables, and return bookkeeping — typically O(1) each, so the stack cost is usually O(max depth).
• Explicit heap space = any arrays, hash maps, result lists, or memo tables the algorithm allocates.

Crucially, the depth that matters is the longest single root-to-leaf path that is alive simultaneously — not the total number of calls. A recursion tree may make thousands of calls, but if they run and return one branch at a time (depth-first), only one path's worth of frames coexist on the stack.

Worked example: two recursions, same time, different space

Compare two O(n)-time functions.

(1) Recursive sum. sum(n) = n + sum(n-1), base case sum(0)=0. Call sum(4). The frames pile up before any returns:

• Push sum(4) → needs sum(3)
• Push sum(3) → needs sum(2)
• Push sum(2) → needs sum(1)
• Push sum(1) → needs sum(0)
• Push sum(0) → returns 0. Now the stack unwinds: 1, 3, 6, 10.

Peak stack depth = 5 frames = n+1. Each frame is O(1). So space is O(n) — even though the code allocates zero data structures. Contrast with the equivalent for loop, which reuses one accumulator: O(1) space, same O(n) time.

(2) Naive Fibonacci. fib(n) = fib(n-1) + fib(n-2). This makes O(2ⁿ) calls total — an exponential number. Yet its space is only O(n). Why? The two child calls execute sequentially: fib(n-1) fully completes and pops before fib(n-2) is even pushed. At any instant, only one root-to-leaf path is on the stack, and the longest such path (following the n-1 branch each time) has depth n. Total work is exponential; live memory is linear.

Common pitfalls & what an interviewer probes

• Confusing call count with depth. The classic trap is answering "Fibonacci is O(2ⁿ) space." No — that's the time. Space is O(n). Interviewers deliberately pick recursions where time and space diverge to see if you understand the stack.
• Forgetting the stack entirely. Candidates report O(1) space for recursive sum or recursive tree traversal because "I didn't allocate anything." The implicit stack is real memory and counts.
• Ignoring per-frame payload. If each call copies a slice/substring — e.g. helper(s[1:]) in Python — each frame holds O(n) data, so depth O(n) × O(n) per frame = O(n²) space. Passing indices instead keeps frames O(1).
• Tree recursion depth. DFS on a tree/graph costs O(height). A balanced tree is O(log n); a degenerate (linked-list-shaped) tree is O(n). State best vs worst honestly.
• Tail-call optimization (TCO). A tail-recursive call can, in principle, reuse the current frame → O(1) stack. But be honest: C, Java, Python, and JavaScript engines generally do not guarantee TCO. Assume O(depth) unless the language/compiler promises otherwise (Scala, some C++/GCC configs do).

When it matters in practice & trade-offs

Stack space is scarce and enforced by the OS — commonly ~1–8 MB per thread, versus gigabytes of heap. That is why deep recursion triggers stack overflow long before you run out of heap. Recursing over a list of a million elements will crash even though the same data fits easily in an array. This is the real-world reason to convert deep linear recursions to iteration or an explicit heap-allocated stack.

The trade-offs against neighbouring complexity classes:

• O(1) vs O(n) stack: linear recursion (sum, list traversal) is elegant but O(n) space; the loop version is O(1). Prefer iteration when depth scales with input and could be large.
• O(log n) is the sweet spot: balanced divide-and-conquer (binary search, merge on a balanced split, balanced-tree DFS) reaches only O(log n) depth — negligible. This is why balanced structures are prized.
• Memoization trades space for time: memoized Fibonacci cuts time from O(2ⁿ) to O(n) but adds an O(n) heap table on top of the O(n) stack. You spend memory to buy speed — the fundamental space/time trade-off.
• Iterative + explicit stack: when you need DFS semantics without risking overflow, move the stack to the heap (a vector/ArrayList). Same O(depth) asymptotics, but heap is vast and won't blow the thread limit.

Key takeaways

• Recursion's space cost is maximum recursion depth × per-frame size, plus any explicit heap allocations — the call stack counts even when you allocate nothing.
• Space depends on the longest live root-to-leaf path, not the total number of calls: naive Fibonacci is O(2ⁿ) time but only O(n) space.
• Depth is O(n) for linear recursion, O(height) for tree DFS (O(log n) balanced, O(n) degenerate); copying data per call multiplies the frame cost.
• Because the OS caps stack size (~MBs), deep recursion overflows early — convert to iteration or an explicit heap stack when depth scales with input, and remember most mainstream languages do not guarantee tail-call optimization.