Recursion and Call Stack Space
What you'll learn: How recursive function calls consume memory on the call stack and how to calculate the space complexity of recursive algorithms.
The Core Idea
When you write a recursive function, each function call gets added to the call stack — a special area of memory that tracks active function calls. Every recursive call takes up space to store:
- Local variables
- Function parameters
- Return address (where to go back after the call finishes)
The space complexity of a recursive algorithm depends on the maximum depth of this call stack — how many function calls can be active simultaneously at the worst moment.
Analyzing Call Stack Depth
Think of the call stack like a stack of plates. Each recursive call adds a plate. The stack only shrinks when a function returns. The highest the stack ever gets determines your space complexity.
Example: Factorial
factorial(5) calls factorial(4) calls factorial(3) calls factorial(2) calls factorial(1)
Maximum depth = 5 calls active at once = O(n) space complexity
Example: Binary Search (Recursive) Each call reduces the problem size by half. Maximum depth = log n levels, so O(log n) space complexity.
Why This Matters
Even if your algorithm doesn't use extra arrays or data structures, recursion itself consumes memory. Deep recursion on large inputs can cause stack overflow errors. This is why analyzing call stack space is essential for understanding total space requirements.
Key Takeaway: The space complexity of a recursive algorithm is determined by the maximum call stack depth — count the deepest chain of simultaneous recursive calls to find your bound.