skip to content

Accumulator Passing Style

6 roadmaps4 questions

Carrying the answer forward in a parameter rather than assembling it as the calls unwind, which is what makes a recursion tail-recursive. Interviewers ask for the rewrite and for what the order does.

on this pageshow

explore

questions

4

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

level: middleimportance: must knowfreq 58%

answer

  1. something moves across the recursive call
  2. post-call work becomes pre-call work
  3. the base-case constant relocates outward
  4. compute the new running value first
  5. keep the original signature as a wrapper

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.

solid answer

~50 s

The rewrite is a transposition, not a rewording. In the original, the function calls itself and then does something to the result — adds one, adds an element, prepends a value. In accumulator-passing style that same combining step is applied **before** the call, to the accumulator, and the result is passed down as an argument. Three edits do it: add a parameter holding the answer so far; make the base case return that parameter instead of its constant; move the post-call combining into the argument expression. The constant the base case used to return becomes the seed of the first call, which is why the rewrite usually keeps a one-parameter wrapper that supplies the seed and hides the extra parameter from callers. Because nothing is left pending, the recursive call now sits in tail position.

code

pseudocode · 4 lines
pseudocode
function length(items)
    if items is empty
        return 0
    return 1 + length(rest(items))

go deeper

for a junior

Learn the three edits as a recipe: add the parameter, return it from the base case, move the post-call work into the argument. Practise it on a sum and on a length until the shape is automatic.

for a middle

This is your tier. Perform the rewrite live on a whiteboard and narrate why the recursive call ends up with nothing after it, then say where the old base-case constant went.

for a senior

Demonstrate the review checks: a stray constant in the base case, a seed that does not match it, an accumulator passed along untouched. Those three defects survive tests that only use symmetric inputs.

for a principal

The trade-off you weigh is readability against uniformity — the rewritten function no longer reads like the definition of the problem, so a team that adopts it by default should pair it with the wrapper and a stated invariant.

## The transformation in one sentence Everything the function used to do **after** its recursive call is moved **before** it, applied to an extra parameter that travels forward. That is the entire content of accumulator-passing style; the rest is bookkeeping. ## The three edits 1. **Add a parameter** — the accumulator — whose meaning you can state: the answer for the part of the input already consumed. 2. **Rewrite the base case** to return that parameter instead of the constant it used to return. 3. **Move the combining step** out of the return expression and into the argument expression of the recursive call, applying it to the accumulator. The constant from step 2 is not lost. It becomes the **seed** given to the first call, which is the single most common thing people forget, because it is the only part of the rewrite that happens outside the function. ## Worked on a length function The unwinding version says "the length of a non-empty list is one more than the length of its tail": the `+ 1` runs after the call returns. The accumulator version says "walk the list, and each time you step past an element, the count you carry goes up by one": the `+ 1` runs before the call is made, inside the argument. Both visit exactly n elements for an input of n elements; the rewrite changes *when* each addition happens, not *how many* there are. | | before the rewrite | after the rewrite | |---|---|---| | recursive call | `length(rest(items))` | `lengthFrom(rest(items), counted + 1)` | | the `+ 1` | applied to the returned value | applied to the argument | | base case | returns `0` | returns `counted` | | where `0` lives | the base case | the first call, as the seed | | after the call returns | one addition is still pending | nothing is pending | ## Why the wrapper The two-parameter helper is an implementation detail. A caller asked to supply a seed can supply the wrong one, and the extra parameter means nothing in terms of the problem being solved. So the rewrite normally ships as a pair: - a **public function** with the original signature, which calls the helper with the correct seed; - a **helper** carrying the accumulator, usually local to the public one. A default value for the extra parameter does the same job where a language offers one, but the wrapper is the form that works everywhere and keeps the seed out of the caller's hands. ## What the rewrite does and does not change It does change: - **when** each combining step runs — on the way down instead of on the way out; - **the order** the steps are applied in: earliest-consumed element first, where the unwinding version effectively combined the last-consumed element first; - **what the base case returns**; - whether the recursive call is in **tail position**: it now is, because its result is returned directly with nothing applied to it. It does not change: - how many elements are visited, or the asymptotic cost of visiting them; - the result, *provided* the combining step is insensitive to the order it is applied in. For addition of exact numbers it is; for a step that concatenates, subtracts, or builds a sequence, it is not — and that is where a careless rewrite silently changes the answer. ## Checking a rewrite you did not write In review, four checks catch nearly everything: 1. Does the base case return the accumulator, or has a stray constant survived? 2. Is the seed the same value the old base case returned? 3. Is the combining step applied to the accumulator, rather than to the element only — that is, is the updated value actually threaded down? 4. Run the pair on one small input where the combining step is not symmetric, and compare. The third check catches the most embarrassing failure mode: a function that has grown an accumulator parameter, passes it along untouched, and still does its real work after the call. It looks like the rewrite and is not one. ## Where candidates slip - Renaming a parameter and calling it an accumulator while the combining step stays after the call. - Forgetting the seed and starting from whatever value is convenient. - Returning the old constant from the base case, so the function reports the empty-input answer for every input. - Exposing the two-parameter helper as the public entry point, which lets callers seed it wrongly.

  • How would you check that a rewrite preserves the original function's result?
    Confirm the seed equals the constant the old base case returned, that the base case now returns the accumulator, and that the updated value is actually threaded into the call. Then run both versions on an input where the combining step is not symmetric — subtraction or sequence-building — because those are the steps whose result depends on the order the rewrite changed.
  • Why keep a wrapper rather than exposing the two-parameter helper directly?
    The accumulator is an implementation detail with no meaning in the problem, and a caller who supplies the wrong seed gets a plausible wrong answer rather than an error. The wrapper fixes the seed in one place and keeps the public signature describing the problem. A default parameter value does the same job where the language provides one.
  • Does the rewrite change how many times the combining step runs?
    No. For an input of n elements both versions apply the step n times and visit n elements; the rewrite only changes whether each application happens before the next call or after that call returns. What can change is the result, when the step is sensitive to the order it is applied in.

It is the difference between a relay team carrying one baton forward and a team where every runner waits at the line to be handed the next leg's time before they can report their own. Accumulator-passing style moves the baton forward, so nothing is left to settle on the way back.

saying these in an interview costs you the question

  • Leaves the combining step after the call and renames a parameter
  • Returns the base-case constant instead of the accumulator
  • Forgets the seed and starts from a convenient value
  • Adds the parameter but never threads the updated value down
  • Thinks the rewrite changes how many elements are visited
  • Exposes the helper and lets callers choose the seed
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

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

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