Why is a recursive function that allocates no data structures still not O(1) space?
answer
- What must survive while a call waits?
- The caller is suspended, not finished
- Parameters, locals, return address per call
- Count frames alive at the deepest point
- Peak depth times frame size
basics
~20 sEvery unfinished call keeps an activation record on the call stack — parameters, locals, return address. A recursion descending n levels holds n frames at once, so it costs O(n) space even when it allocates nothing.
solid answer
~50 sSpace complexity counts everything alive at one moment, and that includes the bookkeeping the machine keeps for you, not just what you explicitly allocate. Each call that has started but not returned owns an activation record holding its arguments, its local variables, the return address it must resume at, and saved caller state. A caller cannot finish until its callee returns, so the frames of the whole current chain of unfinished calls are alive simultaneously; the peak is the maximum depth reached. Walking a chain of `n` linked records with one call per record therefore holds `n` frames at the bottom of the descent, giving O(n) space with O(1) explicitly allocated data. Note that depth, not total call count, is what is charged: a recursion that makes exponentially many calls but nests only `n` deep still peaks at O(n) frames.
code
pseudocode · 10 lines// each log record links to the next; sum severity over the chain
TOTAL_SEVERITY(record)
if record == NIL
return 0
s = record.severity
rest = TOTAL_SEVERITY(record.next)
return s + rest
// caller
total = TOTAL_SEVERITY(head)go deeper
Recall that every call in progress occupies a frame holding its parameters, locals and return address, and that the frames of all unfinished calls exist at the same time. State space as two parts: allocated data plus recursion depth.
Explain why a caller's frame cannot be released while a callee runs, and separate total call count (time) from maximum nesting depth (stack space). Be ready to compute the peak from a fragment you are shown.
Show that you cost recursion depth as a real resource when reviewing designs: on unbounded input, an O(n)-depth routine is a scaling failure waiting for a big enough input, and reviews should ask for the depth function, not just the time bound.
Own the standard: what does your codebase consider acceptable depth on input you do not control, and who checks it? Frame the tradeoff as recursion's readability against a hard, unrecoverable resource ceiling that nothing in normal testing surfaces.
## What space complexity actually counts Space complexity is the peak amount of memory an algorithm needs held **at one time** in order to keep running. It has two components, and beginners routinely count only the first: 1. **Explicitly allocated data** — the arrays, maps, buffers and objects the code creates. 2. **Execution bookkeeping** — the state the machine must retain so that every call in progress can be resumed and finished. A recursive routine can score zero on the first and still be linear on the second. That is exactly why "it allocates nothing, so it is O(1) space" is one of the most reliably wrong sentences a candidate can say. ## Anatomy of one activation record When a call begins, the execution machinery reserves a contiguous block on the call stack — an **activation record**, usually called a **stack frame**. Its contents, in rough order of universality: | Slot | What it is for | | --- | --- | | Parameters | The argument values this particular call received | | Local variables | Anything declared inside this call's body | | Return address | The exact point in the caller to resume at when this call finishes | | Saved caller state | Registers and frame pointers the callee is about to overwrite | | Return-value slot / padding | Room for the result and alignment the machine requires | The frame is created on entry and destroyed on return. Crucially, its lifetime is *the whole duration of the call*, not just the instant the call is executing an instruction. ## Why frames stack up instead of replacing each other A caller is suspended, not finished, while its callee runs — it still has work waiting after the call returns. Its frame therefore cannot be released. So at any instant the stack holds one frame per call in the current chain of unfinished calls: from the outermost entry point down to the call currently executing. The number of frames alive equals the **current recursion depth**, and the memory the algorithm charges is set by the **maximum depth over the whole run**. In the fragment, each record in the chain produces one nested call, and the recursive call is not the last thing the frame does — the addition happens after it returns. At the deepest point, all `n` frames are live. That is O(n) space with O(1) allocated data. ## Depth is not the same as call count Two different quantities get confused here: - **Total calls made** drives *time*. A branching recursion can make exponentially many calls. - **Maximum simultaneous frames** drives *stack space*. Only the current root-to-current-call path is alive; everything already returned is gone, and everything not yet started does not exist. So a recursion making 2^n calls but nesting only `n` deep peaks at O(n) frames, while a linear walk over `n` items makes `n` calls *and* nests `n` deep, also O(n). Same space, wildly different time. ## Why this distinction has teeth in production Memory for frames and memory for allocated data typically come from two regions with very different sizes and very different failure behaviour. The stack region for one execution context is fixed when that context starts and is usually measured in a handful of megabytes; the general allocation region is orders of magnitude larger and can grow. Exhausting the allocation region gives you pressure, collection work, or an allocation failure you can often see coming. Exhausting the stack region is abrupt: the run works, works, works, and then aborts. The O(n) you forgot to count is therefore the O(n) most likely to kill the process first. ## The definitional detail worth carrying into an interview The standard definition of **in-place** is "O(1) auxiliary space, or O(log n) when recursion is involved". That carve-out exists precisely because the discipline already agrees recursion depth is space — a recursive in-place algorithm is granted logarithmic stack, not zero stack. If someone tells you their recursive routine is in-place with no qualification, ask how deep it goes. The answer an interviewer is listening for is two-part and precise: *O(1) auxiliary data, O(n) stack from the recursion depth, therefore O(n) space.* Saying only the first half sounds like someone who has memorised a rule about allocation rather than someone who understands what the machine is holding.
- If a recursion makes 2^n calls in total, how many frames does it hold at once?At most one per level of nesting, so O(n) — only the current chain of unfinished calls is alive. Calls that already returned released their frames, and calls not yet started have none. Total call count drives time; maximum nesting depth drives stack space. Conflating the two is how people report exponential space for a recursion that is linear in stack.
- Does the size of a call's local variables change the frame count?No — the frame count is set by depth alone. But the bytes are set by depth multiplied by frame size, and frame size grows with the number and size of parameters, locals, saved registers and alignment padding. Since the stack limit is a byte budget, a routine with a large local buffer exhausts the stack at a much shallower depth than a lean one running the same shape of recursion.
- Why does exhausting stack space behave so differently from exhausting allocated memory?Frames live in a region fixed in size when the execution context starts, typically a few megabytes, and the runtime cannot quietly extend it mid-run. Allocation regions are far larger and can grow. So allocation pressure shows up as slowdown or a failure you can often handle, while stack exhaustion is a hard abrupt abort at the moment the next frame will not fit.
Think of a pile of half-finished paperwork: starting a call puts a new form on top, and you cannot file the form underneath until the one above it comes back to you. The pile, not the total number of forms you handled, is what has to fit on the desk.
saying these in an interview costs you the question
- It allocates nothing, so it is O(1) space
- Only explicitly allocated data counts toward space complexity
- A frame is released as soon as the next call starts
- Stack space is effectively unlimited, the runtime grows it
- Total number of calls equals the frames held at once