Space Complexity and Recursion Depth
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Time is not the only budget. A solution can run fast and still run out of memory. Learn to count the extra memory a solution needs, including the hidden memory of recursion.
Space is the extra memory you use
Space complexity is how much extra memory a program needs as the input size n grows. The input itself is usually not counted; only the new memory the solution creates is.
Count only the new memory your solution creates, not the input it was given. Reversing a list in place needs two index variables: O(1). A reversed copy needs n more places: O(n).
def reverse_in_place(items): left, right = 0, len(items) - 1 while left < right: items[left], items[right] = items[right], items[left] left += 1 right -= 1
prices = [10, 20, 30, 40]reverse_in_place(prices)print(prices)print(prices[::-1])Example 1 · A copy or the same list
def reversed_copy(items): return items[::-1]
def reversed_in_place(items): items.reverse() return items
data = [1, 2, 3]print(reversed_copy(data) is data)print(reversed_in_place(data) is data)False True
What this code does
items[::-1]builds a new list, so it is not the same object: O(n) extra space.items.reverse()rearranges the list that was passed in: O(1) extra space.- The in-place version also changes the caller's list, so use it only when that is fine.
The function reversed the same list using two variables. The slice built a second list of the same size.
Recursion uses the call stack
Call stack is the memory where Python keeps one frame for every function call that has not finished. Its height is the recursion depth, and each frame costs memory.
Each call that has not returned keeps its own frame in memory. sum_to(4) must wait for sum_to(3), so five frames exist at once. No list was built, yet memory grows with n.
def sum_to(n): if n == 0: return 0 return n + sum_to(n - 1)
print(sum_to(4))Example 2 · Measuring the depth
max_depth = 0
def count_down(n, depth=1): global max_depth max_depth = max(max_depth, depth) if n == 0: return count_down(n - 1, depth + 1)
count_down(10)print(max_depth)11
What this code does
- The
depthargument grows by one on every nested call. - Counting down from 10 reached depth 11, which means eleven frames alive at once.
Example 3 · Halving recursion is shallow
def depth_binary(low, high, target, depth=1): if low > high: return depth mid = (low + high) // 2 if mid == target: return depth if mid < target: return depth_binary(mid + 1, high, target, depth + 1) return depth_binary(low, mid - 1, target, depth + 1)
print(depth_binary(0, 999_999, -1))20
What this code does
- A recursive binary search halves the range on every call.
- For a million items the depth is about 20, so the space is O(log n) and the recursion limit is no danger.
- Recursion that shrinks by one each time reaches depth n instead.
A recursion that goes n levels deep holds n + 1 frames, so its space is O(n).
Python's recursion limit
Recursion limit is the deepest call depth Python allows, 1000 by default. Going deeper raises RecursionError, which protects the program from using all its memory.
Python stops runaway recursion at about 1000 frames and raises RecursionError. A loop has no such limit, so deep work belongs in a loop.
import sys
def depth(n): return 0 if n == 0 else 1 + depth(n - 1)
print(sys.getrecursionlimit())try: depth(5000)except RecursionError: print("too deep")Example 4 · RecursionError or a loop
def sum_recursive(n): return 0 if n == 0 else n + sum_recursive(n - 1)
def sum_loop(n): total = 0 for value in range(1, n + 1): total += value return total
print(sum_loop(100_000))try: print(sum_recursive(100_000))except RecursionError: print("RecursionError")5000050000 RecursionError
What this code does
- The loop uses two variables, O(1) space, and has no depth limit.
- The recursive version needs 100,000 frames and stops with RecursionError.
- Interviewers often ask you to convert a deep recursion into a loop.
The default limit is 1000 and a depth of 5000 crossed it. You can raise the limit, but a loop is the safer fix.
Trade space for time
Extra memory often buys speed. A set of seen ids turns a repeated scan into one lookup, at the price of O(n) space. Choose using the constraints on both time and memory.
seen = set()orders = [7, 3, 9, 3]for order in orders: if order in seen: print("duplicate", order) seen.add(order)print(len(seen))Example 5 · Memoising Fibonacci, then removing the memory
def fib_memo(n, cache): if n < 2: return n if n not in cache: cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n]
cache = {}print(fib_memo(50, cache), len(cache))
a, b = 0, 1for _ in range(50): a, b = b, a + bprint(a)12586269025 49 12586269025
What this code does
- The cache stores 49 answers, so time is O(n) and space is O(n), and the recursion is 50 deep.
- The loop keeps only the last two values: same answer, O(n) time and O(1) space.
- Each step down this list uses less memory, but the code is a little less obvious.
Example 6 · Generator or list
n = 100_000squares_list = [i * i for i in range(n)]print(len(squares_list))
squares_gen = (i * i for i in range(n))print(sum(squares_gen))100000 333328333350000
What this code does
- The list comprehension stores all 100,000 squares at once: O(n) space.
- The generator creates one square at a time and
sumconsumes it: O(1) space. - Use a generator when you only need to loop over the values once.
The set holds the 3 distinct ids. For a million distinct ids it would hold a million.
Next step
Check your understanding
11 quick questions