Recursive list reversal is called O(1) space; why does that fail on a 10-million-node feed?

## Recursion depth is space, and the bound is not optional Space complexity counts every byte the algorithm needs beyond its input, and a pending call frame is such a byte. Each frame holds the parameters, the return address and any live locals of a call that has not yet returned. If an algorithm recurses to depth d, then d frames coexist at the deepest point, so its auxiliary space is Ω(d) — regardless of how little each frame contains. For list reversal written recursively over a newest-first notification feed, the recursion descends one node at a time to the end of the feed before doing any work, so d = n. The auxiliary space is O(n). Calling it O(1) because "no new nodes are allocated" is the single most common wrong answer on this topic: it counts heap allocation and ignores the stack. ## The classic shape, and why it is not tail-recursive The usual recursive formulation says: reverse everything after the current node, then attach the current node to the end of that result. ``` reverse(node): if node == null or node.next == null: return node newHead = reverse(node.next) node.next.next = node node.next = null return newHead ``` The two rewiring lines run *after* the recursive call returns. A call is in tail position only when it is the very last action of its caller, with nothing left to do afterwards — which is not the case here. So even a runtime that eliminates tail calls cannot flatten this version; the pending work is real and must be remembered. An accumulator variant is genuinely tail-recursive: `rev(curr, prev)` flips one link and then calls itself as its final action, mirroring the iterative loop exactly. But a tail call is only free where the runtime is required or willing to reuse the frame, and mainstream runtimes disagree sharply on this: Scheme implementations and most functional-language runtimes guarantee it, while the JVM and CPython do not eliminate tail calls at all. Writing tail-recursively is therefore a portability bet, not a space guarantee. ## What ten million actually means Stack size is a bounded, configured resource — typically a fixed allocation per thread, orders of magnitude smaller than the heap, and the same limit is shared by every frame the request is already holding. Whatever the exact per-frame size, the arithmetic is not close: ten million frames against a stack that holds thousands to a few hundred thousand of them fails by two or more orders of magnitude. That is why "increase the stack size" is a bad answer here. It converts a hard failure at n into a hard failure at some larger n, multiplies the memory reserved by every thread in the service, and leaves you with an algorithm whose safety depends on an operational setting nobody will remember when the feed grows. ## Where the failure lands, and why that detail is worth knowing Because the classic version rewires only on the way up, the stack is exhausted during descent — before a single link has been changed. The feed is left exactly as it was. That is a genuinely useful property to state in an interview, because it distinguishes this failure from the far nastier one where a mutation aborts halfway and leaves the structure inconsistent. But it is a consequence of where the writes sit, not a safety guarantee: the accumulator variant rewires on the way *down*, so if it exhausts the stack without tail-call elimination, it leaves a partially reversed feed with a severed tail. ## When recursion is still the right call Recursion is not banned; unbounded recursion over externally sized data is. If the recursion depth is bounded by something you control — a segment of at most a few hundred nodes, a balanced structure of logarithmic depth — the frames are bounded and the clearer code can win. The rule that scales is: *if the depth is a function of an input size you do not bound, do not recurse.* Feed lengths, user-supplied collections and imported batches all fall on the wrong side of that line. ## What to say in the room Three sentences carry the whole answer. Recursion depth is auxiliary space, and here it is O(n). The classic form is not in tail position, and even the tail-recursive rewrite only helps on runtimes that eliminate tail calls. The iterative three-pointer walk is the same O(n) time with genuinely O(1) space, so on an unbounded feed there is no tradeoff to weigh — the iterative version is strictly better, and the only argument for the recursive one is teaching clarity.