After a tail-position accumulator rewrite, is a recursive ledger fold stack-safe?

middlemust knowfreq 48%

answer

two different claims are being merged
which half does your source control
who decides whether the frame is reused
eligibility is not the same as elimination
count the frames per ledger entry

basics

~20 s

Not by itself. Tail position is a property of your code; eliminating the caller's frame is a property of the runtime, and many runtimes never do it. Without a guarantee, depth still grows by one per entry.

solid answer

~50 s

The rewrite makes the call eligible for tail-call elimination; it does not perform it. Tail position is static and decidable by reading the source, whereas elimination — reusing the dead frame instead of pushing a new one — is a contract the compiler and runtime either offer or refuse. Where they refuse, the accumulator version has exactly the same depth curve as the original: one frame per entry, so a ledger of unknown length is unbounded depth. What counts as proof is a specified guarantee covering the call shape and build mode you ship, not a run that happened not to fail; a best-effort optimization can vanish in a debug build or when an inlining decision changes. If there is no guarantee, bound the depth or iterate over the unbounded dimension and keep recursion for the provably shallow parts.

The rewrite makes the call *eligible* for tail-call elimination; it does not perform it. Tail position is static and decidable by reading the source, whereas elimination — reusing the dead frame instead of pushing a new one — is a contract the compiler and runtime either offer or refuse. Where they refuse, the accumulator version has exactly the same depth curve as the original: one frame per entry, so a ledger of unknown length is unbounded depth. What counts as proof is a specified guarantee covering the call shape and build mode you ship, not a run that happened not to fail; a best-effort optimization can vanish in a debug build or when an inlining decision changes. If there is no guarantee, bound the depth or iterate over the unbounded dimension and keep recursion for the provably shallow parts.

code

pseudocode · 10 lines

pseudocode

SUM-LEDGER(entries, i, acc)
    if i == length(entries)
        return acc
    return SUM-LEDGER(entries, i + 1, acc + amount(entries[i]))

// call site over a ledger of unknown length
total = SUM-LEDGER(entries, 0, 0)

// depth without elimination: length(entries)
// depth with elimination:    1

go deeper

for a junior

Remember the two-part answer: writing the call in tail position is your half, actually reusing the frame is the runtime's half. Do not promise stack safety from the source alone.

for a middle

Explain the mechanism — reuse the dead frame and jump instead of pushing — and be able to say what depth the fold reaches when the runtime declines, namely one frame per entry.

for a senior

Demonstrate that you check the guarantee's scope before depending on it: self versus general tail calls, build modes, and calls sitting inside exception-handling regions.

for a principal

Own the rule for the codebase: which targets guarantee elimination, what the depth bound is on the ones that do not, and what reviewers do when a recursive traversal takes unbounded input.

Two different claims, routinely merged into one. "This function is tail-recursive" is a claim about your source code: the recursive call's value is returned unchanged, so the caller's frame is dead at the moment of the call. "This function runs in constant stack space" is a claim about the machine that executes it: the implementation actually reuses that dead frame instead of pushing a new one. The first is tail position; the second is tail-call elimination (also called proper tail calls, or tail-call optimization). The rewrite buys you the first. Only the runtime can give you the second.

What elimination actually does. For a self tail call, the transformation is small: overwrite the current frame's parameters with the new argument values and jump back to the function's entry point instead of executing a call instruction. The recursion becomes a loop in the generated code, and stack depth stops depending on input size. For a general tail call — to a different function, or through mutual recursion — the implementation must additionally arrange the outgoing arguments in the caller's own frame and transfer control without a return address, which requires the calling convention to support it. Neither is exotic, but both are choices an implementation makes, not consequences of how you wrote the source.

Do the depth arithmetic before you claim safety. A fold over a ledger of unknown length recurses once per entry, so without elimination the depth equals the number of entries. A month of transactions might be fine; a full-history replay or a stream with no known bound is not. The failure is also input-dependent and therefore invisible in tests built from small fixtures — which is why "it ran fine on the sample file" is not evidence. Nothing about the accumulator changed this: it changed eligibility, and the depth curve is identical if the runtime does not act on that eligibility.

Guarantee versus observation. There are three meaningfully different states, and only the first is safe to build on:

State	What you can rely on
Specified guarantee	Elimination holds for the constructs the spec names, in every build mode
Best-effort optimization	It may happen in optimized builds, may vanish in a debug build, an interpreter tier, or after an inlining decision changes
Never eliminated	Depth always grows with input; the rewrite is a style choice only

An experiment that did not overflow tells you which state you were in for that build, that input size, and that call shape. It does not promise the next one.

Scope caveats even where a guarantee exists. A guarantee is usually narrower than "all tail calls everywhere". Common restrictions: self-recursion only, so mutual recursion still stacks; the call must not sit inside an exception-handling or scoped-cleanup region, which silently reintroduces pending work; the target must be statically known, so a call through a function value or an overridable method may not qualify; and the guarantee may be tied to a specific compilation mode. Read the scope, not the headline.

Ecosystems have made visibly different calls here. The Scheme standard mandates proper tail calls, and Lua guarantees them too, so unbounded loops written as recursion are ordinary practice there. The JVM and CPython do not eliminate tail calls at all, and CPython's designers have argued publicly that the lost stack traces are not worth the win. Several compiled languages sit in between, eliminating self tail calls in optimized builds while promising nothing in the language specification. The same source shape gets three different runtime behaviours — which is precisely why the property has to be established per target, not assumed from the code.

How to answer this in an interview. Say the distinction first, then the consequence: tail position is necessary but not sufficient; elimination is the sufficient half and it is the runtime's to give. Then name what you would actually do when the guarantee is absent — bound the input, process in chunks, or use a loop for the unbounded traversal and keep recursion for the bounded, shallow parts. The candidate who says "it's tail-recursive now, so it can't blow the stack" has stated a property of the code and drawn a conclusion about the machine, and that is the single most common wrong answer in this area.

**Two different claims, routinely merged into one.** "This function is tail-recursive" is a claim about your source code: the recursive call's value is returned unchanged, so the caller's frame is dead at the moment of the call. "This function runs in constant stack space" is a claim about the machine that executes it: the implementation actually reuses that dead frame instead of pushing a new one. The first is *tail position*; the second is *tail-call elimination* (also called proper tail calls, or tail-call optimization). The rewrite buys you the first. Only the runtime can give you the second. **What elimination actually does.** For a self tail call, the transformation is small: overwrite the current frame's parameters with the new argument values and jump back to the function's entry point instead of executing a call instruction. The recursion becomes a loop in the generated code, and stack depth stops depending on input size. For a general tail call — to a different function, or through mutual recursion — the implementation must additionally arrange the outgoing arguments in the caller's own frame and transfer control without a return address, which requires the calling convention to support it. Neither is exotic, but both are choices an implementation makes, not consequences of how you wrote the source. **Do the depth arithmetic before you claim safety.** A fold over a ledger of unknown length recurses once per entry, so without elimination the depth equals the number of entries. A month of transactions might be fine; a full-history replay or a stream with no known bound is not. The failure is also input-dependent and therefore invisible in tests built from small fixtures — which is why "it ran fine on the sample file" is not evidence. Nothing about the accumulator changed this: it changed *eligibility*, and the depth curve is identical if the runtime does not act on that eligibility. **Guarantee versus observation.** There are three meaningfully different states, and only the first is safe to build on: | State | What you can rely on | | --- | --- | | Specified guarantee | Elimination holds for the constructs the spec names, in every build mode | | Best-effort optimization | It may happen in optimized builds, may vanish in a debug build, an interpreter tier, or after an inlining decision changes | | Never eliminated | Depth always grows with input; the rewrite is a style choice only | An experiment that did not overflow tells you which state you were in *for that build, that input size, and that call shape*. It does not promise the next one. **Scope caveats even where a guarantee exists.** A guarantee is usually narrower than "all tail calls everywhere". Common restrictions: self-recursion only, so mutual recursion still stacks; the call must not sit inside an exception-handling or scoped-cleanup region, which silently reintroduces pending work; the target must be statically known, so a call through a function value or an overridable method may not qualify; and the guarantee may be tied to a specific compilation mode. Read the scope, not the headline. **Ecosystems have made visibly different calls here.** The Scheme standard mandates proper tail calls, and Lua guarantees them too, so unbounded loops written as recursion are ordinary practice there. The JVM and CPython do not eliminate tail calls at all, and CPython's designers have argued publicly that the lost stack traces are not worth the win. Several compiled languages sit in between, eliminating self tail calls in optimized builds while promising nothing in the language specification. The same source shape gets three different runtime behaviours — which is precisely why the property has to be established per target, not assumed from the code. **How to answer this in an interview.** Say the distinction first, then the consequence: tail position is necessary but not sufficient; elimination is the sufficient half and it is the runtime's to give. Then name what you would actually do when the guarantee is absent — bound the input, process in chunks, or use a loop for the unbounded traversal and keep recursion for the bounded, shallow parts. The candidate who says "it's tail-recursive now, so it can't blow the stack" has stated a property of the code and drawn a conclusion about the machine, and that is the single most common wrong answer in this area.

The rewrite passed a test over ten million entries without failing. What has that proved?
That elimination happened for that build, that call shape, and that input size. If the behaviour is a best-effort optimization rather than a specified guarantee, it can disappear in a debug build, an interpreter tier, or after an inlining decision changes — and the regression will surface at production scale, not in the test. Only a written contract covers future executions.
If elimination does happen, what does the generated code for a self tail call look like?
Roughly a loop: overwrite the current frame's parameters with the new argument values and jump back to the function's entry instead of executing a call. Stack depth becomes constant because no new activation record is pushed. A general tail call to another target is harder — the calling convention has to let the callee reuse a frame whose argument layout differs.
Does the accumulator rewrite buy anything at all on a runtime that never eliminates tail calls?
Only readability and a shape that ports cleanly to a mechanical loop conversion; it buys no stack safety. Treating it as a safety measure is the error. On such a target, the honest move is to make the unbounded dimension iterative and reserve recursion for structures whose depth is bounded by construction.

saying these in an interview costs you the question

Says it is tail-recursive now, so it cannot overflow
Treats tail-call elimination as automatic everywhere
Offers a large passing test as proof of a guarantee
Thinks the accumulator itself reduces stack usage
Assumes a guarantee covers mutual recursion and debug builds

After a tail-position accumulator rewrite, is a recursive ledger fold stack-safe?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions6 questions

▾related topics3 topics

answer

go deeper

context