Recursion vs Iteration

## What a call frame is actually holding Every time a function calls itself, the runtime allocates a frame holding three things: the **parameter values** for this invocation, its **local variables**, and a **return address** — the point in the body to resume at once the call comes back. The call stack is the sequence of those frames, one per level of depth, and it is the reason recursion needs no data structure of your own: the runtime is maintaining one for you. Converting recursion to iteration is the question of how much of that frame you actually need. ## The shape that collapses into a loop Consider walking a chain of transaction records to produce a running account balance. Each record has an amount and a pointer to the next one; the recursion adds the amount and calls itself on the next record, returning that result unchanged. When a frame does nothing after its recursive call — no arithmetic on the result, no comparison, no logging, no cleanup, and there is only **one** self-call — the return address is worthless. There is nothing to resume; the answer the sub-call produces is the answer this level produces. And if the return address is worthless, the whole frame is worthless the moment the call is made, because nobody will ever look at those parameters again. So you can reuse a single set of variables instead of allocating a frame per level: - the parameters that change per level become loop variables; - the recursive call becomes "assign the new values and continue"; - the base case becomes the loop condition (or an early exit). That rewrite is mechanical, and it is exact: the same operations happen in the same order and produce the same result. This is a source-level transformation you perform by hand; it does not depend on the runtime doing anything clever for you. ## What the rewrite does and does not buy **Time complexity is unchanged.** The loop performs exactly the work the recursion performed. You save the per-call overhead of setting up and tearing down frames, which is a constant factor and often a real one on a hot path, but a quadratic algorithm is still quadratic after you loop it. **Auxiliary space genuinely improves**, from one frame per element down to a constant handful of variables. This is the point people usually miss: recursion depth *is* space, and a chain-walking recursion over a million records is a million live frames. **Crash behaviour improves most of all.** The call stack is typically a fixed-size region reserved when the thread is created; it does not grow on demand the way ordinary allocated memory does. A recursion whose depth scales with input size is a latent crash waiting for the day the input gets big enough, and the loop version has no depth at all. ## The shape that does not collapse Now take a product catalogue: a category holds a stock count and a list of sub-categories, and the recursion sums a category's own stock plus the totals of all its children. Two things break the easy rewrite: 1. **More than one self-call per frame.** After returning from the first child, the frame must go on and process the second, so it has to survive. 2. **Work after the call.** The parent adds up what the children returned; that addition is the resume point the return address was pointing at. Both mean the pending state of every ancestor along the current path must be retained. Removing the call stack does not remove that requirement — it only moves it. The honest form of "any recursion can be written as a loop" is *any recursion can be written as a loop plus a stack you maintain yourself*, and that version is you re-implementing, by hand, the bookkeeping the runtime was doing correctly and invisibly. ## Deciding whether to bother Rewrite when the depth scales with data you do not control, when the frame overhead shows up in a measured hot path, or when you need to pause, checkpoint, or bound the traversal — an explicit stack is inspectable state, a call stack is not. Leave it recursive when the depth is bounded by the shape of the data (a fan-out tree a handful of levels deep) and the recursive version reads like the definition of the problem, which it usually does. "Loops are faster than recursion" is not, on its own, a reason: it is a constant-factor claim about a thing you have not measured.