What is space complexity, and how much stack space does recursion use?

Q: What is space complexity, and how much stack space does recursion use?

**Target Audience:** Beginners preparing for coding interviews — you should know what a function call and a loop are. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain words first, then tagged with `📌 Interview term:` so you also learn the exact vocabulary an interviewer expects. Every depth, count and error message on this page comes from running the Python code shown; the **Verified** section quotes that output. This page assumes you know [Big-O notation](/interview-question/what-is-big-o-notation); recursion itself is introduced on [what recursion and a base case are](/interview-question/what-is-recursion-and-what-is-a-base-case). ## 1. Why This Even Matters — A Story First You are reading a recipe. Step 3 says "make the sauce (see page 40)". You put a sticky note on step 3 so you remember where you were, and turn to page 40. Page 40 says "first make the stock (see page 72)". Another sticky note, turn to page 72. When the sto

The problem

Question presented to candidate: "We talk a lot about time complexity. What is space complexity? And if I write a recursive function in Python, how much memory does the recursion itself use — for example for a recursive sum, a recursive binary search and naive Fibonacci?"

What a strong answer should cover:

Space complexity is how extra memory grows with n; distinguish auxiliary space (extra) from total space (including the input), and say whether the output counts.
Each active call occupies a stack frame, so recursion costs O(maximum recursion depth) stack space — not O(number of calls).
Worked examples: recursive sum O(n) stack, recursive binary search O(log n), naive Fibonacci O(2ⁿ) time but O(n) stack, DFS O(height).
Converting deep recursion to a loop or an explicit stack, and in-place algorithms with O(1) extra space.
Python specifics: the default recursion limit of 1000 (RecursionError), no tail-call elimination in CPython, and slicing (nums[1:]) copying memory at every level.

Code / implementation expected: Yes — a recursive function and its iterative or explicit-stack rewrite in Python, with the stack depth stated.

dsa
complexity
recursion
space

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what a function call and a loop are. Difficulty: Easy Language: Python 3

How to read this doc: Each idea is explained in plain words first, then tagged with 📌 Interview term: so you also learn the exact vocabulary an interviewer expects. Every depth, count and error message on this page comes from running the Python code shown; the Verified section quotes that output. This page assumes you know Big-O notation; recursion itself is introduced on what recursion and a base case are.

1. Why This Even Matters — A Story First

You are reading a recipe. Step 3 says "make the sauce (see page 40)". You put a sticky note on step 3 so you remember where you were, and turn to page 40. P

The solution is hidden so you can try first

9 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonMeasure the call-stack depth of recursive and iterative code

Practice

PythonO(1) vs O(n) extra space, and replacing recursion with an explicit stack

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.