Space, in-place work, and the cost of recursion

Memory is the second budget, and a recursion spends it invisibly, one stack frame per call.

Time is not the only thing an algorithm spends. A procedure that runs in a fraction of a second and asks for sixteen gigabytes is as unusable as one that runs for a week. Memory has its own accounting, and it has one trap that time does not.

Here are two ways to reverse a list. One builds a new list; the other exchanges entries where they sit. Both are correct. Watch the count of extra cells each one needs.

The copying version's extra memory grows with the input; the swapping version's does not, whatever the size. That distinction has a name and a definition.

Total space and auxiliary space

Total space is everything the program holds at once, including the input. Auxiliary space is everything except the input: the working memory the algorithm asked for on top of what it was handed. Unless a claim says otherwise, a space bound quoted for an algorithm means auxiliary space.

An algorithm is called in-place when its auxiliary space is $\Theta(1)$, that is, a fixed number of extra cells no matter how large the input is. The swapping reversal is in-place: it uses two indices and one temporary. The copying reversal uses $\Theta(n)$ auxiliary space.

The measure is the peak, not the total ever allocated. A loop that creates and discards one temporary value per pass has used $n$ temporaries over its life and holds one at a time, so its auxiliary space is $\Theta(1)$.

Recursion spends memory you did not write down

Every call a program makes puts a stack frame in memory: a small block holding that call's parameters, its local variables, and the place to return to. The frame lives until the call returns. In a recursion, none of the outer calls have returned while the inner ones run, so all their frames are alive at once.

The peak number of frames alive together is the recursion depth, and it is auxiliary space every bit as much as an array is. Run this and watch the depth grow with the input while the loop version stays flat.

The recursive sum uses $\Theta(n)$ auxiliary space and the loop uses $\Theta(1)$, for identical arithmetic. Nothing in the recursive source code mentions memory, which is what makes this cost easy to miss.

The limits are real and they are low. Python refuses to go beyond about a thousand nested calls by default and raises an error rather than crashing. A typical C++ program gets a stack of about 8 megabytes, and a frame of 50 bytes gives roughly 160000 frames before the program is killed with no useful message. Either way, a recursion whose depth is $n$ is unsafe once $n$ reaches the hundreds of thousands.