Space complexity and the call stack

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
def depth(n: int) -> int:
    if n == 0:
        return 0
    return 1 + depth(n - 1)

print(depth(50))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 50

Right: 50 nested calls are pending at the deepest point.

Fifty frames are alive at once at the bottom of the recursion, which is its O(n) space cost.

Why not the others?
  • B 1. Each call adds one before returning, so the total is the depth.
  • C 0. The base case returns 0, but each level above it adds 1.

30-second answer

Count the extra memory beyond the input: new lists, dicts, sets and queues, plus the call stack. Each pending recursive call holds a frame, so recursion uses space equal to its maximum depth: O(log n) for binary search done recursively, O(h) for a tree walk, O(n) for recursion on a list one item at a time.

Practise saying it · 30 s. No recording, just a timer

Explain space complexity with recursion.

Say your answer out loud, then check which of these points you covered:

  • Extra memory beyond input
  • Stack depth counts
  • Slicing in recursion adds up

Deep dive

The output usually does not count as extra space when the question requires it; say which convention you use.

Slicing in recursive calls (f(xs[1:])) adds O(n) per level, often O(n²) total memory and time.

Iterative versions can turn O(n) stack into O(1) or into an explicit stack of the same size.

Common mistakes

  • Calling a recursive function O(1) space because it creates no lists.
  • Forgetting the queue in BFS, which can hold a whole level.

Senior take & follow-ups

Always mention the call stack when you use recursion; it is the space cost people forget.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is the space cost of memoisation?

    Show hint

    One entry per distinct subproblem, plus the stack depth.

  2. Does Python free frames as soon as a call returns?

    Show hint

    Yes; only the active chain of calls takes stack space.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.