Why does a recursive step that returns a description of its next call, instead of making the call, keep stack depth constant?

middlemust knowfreq 50%

answer

who makes the next call?
the step finishes first
a value that says what to do next
one invocation at a time
depth becomes loop turns

basics

~20 s

Each step finishes and returns before the next one starts, so its space is gone when the next begins. A driver loop, not the step, makes every call, so only one step is ever in progress.

solid answer

~40 s

The step's job now ends at here is what to do next, returned as a value: a zero-argument function, or a small tagged value naming the next step. Control goes back to the caller and the step is finished. A driver loop takes that value, invokes it, gets the next one, and repeats until a step returns a value tagged as final rather than as more work. The same number of invocations happen in the same order, but sequentially instead of nested, so depth turns into loop turns. This flattens the call that is a step's last act; it needs no guarantee from the runtime, because it is ordinary code.

The step's job now ends at `here is what to do next`, returned as a value: a zero-argument function, or a small tagged value naming the next step. Control goes back to the caller and the step is finished. A driver loop takes that value, invokes it, gets the next one, and repeats until a step returns a value tagged as final rather than as more work. The same number of invocations happen in the same order, but sequentially instead of nested, so depth turns into loop turns. This flattens the call that is a step's last act; it needs no guarantee from the runtime, because it is ordinary code.

code

pseudocode · 6 lines

pseudocode

function processFrom(step)
    if step.isFinal then
        return step.result
    return processFrom(step.next)

// 50,000 approvals: 50,000 invocations unfinished at once

go deeper

for a junior

Hold on to one image: the step hands back a note saying what to do next, and a loop does the calling. Nothing else needs to be memorised to follow a trampolined function.

for a middle

Be able to name the three parts out loud — a step that returns a description, a value that distinguishes more work from a finished answer, and the loop that invokes descriptions until it sees the second kind. Say why only one invocation is ever live.

for a senior

Show that you know the boundary: this flattens the call that is a step's last act, and one handler that recurses directly puts the depth straight back. Mention that it costs a turn and an allocation per step.

for a principal

The judgment is whether unbounded depth is a real risk for this engine. Imposing the returning style on every handler is a cost paid by everyone who extends the system, and it is worth paying only where chain length is decided by data you do not control.

The problem this solves

A workflow engine walks an approval chain: every approval decides which approval comes next. Written as direct recursion, a step function calls itself on the next step, and that inner invocation begins while the outer one is still unfinished — the outer one has promised to hand back whatever the inner one produces. On a chain of tens of thousands of approvals, tens of thousands of invocations are in progress at the same instant. Some languages promise that a call made as a function's very last act reuses the caller's space; many make no such promise at all. A technique that belongs to the paradigm rather than to one runtime cannot rest on a guarantee half of its audience does not have.

A trampoline is that technique. It runs the same recursion with never more than one step in progress.

The inversion: return the call instead of making it

Three things change, and only three:

The step stops calling. Instead of invoking the next step, it builds a description of that invocation — a zero-argument function that will run it when asked, or a small tagged value naming the next step and its input.
The step returns that description. Having returned, the step is finished: it holds nothing, waits for nothing, and its space is reclaimed before anything else runs.
A driver loop does all the calling. It invokes the description it holds, receives the next description, and repeats.

The loop needs one more thing in order to stop: the returned value must say which of two things it is. More work carries a description the loop should invoke. Finished carries the answer the loop should hand back. That distinction has to be visible in the value itself — if one value could be read either way, the loop cannot decide whether to run it or return it.

One turn of the loop

The loop holds the most recent value.
If that value is tagged finished, the loop returns the answer inside it and stops.
Otherwise the loop invokes the description, which runs exactly one step from entry to return.
The value that step returns replaces the one the loop held, and the previous description is dropped.

Nothing in that cycle nests. Step n+1 begins only after step n has returned, which is exactly the property direct recursion lacks.

Where the depth went

The recursion did not disappear; it changed axis. For a chain of n steps, n invocations still run, in the same order, doing the same work. Before the rewrite, n measured how much was in progress at once. After it, n counts turns of the loop.

	direct recursion	trampolined
who invokes step n+1	step n, before it finishes	the driver loop, after step n finished
in progress at once	n invocations	one invocation
what grows with n	space held by unfinished work	loop turns, and descriptions made then dropped
how it ends	the base case returns through every caller	a step returns the finished tag to the loop
what it needs from the runtime	a call-elimination guarantee, at depth	nothing beyond ordinary calls and values

That last row is the reason the technique exists. It is ordinary code: a function that returns values, and a loop that runs them.

What it does not do

It does not reduce the number of invocations. The same n calls happen, plus a loop turn and usually one allocation each.
It does not help a step that still invokes the next one before returning. The rewrite is the returning, not the wrapping: a description built and then immediately run inside the same step nests exactly as before.
It flattens only the call that is a step's last act. Work a step must perform after the next step's result comes back cannot simply be returned; that pending work has to become a value of its own first.
It is not an optimisation. A trampolined chain does more work per step than the recursion it replaces; what it buys is that the chain's length stops being a limit.
It is not local. One handler in the chain that recurses directly re-creates the nesting everything else gave up performance to avoid.

What an interviewer is listening for

The sentence that separates a candidate who has done this from one who has read about it is who makes the call. A weak answer describes wrapping things in closures and hopes the depth somehow behaves; a strong one says the step finishes and returns, and the loop — the only caller in the design — starts the next one. The second thing worth volunteering is the boundary: this flattens the last call, and anything still pending after that call needs a further transform before a loop can drive it.

## The problem this solves A workflow engine walks an approval chain: every approval decides which approval comes next. Written as direct recursion, a step function calls itself on the next step, and that inner invocation begins while the outer one is still unfinished — the outer one has promised to hand back whatever the inner one produces. On a chain of tens of thousands of approvals, tens of thousands of invocations are in progress at the same instant. Some languages promise that a call made as a function's very last act reuses the caller's space; many make no such promise at all. A technique that belongs to the paradigm rather than to one runtime cannot rest on a guarantee half of its audience does not have. A **trampoline** is that technique. It runs the same recursion with never more than one step in progress. ## The inversion: return the call instead of making it Three things change, and only three: - **The step stops calling.** Instead of invoking the next step, it builds a **description** of that invocation — a zero-argument function that will run it when asked, or a small tagged value naming the next step and its input. - **The step returns that description.** Having returned, the step is finished: it holds nothing, waits for nothing, and its space is reclaimed before anything else runs. - **A driver loop does all the calling.** It invokes the description it holds, receives the next description, and repeats. The loop needs one more thing in order to stop: the returned value must say which of two things it is. *More work* carries a description the loop should invoke. *Finished* carries the answer the loop should hand back. That distinction has to be visible in the value itself — if one value could be read either way, the loop cannot decide whether to run it or return it. ## One turn of the loop 1. The loop holds the most recent value. 2. If that value is tagged finished, the loop returns the answer inside it and stops. 3. Otherwise the loop invokes the description, which runs exactly one step from entry to return. 4. The value that step returns replaces the one the loop held, and the previous description is dropped. Nothing in that cycle nests. Step n+1 begins only after step n has returned, which is exactly the property direct recursion lacks. ## Where the depth went The recursion did not disappear; it changed axis. For a chain of n steps, n invocations still run, in the same order, doing the same work. Before the rewrite, n measured how much was in progress at once. After it, n counts turns of the loop. | | direct recursion | trampolined | |---|---|---| | who invokes step n+1 | step n, before it finishes | the driver loop, after step n finished | | in progress at once | n invocations | one invocation | | what grows with n | space held by unfinished work | loop turns, and descriptions made then dropped | | how it ends | the base case returns through every caller | a step returns the finished tag to the loop | | what it needs from the runtime | a call-elimination guarantee, at depth | nothing beyond ordinary calls and values | That last row is the reason the technique exists. It is ordinary code: a function that returns values, and a loop that runs them. ## What it does not do - It does not reduce the number of invocations. The same n calls happen, plus a loop turn and usually one allocation each. - It does not help a step that still invokes the next one before returning. The rewrite is the returning, not the wrapping: a description built and then immediately run inside the same step nests exactly as before. - It flattens only the call that is a step's **last act**. Work a step must perform *after* the next step's result comes back cannot simply be returned; that pending work has to become a value of its own first. - It is not an optimisation. A trampolined chain does more work per step than the recursion it replaces; what it buys is that the chain's length stops being a limit. - It is not local. One handler in the chain that recurses directly re-creates the nesting everything else gave up performance to avoid. ## What an interviewer is listening for The sentence that separates a candidate who has done this from one who has read about it is *who makes the call*. A weak answer describes wrapping things in closures and hopes the depth somehow behaves; a strong one says the step finishes and returns, and the loop — the only caller in the design — starts the next one. The second thing worth volunteering is the boundary: this flattens the last call, and anything still pending after that call needs a further transform before a loop can drive it.

What must the returned value let the driver loop tell apart, and what happens if it cannot?
Two readings: more work to invoke, and a finished answer to hand back. If a single value could be either, the loop has no rule for choosing between invoking it and returning it, so it either stops early on a description or tries to invoke a plain result. A two-variant value, or a tag the loop checks, is the minimum.
Does the trampolined version perform fewer calls than the direct recursion?
No. For a chain of n steps it performs the same n step invocations, plus a loop turn and typically one allocation per step. Nothing was removed; the calls were made sequential instead of nested. The win is in what is in progress at once, never in total work done.
A handler builds a description of the next step and then invokes it before returning. What has it bought?
Nothing. The nesting is back: the inner step now runs inside the outer one, so both are unfinished at the same time, and the allocation for the description is pure overhead. The deferral only exists if the description leaves the step unrun, as the returned value.

It is the difference between a clerk who carries the form to the next desk and waits there, and a clerk who hands back a note saying which desk is next. In the second office one runner does all the walking, and no clerk is ever left standing.

saying these in an interview costs you the question

Claims the trampoline removes the recursive calls rather than un-nesting them
Says the depth only drops because the compiler eliminated the tail call
Thinks the driver loop must know in advance how many steps remain
Believes returning a function defers nothing unless the language is lazy
Assumes a step may call the next one directly if it returns quickly

Why does a recursive step that returns a description of its next call, instead of making the call, keep stack depth constant?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The problem this solves

The inversion: return the call instead of making it

One turn of the loop

Where the depth went

What it does not do

What an interviewer is listening for

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

The problem this solves

The inversion: return the call instead of making it

One turn of the loop

Where the depth went

What it does not do

What an interviewer is listening for

answer

go deeper