The stack nobody counts

A recursive function’s frames are memory. They are allocated on entry, freed on return, live simultaneously with all their ancestors, and they come out of a region that is typically a few megabytes and is not growable.

Nothing about that is controversial and almost nothing about it is measured. A complexity table gives merge sort’s space as $\Theta(n)$ for the buffer and stops; the $\Theta(\log n)$ of frames underneath is smaller and therefore ignored. That is fine for merge sort. It is not fine in general, because the stack is the resource whose exhaustion is an error rather than a slowdown, and because for several algorithms it is the only auxiliary space there is.

Peak and total, again #

The counted array tracks two things about calls: how many were made, and how deep it ever got. At $n = 4{,}096$ on random input:

Eight thousand calls and fourteen frames. That is the peak-against-total distinction applied to the stack, and the ratio is enormous because a recursion tree is wide and shallow: almost all of those calls have already returned by the time any given one is running.

Which of the two numbers matters depends on the question. Peak is what the stack limit is about, and it is $\log_2 n$. Total is what the call overhead is about — every call is a frame set up and torn down, arguments moved, a return address pushed — and at 8,192 calls for 4,096 elements, merge sort spends two calls per element on function-call machinery that no count on this site has ever measured.

The hybrid’s row is the interesting one. Cutting the recursion off at 16 elements takes the call count from 8,192 to 512 — a factor of sixteen — and the depth from 14 to 10. The essay on the cutoff concluded that the crossover it exists for is entirely in memory traffic, and named three effects the instrument could not see, the first of which was “recursion has a cost that no array count sees”.

That effect is now measurable, and it is a factor of sixteen in call count. It is still not a duration and this site still does not have one. But “the hybrid makes one sixteenth as many calls” is a specific, exact, reproducible statement about a mechanism that was previously a hand-wave, and it is the right order of magnitude to explain a crossover that the traffic count only just accounts for.

One traversal, three space profiles #

Depth-first search is the cleanest case, because it has three standard implementations that do byte-identical counted work and hold three different things.

On a 12 × 12 grid, all three perform 528 adjacency scans and 144 visits — the gate requires it — and at their peak they hold:

Three numbers spanning a factor of twelve for what is usually discussed as one question.

The reason they differ is that they hold different things, and the distinction is easy to miss because both of the depth-first versions are described as “using a stack”.

The explicit-stack version holds the frontier. It pushes every unvisited neighbour of every vertex it pops. So the stack contains vertices that have been discovered and not yet processed, which on a grid is a band of them.

The recursive version holds the path. One frame per vertex on the route from the source to wherever the search currently is. Its neighbours are not stored anywhere; they are recomputed from the adjacency when the frame resumes.

Those coincide on some graphs and diverge wildly on others. On a path graph of 1,024 vertices, the explicit-stack version holds one vertex and the recursive version holds 1,024. On a random sparse graph of 1,024 vertices they are 553 and 724, close enough to be indistinguishable in practice.

So “depth-first search uses $O(V)$ space” is true of one implementation, “$O(\text{frontier})$” is true of another, and neither is a property of depth-first search.

Why the failure mode is different #

Everything else this site measures degrades. A quadratic sort of a large array takes a long time; a cache-hostile access pattern costs a factor; an algorithm at ten times the comparison floor does ten times the comparing. In every case the program produces the right answer eventually, and the cost is somebody’s patience.

A stack overflow is not like that. There is a limit, it is a few thousand frames, and past it the program raises an error and stops. On the machine that builds this site, first-element quicksort on a sorted array succeeds at 7,000 elements and fails at 7,015.

Three properties make this worse than an ordinary limit.

It is not a round number and it is not stable. The threshold depends on the engine, on how large each frame is, and on how much stack the caller had already used before the algorithm was entered. The same code at the same size can succeed when called from main and fail when called from six frames down inside a request handler.

It arrives at a size, not a load. Doubling the traffic to a service does not cause it; a single request with an input twice as large does. So it does not show up in load testing and it does show up on the day somebody uploads a bigger file.

It cannot be caught usefully. By the time the error is raised the stack is exhausted, so the handler that would clean up has nowhere to run. Most runtimes treat a deep enough overflow as unrecoverable.

That combination — a hard limit, at an unstable threshold, triggered by input size, unrecoverable — is why this resource deserves counting rather than an assurance that it is small.

Bounding it, for free #

The fix for quicksort is old, well known, and absent from most presentations of the algorithm, and it is worth spelling out because its cost is nothing.

After partitioning, quicksort recurses on both sides. Instead: recurse on the smaller side, and loop on the larger.

Partition as usual; compare the sizes of the two sides; make the recursive call on the shorter one; then, instead of recursing on the longer one, narrow the current bounds to it and go round the loop again. Six lines instead of four.

The recursive call is now always on a subproblem of at most half the current size, so the depth is at most $\log_2 n$ on every input — including the sorted one, including the adversarial one. The comparison count does not change by a single comparison: the same partitions happen in the same order and the same elements are compared. The $\Theta(n)$ row in the space table becomes $\Theta(\log n)$ and nothing else moves.

This is the strongest argument in the space field. A worst case that costs nothing at all to remove is one that people would remove if they knew it was there, and the reason it survives is that the resource it lives in is the one nobody counts. It is not a trade-off, it is not a tuning parameter, and it is not in most textbook presentations.

Two related manoeuvres are worth naming beside it.

Tail-call elimination does the same thing automatically, when the language guarantees it. The second recursive call in the naive version is in tail position, so a compiler that eliminates tail calls turns the naive quicksort’s depth from $n$ into the depth of the non-tail branch — which is still $n$ on sorted input unless the smaller side is chosen first. The two techniques compose and neither substitutes for the other.

An explicit stack converts the recursion into a loop over a heap-allocated array of subproblems. The depth is unchanged; what changes is that the array can grow to whatever memory allows rather than dying at the runtime’s frame limit, and that the failure becomes an allocation failure, which is catchable. This is why several production sorts do it, and the reason is not speed.

What the counters here do and do not see #

Two limits worth stating, since this essay has been quantitative about a resource whose unit is fuzzy.

A frame is charged as one slot. A real frame is a few words to a few tens of words depending on how many locals the function has, and merge sort’s frames hold four indices while quicksort’s hold two. So the numbers here compare depths honestly and compare frames against array elements only roughly. The direction is knowable: a frame is usually larger than an element, so the stack is being undercounted relative to the buffers, and quicksort’s disadvantage against heapsort is slightly greater than the figures show.

Nothing here models the runtime’s own frames. A traversal written in a language with closures, iterators or generators may allocate additional structure per level that no enter() call records. The measurements are of the algorithm’s recursion, not of the implementation’s, and on a real system the second can dominate.

Neither changes the conclusions, and both are the same shape as every honest limit in the machine field: the model is simpler than the machine, the simplification is stated, and where it is not neutral between the things being compared, the direction is given.

The cutoff divides one number and subtracts from the other #

The hybrid’s row is worth taking apart arithmetically, because it makes the independence of peak and total exact rather than merely observed.

A recursion over $n$ elements that stops at subproblems of size $c$ has $n/c$ leaves and therefore $2n/c - 1$ nodes, at a depth of $\log_2(n/c) + 1$. Put the numbers in. Uncut, $c = 1$: 8,191 calls at depth 13, against the measured 8,192 at 14. Cut at sixteen: 511 calls at depth 9, against the measured 512 at 10. Both rows recovered, both off by one in the same direction, which is the top-level call the counter includes and the arithmetic does not.

So the cutoff enters the two quantities differently. It divides the call count and subtracts from the depth. Raising $c$ from 1 to 16 removes fifteen sixteenths of the calls and four frames.

That settles what the parameter is for. As a call-count lever it is enormous and cheap: sixteen is a factor of sixteen, and the factor is linear in a constant somebody types. As a stack lever it is feeble — halving the depth needs $c = \sqrt{n}$, which at four thousand elements is a cutoff of sixty-four and at a million is a cutoff of a thousand, and a cutoff of a thousand is not an insertion-sort cutoff, it is a different algorithm.

So a cutoff is not a stack defence and should never be mistaken for one. A recursion whose depth is the problem needs the smaller-side-first change of the previous section, which turns a linear depth into $\log_2 n$ on every input at no cost at all; a cutoff applied to the same recursion turns $n$ into $n/c$, which is still linear. The two look like the same kind of intervention — both are “recurse less” — and one of them changes a class while the other changes a constant.

It also sharpens what the earlier finding bought. The cutoff essay named “recursion has a cost no array count sees” as the first of three effects its instrument could not reach, and the factor of sixteen is now that effect’s size. But the factor is in calls, which is a time-like quantity, and the four frames are in depth, which is the space-like one. A single sentence about “recursion cost” was standing in for two numbers moving by a factor of sixteen and by four, and only the first is what the crossover was about.

Which is the field’s own argument arriving inside a single parameter. Peak and total are independent, so a knob that moves both moves them by unrelated amounts, and a claim that the knob “reduces recursion” is a claim about whichever of the two the reader happens to have in mind. The honest statement of what a cutoff of sixteen does is: sixteen times fewer calls, four fewer frames, and no change whatever to the worst case that in-place is a claim is about.

Where else a recursion runs out #

Sorting is not where this bites hardest. Three ordinary situations have the same structure and worse consequences, and all three are recursions whose depth is set by the data.

Walking a degenerate tree. A binary search tree built from sorted keys has height $n-1$ — 1,022 for 1,023 keys, measured, not estimated. A recursive in-order traversal of that tree recurses once per level, so walking a tree built from ten thousand sorted keys is a recursion ten thousand deep. The structure was chosen for its $O(\log n)$ lookup; the traversal that visits it dies on the same input that ruins the lookup, and dies harder.

That is the same failure as quicksort’s and it is worse in one respect: the tree persists. A quicksort that overflows can be re-run with a different pivot rule. A tree that has been built in sorted order is a tree that every subsequent recursive traversal will fail on, until it is rebuilt.

Parsing nested input. A recursive-descent parser recurses once per level of nesting, so a JSON document with a hundred thousand nested arrays is a recursion a hundred thousand deep. This is a well-known denial-of-service vector precisely because the depth is chosen by whoever supplies the document, and the standard mitigation is an explicit depth limit checked before recursing — which is the modelled stack limit of this essay, implemented for real.

Depth-first search on a large graph. The recursive version holds the path, so a graph with a long path — a chain of dependencies, a road network, a linked list of records — gives a recursion as deep as the path is long. The explicit-stack version holds the frontier instead and does not have the problem, which is why every graph library ships the iterative one.

The pattern in all three: the recursion depth is a function of the input, the function is not obvious from the code, and the limit is not the algorithm’s to set. Where the depth is $\log n$ it can be ignored. Where it is $n$, or the height of a structure somebody else built, or the nesting of a document somebody else supplied, it is an input-controlled resource with a hard ceiling — which is the definition of something worth counting.

What the language decides #

One more thing outside the algorithm’s control, and it is the reason two correct implementations of the same recursion can have different limits.

Frame size varies with the compiler. A recursive function with six locals may get six stack slots, or two if the optimiser keeps the rest in registers, or more if it is compiled without optimisation. So the same algorithm at the same depth uses different amounts on a debug build and a release build, and the debug build is the one that runs on the developer’s machine.

Some languages remove the recursion entirely. A guaranteed tail-call elimination turns a tail-recursive walk into a loop with no frames at all. Whether a given call is in tail position is a syntactic property that a small refactor can destroy, so an algorithm’s space class can change by editing the code without changing what it computes.

Some runtimes grow the stack. A goroutine’s stack starts small and grows by copying, so the limit is memory rather than a fixed reservation, and a deep recursion becomes slow rather than fatal.

The measurement here — one frame charged as one slot, no engine assumed — sits underneath all of that, and it is the only version of the number that is a property of the algorithm rather than of the toolchain.

The same depths, three more ways #

A stack limit is a number somebody chose and the depth is a number the run produces, so both sides of the comparison are worth moving.

The third variation changes the input rather than either number, and it is the one that shows the depth is not a property of the algorithm alone.

The general point #

The site’s fields have a habit of discovering that a quantity everybody treats as one number is several. Comparisons turned out to be four counts that rank differently. Cost turned out to be operations and cache misses, disagreeing. Space turned out to be peak and total.

The stack is the same discovery one level further in. “Space” splits into buffers and frames; frames split into peak and total; and peak depth splits again by implementation, so that one algorithm has three of them. At each split, the two numbers are independent — knowing one does not give the other — and at each split the vocabulary has one word.

There is no reason to think this is the bottom. What the instrument buys is not a complete cost model but the ability to notice the next split when it appears, which is what happened here: the space counters were built to make “sorts in place” checkable, and the first thing they found was that a traversal nobody was arguing about has three answers.