skip to content

Recursion and Tail Calls

6 roadmaps20 questions

Recursion as the loop of a language with no mutable loop variable: structural cases, accumulators, mutual definitions, trampolines. Interviewers ask because production stack overflows start here.

on this pageshow

explore

questions

20

In a nested comment thread, how does the shape of the data decide a recursive walker's cases?

level: juniorimportance: must knowfreq 72%

answer

  1. start from how the value is built
  2. one case per way, not per example
  3. empty against comment-plus-rest
  4. recurse on the parts it carries
  5. empty case returns the neutral value

basics

~20 s

The data definition lists the ways a value can be built, and each way becomes one case. A reply list is either empty or a comment plus the rest, so the walker has exactly those two cases.

solid answer

~40 s

A nested comment thread has a recursive definition: a reply list is either **empty** or **a comment followed by the rest of the list**, and a comment carries text plus a reply list of its own. Structural recursion gives the walker one case per way the value can be built, and inside each case it recurses on exactly the parts that have the same type - here, the comment's own replies and the rest of the list. Nothing is guessed: the cases are read off the definition, the recursive call sites are forced by which parts are threads, and the only thing left to decide is how to combine the results. That is why the shape of the answer ends up mirroring the shape of the data.

code

pseudocode · 6 lines
pseudocode
function countComments(replies)
    if replies is empty
        return 0
    first = head of replies
    rest  = tail of replies
    return 1 + countComments(first.replies) + countComments(rest)

go deeper

for a junior

Be able to say the two ways a reply list can be built and write one branch for each. Knowing that the empty case exists and returns the neutral value is most of the answer at this level.

for a middle

Explain the derivation as a procedure: enumerate the ways the value is built, one case each, recurse on the parts of the same type, choose a combining step. Show why a "has replies" split is not a case.

for a senior

Show that the skeleton is reusable across counting, collecting and rendering, and that reviewing a walker reduces to checking cases against the definition. Point out where per-comment cost, not control flow, is the real risk.

for a principal

Frame it as a convention worth setting: when types are defined inductively and walkers are derived from them, whole classes of missing-branch bugs stop being possible, and the cost is insisting that data shapes be written down first.

## What a recursive data definition actually says A **recursive (inductive) data definition** lists the finite number of ways a value of the type can be built, and says that nothing else is a value of that type. A thread of replies, written that way, is either: - **empty** - no comments at all; or - **a comment followed by the rest of the list** - one comment, plus a reply list that is itself a reply list. And a **comment** is built one way: some text plus a reply list of its own. Two ways to build a list, one way to build a comment, and every thread the program will ever be handed was assembled out of exactly those pieces. That enumeration is not a stylistic note in a design document. It is the specification the walker is written against. ## Reading the cases off the definition Structural recursion is the discipline of letting that enumeration drive the function: 1. Write down every way a value of the type can be built. 2. Give the function exactly one case per way. 3. In each case, name the parts that way carries. 4. Recurse on exactly the parts that have the same type, and combine those results with whatever the case contributes itself. For a reply list, that mechanical procedure produces this: | Way the value was built | Parts it carries | Recursive positions | What the case must produce | |---|---|---|---| | empty list | none | none | the answer for nothing at all - the neutral value | | comment + rest of list | the comment, the rest of the list | the comment's own replies, and the rest | the comment's own contribution combined with both recursive results | Notice how little judgement is left. The number of cases is fixed by the definition. The recursive call sites are fixed by which parts are again threads. The only genuinely free decision is the **combining operation** - addition for a count, concatenation for a flattened list, maximum for a depth - plus the value the empty case returns, which has to be the neutral element of that operation. ## Why derived cases beat guessed ones - **No missing case.** A case per constructor cannot silently omit the empty list, which is the shape a guessed walker most often forgets. - **No invented case.** "A comment with replies" versus "a comment without replies" looks like a third case, but it is not a way a comment is built - it is a test on a comment's reply list, which the list's own two cases already cover. Splitting on it duplicates logic that the recursion handles for free. - **The recursion cannot wander.** Each recursive call is handed a part the current value already carries, so the walker descends the thread it was given rather than re-deriving some other value to walk. - **The code documents the data.** A reader who has never seen the type can reconstruct its definition from the walker's cases, because they are the same list. - **Review is mechanical.** "Is there a case for every way this is built, and does each recursive call take a part?" is a question a reviewer can answer without running anything. ## What the shape decides, and what it leaves open The shape decides the *skeleton*. It does not decide the *meaning*. Counting comments, collecting author names, finding the deepest nesting and rendering an indented view are four different functions with identical case structure and different combining steps. That is exactly the payoff: once the skeleton is derived, the remaining work is small and local, and a bug is almost always in the combining step rather than in the control flow. Several things the shape explicitly does not hand you: - **Visit order.** Handling a comment before descending into its replies, or after, is a free choice; both are structural. - **Cost.** The walker touches every comment once, so the work is proportional to the number of comments in the thread - but the shape says nothing about how expensive the per-comment step is. - **Stack depth.** The number of nested frames follows the *nesting depth* of the thread, which is a property of the data, not something the discipline bounds. - **What to do with a malformed value.** If a thread can arrive with something the definition does not allow, that is a validation concern at the boundary, not another case in the walker. The habit worth building is the first step, not the last: before writing any branch, say out loud the ways a value of this type can be built. The cases follow from that sentence, and a walker whose cases do not line up with it is a walker that will surprise someone.

  • The empty reply list returns 0 for a count. What decides that value for a different walker?
    The combining operation does. The empty case must return the value that leaves the combination unchanged: `0` when results are added, an empty collection when they are concatenated, the smallest sensible value when they are maximised. Choosing a value that is not neutral for the operation quietly skews every result that passes through an empty list.
  • Is splitting a comment into "has replies" and "has no replies" a third case?
    No. Those are not two ways a comment is built - a comment always carries a reply list, and that list's own two cases already distinguish them. Writing the split by hand duplicates work the recursion does anyway, and the duplicated branch is where the two copies drift apart later.
  • Does the derived skeleton change if the walker must visit replies before the comment itself?
    No. Visit order is a free choice inside each case: the same cases and the same recursive calls, with the combining step arranged differently. Both orders are structural, because both hand each recursive call a part the current value already carries.

Unpacking a set of nested boxes: you do not plan the moves in advance, you open whatever box you are holding and repeat on whatever is inside it, and you stop because a box is eventually empty.

saying these in an interview costs you the question

  • Says the number of cases depends on how deep the thread is
  • Forgets the empty case and handles emptiness by accident
  • Adds a case for "a comment with no replies" as if it were a constructor
  • Thinks structural means one recursive call, so a list of children is impossible
  • Picks an empty-case value that is not neutral for the combining step
open as a page

When you rewrite a recursion into accumulator-passing style, where does the work that followed the recursive call go?

level: middleimportance: must knowfreq 58%

basics

~20 s

It moves across the call, into the argument expression. The combining step is applied to the running result first, and the updated value is passed down, so the recursive call becomes the last thing the function does.

open as a page

A corecursive appointment-date producer has no base case, so what condition makes it well defined instead of a definition that spins?

level: middleimportance: must knowfreq 52%

basics

~20 s

Guardedness: every recursive call must sit behind a step that has already handed back one date, so each turn of the definition delivers output. A path that recurses without delivering anything is the real failure to look for.

open as a page

Both phase functions of a turn loop end in a tail call to each other — why does the usual tail-call-to-loop rewrite not fire?

level: middleimportance: must knowfreq 55%

basics

~20 s

That rewrite is local: it turns a call to the enclosing function into reassigned parameters and a jump to the top of the same body. A mutual call's target is a different body, so no such jump exists.

open as a page

Why does a comment walker that recurses only into each comment's own replies need no depth counter?

level: middleimportance: must knowfreq 58%

basics

~20 s

Every recursive call receives a part of the value it was given, so the argument is strictly smaller each time and the descent runs out of thread. Termination comes from the data, not from a number someone picked.

open as a page

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

level: middleimportance: must knowfreq 50%

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.

open as a page

In an accumulator-passing sum, what does the extra parameter hold when the base case is finally reached?

level: juniorimportance: should knowfreq 52%

basics

~20 s

It holds the finished total of every element consumed so far, which at the base case is every element in the input. The base case therefore returns that parameter unchanged instead of returning a constant.

open as a page

How does a recursion that produces recurring appointment dates from a start date differ from one that consumes a list?

level: juniorimportance: should knowfreq 35%

basics

~20 s

A consuming recursion takes an existing value apart and shrinks toward a base case; a producing one grows a result outward from a seed. A decreasing measure is replaced by handing back one piece per step.

open as a page

A turn-based game's two phase functions each end by calling the other; what must decrease for the pair to terminate?

level: juniorimportance: should knowfreq 46%

basics

~20 s

Some measure defined over both functions' arguments must strictly decrease every time control crosses between them, drawn from an order with no infinite descent. Neither function shrinks anything on its own, so the argument covers the pair together.

open as a page

When rewriting a recursive product into accumulator-passing style, how do you choose the accumulator's starting value?

level: middleimportance: should knowfreq 45%

basics

~20 s

Pick the result the function should give for empty input, which for a product is one. Where the combining step has such a neutral value the seed is that value; where it has none, seed from the first element and require non-empty input.

open as a page

What does merging two mutually recursive phase functions into a single tag-dispatched function actually buy you?

level: middleimportance: should knowfreq 42%

basics

~20 s

Every crossing becomes a self-call, so the cycle sits inside one body that a plain loop can replace. You pay for it with a widened parameter list and a branch on the tag chosen at run time.

open as a page

In a comment thread walker, why is recursing on the thread minus one comment not structural?

level: middleimportance: should knowfreq 46%

basics

~20 s

The thread minus one comment is a new value built from the old one, not a part the old one carries. It may well shrink, but only on a size measure someone has to check by hand - the shape no longer guarantees anything.

open as a page

Your accumulator-passing walk over an account statement returns the per-entry balances in reverse — what in the rewrite causes that?

level: seniorimportance: should knowfreq 38%

basics

~20 s

The accumulator is extended at its cheap end before each recursive call, so the earliest entry is added first and ends up deepest, and the base case returns that collection untouched. The usual fix is one final reversing pass.

open as a page

Your appointment-date producer keeps part of its repeat rule outside the seed — what does that cost you?

level: seniorimportance: should knowfreq 38%

basics

~20 s

The step stops being a function of the seed alone, so the seed no longer names a position in the series: you cannot resume or replay from it, two readers can disagree, and caching results by seed becomes unsound.

open as a page

A structurally recursive comment walker exhausts the stack on one very deep thread - what did the structural argument never promise?

level: seniorimportance: should knowfreq 40%

basics

~20 s

It promised the walk ends, not that it stays shallow. Recursing on parts bounds the number of calls by the pieces in the data; the frames alive at once follow the thread's nesting depth, which the data chooses, not the walker.

open as a page

You trampoline a recursion whose work happens after the recursive call returns; why does it still need memory proportional to depth?

level: seniorimportance: should knowfreq 36%

basics

~20 s

The work pending after the call cannot vanish. To let each step return, that leftover is packaged as a continuation value, so for a chain of n steps you hold n continuations instead of n unfinished invocations.

open as a page

A workflow engine will require every handler to return its next step as a value rather than call it — what does publishing that step type commit extending teams to?

level: principalimportance: should knowfreq 24%

basics

~20 s

It makes the returning style viral across the whole extension surface: handlers may no longer use ordinary calls to continue a chain, the step type becomes public API you cannot change quietly, and failures show the driver loop instead of the logical path.

open as a page

Folding collapses a list of appointment dates to one value; what does the mirror-image unfolding operation take and produce?

level: seniorimportance: nice to knowfreq 28%

basics

~20 s

Unfolding takes a seed and a step and produces a structure. The step turns one seed into an element plus the next seed, or reports stop. Folding is a structure in and a value out; unfolding is that arrow reversed.

open as a page

Walking a structure whose levels alternate between container and entry, why write two mutually recursive functions instead of one?

level: seniorimportance: nice to knowfreq 32%

basics

~20 s

Because the alternation is a fact about the data, and two functions put it in the call graph: each receives exactly one kind of level, carries its own termination condition, and never has to re-establish where in the structure it is.

open as a page

A trampolined step chain runs measurably slower than the direct recursion it replaced; what is each step now paying for?

level: seniorimportance: nice to knowfreq 28%

basics

~20 s

Every step now allocates a description of the next call and is reached through an indirect invocation the compiler cannot see through, plus a loop turn and a tag check. The safety is bought with allocation churn and lost inlining.

open as a page