Rewriting a recursive dependency walk as a loop, what must the explicit stack hold that recursion kept implicitly?

seniorshould knowfreq 40%

answer

tail position needs no stack
what survives a call is pending work
where you were and what you had
a marker for arriving versus returning
push order decides visit order

basics

~20 s

Whatever was still to be done after each pending call came back: which item is being visited, how far through its dependencies you had got, and any partial result waiting to be combined. A call in tail position leaves nothing pending, so that rewrite needs no stack at all.

solid answer

~50 s

It depends on whether the recursive call is the last thing the routine does. If it is — tail position, nothing pending after it — the rewrite is mechanical: the parameters become loop variables, the recursive call becomes reassignment plus another pass, and the base case becomes the loop's exit condition. No stack is needed because there is no pending work to remember. If work remains after the call returns, that work is what the machinery was holding for you, and the explicit stack has to hold it: the item under visit, the position within its dependency list, any accumulated partial result, and a marker for which phase to resume in when it comes back off the stack. Drop the position or the marker and you get a traversal that visits everything but runs the after-the-call step in the wrong order, or not at all.

It depends on whether the recursive call is the last thing the routine does. If it is — **tail position**, nothing pending after it — the rewrite is mechanical: the parameters become loop variables, the recursive call becomes reassignment plus another pass, and the base case becomes the loop's exit condition. No stack is needed because there is no pending work to remember. If work remains **after** the call returns, that work is what the machinery was holding for you, and the explicit stack has to hold it: the item under visit, the position within its dependency list, any accumulated partial result, and a marker for which phase to resume in when it comes back off the stack. Drop the position or the marker and you get a traversal that visits everything but runs the after-the-call step in the wrong order, or not at all.

code

pseudocode · 13 lines

pseudocode

// tail position: the call's result is returned unchanged
function drain(work, done):
    if work is empty: return done
    item = head(work)
    return drain(tail(work) + deps_of(item), done + item)

// the same computation, no stack needed
function drain(work, done):
    while work is not empty:
        item = head(work)
        work = tail(work) + deps_of(item)
        done = done + item
    return done

go deeper

for a junior

Know the two shapes apart: a call that is the last thing done needs nothing remembered, while a call with work waiting after it does. That distinction is the whole basis of the rewrite.

for a middle

Do the tail conversion on a whiteboard without hesitating — parameters to variables, call to reassignment, base case to exit condition — and say why the other shape needs somewhere to put the pending work.

for a senior

Design the stack record: item, phase, position, partial result. Then show the rewritten walk produces the same order as the original, and say what you had to reverse to get it.

for a principal

Judge when the rewrite earns its cost. Bounded depth and a clear recursive statement argue for leaving it alone; unbounded input, or a need to checkpoint and resume a long walk, argues for making the pending work a value you own.

Tail recursion is already a loop

Start with the easy half. A routine whose recursive call is the last thing it does — the result of that call is returned unchanged, nothing is added to it, nothing is combined with it — has no pending work at the moment of the call. Everything it will ever need is in the arguments it is passing along. That is exactly the shape of a loop:

Recursive form	Loop form
parameters	loop variables initialised from them
the base-case test	the loop's exit condition, negated
the recursive call's arguments	the new values assigned to those variables
returning the call's result	falling out of the loop and returning the variables

Nothing is lost in that translation, and no auxiliary structure appears, because there was nothing pending to store.

Non-tail recursion has work waiting

Now the interesting half. A dependency walk that installs an item after all of its dependencies are done has work waiting at every call: when the call returns, this routine still has to install this item, and possibly still has more dependencies to walk. Two things survive the call and must be recoverable:

Where you were — which item, and how far through its dependency list.
What you had — any partial result accumulated so far that the returning value will be combined with.

A rewrite that keeps only the items and drops the position is the usual mistake. It visits everything, but it cannot tell a first encounter from a return, so the step that was supposed to run after the children never runs in the right place.

What goes on the explicit stack

The practical recipe is to push a small record rather than a bare item:

The item itself.
A phase marker saying whether this record represents arriving at the item or returning to it — the moral equivalent of the resume point the machinery held for you.
If the dependencies are walked one at a time rather than all pushed at once, the index of the next one.
The partial result, when the walk is accumulating something rather than acting by side effect.

With the marker in place the loop becomes uniform: pop a record; if it says arriving, push the same item back marked returning and then push its dependencies marked arriving; if it says returning, do the after-the-children work. The order the dependencies come back in depends on the order you push them, which is one more thing the recursion was deciding for you silently.

The rewritten loop needs its own argument

Once the stack is explicit, the property to preserve is about a data structure you can point at: the records on the stack, together with the items already finished, account for exactly the work the walk still owes. That is a strictly better position than the recursive version, where the pending work lives somewhere you cannot inspect. It is also where termination is argued again from scratch: the measure is the number of unvisited items paired with the stack's size, and without a record of what has already been visited a cyclic graph pushes forever.

Converting a recursion to a loop never removes the obligation to show it stops. It relocates it.

Why do the rewrite at all

The depth a chain of calls may reach is capped by the environment, while a stack you build is a structure whose size you choose and can bound yourself.
An explicit stack can be inspected, checkpointed, paused and resumed — a long walk can report progress or restart where it left off, which a chain of pending calls cannot.
The work still owed becomes a value, so the property you are preserving can be stated over it rather than over invisible machinery.
Against that: the loop form is longer and the phase marker is easy to get wrong, so the recursive version is usually the clearer one to write first and the one to keep when depth is bounded by the domain.

What the rewrite must not change

The result. A conversion is worth nothing if the iterative walk visits the same items in a different order and the after-the-children step was order-sensitive. The check is to name the order the recursive version produced, name the order the stack produces, and reconcile them — pushing dependencies in reverse is the usual adjustment, because the last one pushed is the first one popped.

The interview signal

A candidate who says "use a stack" has the headline. The one who says what goes in each record, and why the phase marker is there has done it, and will not ship the version that visits everything in the right set and the wrong order.

## Tail recursion is already a loop Start with the easy half. A routine whose recursive call is the **last** thing it does — the result of that call is returned unchanged, nothing is added to it, nothing is combined with it — has no pending work at the moment of the call. Everything it will ever need is in the arguments it is passing along. That is exactly the shape of a loop: | Recursive form | Loop form | |---|---| | parameters | loop variables initialised from them | | the base-case test | the loop's exit condition, negated | | the recursive call's arguments | the new values assigned to those variables | | returning the call's result | falling out of the loop and returning the variables | Nothing is lost in that translation, and no auxiliary structure appears, because there was nothing pending to store. ## Non-tail recursion has work waiting Now the interesting half. A dependency walk that installs an item **after** all of its dependencies are done has work waiting at every call: when the call returns, this routine still has to install this item, and possibly still has more dependencies to walk. Two things survive the call and must be recoverable: - **Where you were** — which item, and how far through its dependency list. - **What you had** — any partial result accumulated so far that the returning value will be combined with. A rewrite that keeps only the items and drops the position is the usual mistake. It visits everything, but it cannot tell a first encounter from a return, so the step that was supposed to run after the children never runs in the right place. ## What goes on the explicit stack The practical recipe is to push a small record rather than a bare item: 1. The item itself. 2. A **phase marker** saying whether this record represents arriving at the item or returning to it — the moral equivalent of the resume point the machinery held for you. 3. If the dependencies are walked one at a time rather than all pushed at once, the index of the next one. 4. The partial result, when the walk is accumulating something rather than acting by side effect. With the marker in place the loop becomes uniform: pop a record; if it says *arriving*, push the same item back marked *returning* and then push its dependencies marked *arriving*; if it says *returning*, do the after-the-children work. The order the dependencies come back in depends on the order you push them, which is one more thing the recursion was deciding for you silently. ## The rewritten loop needs its own argument Once the stack is explicit, the property to preserve is about a data structure you can point at: *the records on the stack, together with the items already finished, account for exactly the work the walk still owes.* That is a strictly better position than the recursive version, where the pending work lives somewhere you cannot inspect. It is also where termination is argued again from scratch: the measure is the number of unvisited items paired with the stack's size, and without a record of what has already been visited a cyclic graph pushes forever. Converting a recursion to a loop never removes the obligation to show it stops. It relocates it. ## Why do the rewrite at all - The depth a chain of calls may reach is capped by the environment, while a stack you build is a structure whose size you choose and can bound yourself. - An explicit stack can be **inspected, checkpointed, paused and resumed** — a long walk can report progress or restart where it left off, which a chain of pending calls cannot. - The work still owed becomes a value, so the property you are preserving can be stated over it rather than over invisible machinery. - Against that: the loop form is longer and the phase marker is easy to get wrong, so the recursive version is usually the clearer one to write first and the one to keep when depth is bounded by the domain. ## What the rewrite must not change The result. A conversion is worth nothing if the iterative walk visits the same items in a different order and the after-the-children step was order-sensitive. The check is to name the order the recursive version produced, name the order the stack produces, and reconcile them — pushing dependencies in reverse is the usual adjustment, because the last one pushed is the first one popped. ## The interview signal A candidate who says "use a stack" has the headline. The one who says **what goes in each record, and why the phase marker is there** has done it, and will not ship the version that visits everything in the right set and the wrong order.

A rewrite pushes bare items with no phase marker. What goes wrong?
The loop cannot tell arriving at an item from returning to it, so the step that was supposed to run after all dependencies has nowhere to hang. You get the right set of items visited in the wrong order — typically the after-the-children work running on the way down instead of on the way back.
Does converting a recursion to a loop remove the need for a termination argument?
No, it relocates it. The measure is now stated over the explicit stack and the record of what has been visited — the unvisited count paired with the stack's size — and without that record a cyclic graph pushes forever in the loop exactly as it recursed forever before.
What happens to an accumulator parameter in the rewrite?
In tail position it becomes an ordinary loop variable, initialised to the base-case value and reassigned where the call passed it along. Outside tail position it cannot: the combination has to wait until the pending work comes back, so the partial value travels on the stack record instead.

saying these in an interview costs you the question

Says every recursion converts to a loop without a stack
Pushes only the items and loses the position within them
Assumes a stack of items alone reproduces an after-the-children visit
Thinks the rewrite changes what the walk computes
Believes converting to a loop removes the termination obligation
Ignores that push order decides the order items come back

Rewriting a recursive dependency walk as a loop, what must the explicit stack hold that recursion kept implicitly?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Tail recursion is already a loop

Non-tail recursion has work waiting

What goes on the explicit stack

The rewritten loop needs its own argument

Why do the rewrite at all

What the rewrite must not change

The interview signal

▾common follow-ups3 questions

▾red flags6 flags

Tail recursion is already a loop

Non-tail recursion has work waiting

What goes on the explicit stack

The rewritten loop needs its own argument

Why do the rewrite at all

What the rewrite must not change

The interview signal

answer

go deeper