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.setrecursionlimitsys.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 nn levels deep uses $O(n)$ auxiliary space just for frames, even if it never allocates a single list.

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))

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 RecursionErrorRecursionError instead. You can raise the cap with sys.setrecursionlimitsys.setrecursionlimit, but that doesn’t grow the underlying OS stack — it just changes when Python’s own counter gives up.

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))

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))

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:

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))

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.

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.setrecursionlimitsys.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.