skip to content

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

level: juniorimportance: should knowfreq 52%

answer

  1. look at the parameter, not the return
  2. a running answer carried downward
  3. true at every call, not one
  4. it describes the part already consumed
  5. the base case has nothing left to compute

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.

solid answer

~40 s

The extra parameter is a running answer, not a leftover. The invariant is that at every call it already holds the combined result of the part of the input that has been consumed, while the other parameter holds the part still to go. When the input parameter becomes empty, nothing is left to consume, so the running answer is the answer for the whole input — and the base case returns it directly. That is the structural difference from the unwinding version, whose base case returns a constant such as `0` and then rebuilds the answer as each call returns. Here every combining step has already happened on the way down, and each return simply hands the same value back to the caller.

code

pseudocode · 7 lines
pseudocode
function sumFrom(entries, runningTotal)
    if entries is empty
        return runningTotal
    return sumFrom(rest(entries), runningTotal + first(entries))

function sum(entries)
    return sumFrom(entries, 0)

go deeper

for a junior

Recall the shape: an extra parameter carries the running answer, and the base case returns that parameter instead of a constant. Being able to trace three or four calls by hand is enough at this stage.

for a middle

Explain the invariant out loud — the accumulator is the answer for what has been consumed — and show where the old base-case constant went. That explanation is what an interviewer is listening for.

for a senior

Show that you check the invariant on a non-empty and an empty input before trusting a rewrite someone else made, and that you can spot a base case still returning the constant in review.

for a principal

The angle you own is when to standardise on this shape at all: it buys a uniform review rule at the cost of a parameter that means nothing to a caller, which is why teams pair it with a wrapper.

## What the extra parameter is A recursion written in **accumulator-passing style** takes one parameter more than the problem needs. The first parameter shrinks in the usual way — the remaining part of the input. The extra one, the **accumulator**, grows: it carries the answer computed so far, forward, into the next call. This is the whole trick. In the version most people write first, the answer is assembled *after* the recursive call returns, on the way back out of the call chain. In accumulator-passing style the answer is assembled *before* the recursive call is made, and handed down as an argument. ## The invariant, stated once The accumulator is only meaningful if you can say what it means at **every** call, not just at the first or the last. For a sum over a list of numbers, the invariant is three short claims that hold together at the moment of any call: 1. the input parameter holds the elements not yet consumed; 2. the accumulator holds the total of the elements already consumed; 3. the total of the whole original input equals the accumulator plus the total of what remains. Being able to state that third line is what separates a candidate who has memorised the shape from one who understands it. It is an ordinary loop invariant, written for a recursion. ## A trace Summing `[4, 7, 2]` with a seed of `0`: | call | remaining input | accumulator | meaning of the accumulator | |---|---|---|---| | 1 | `[4, 7, 2]` | `0` | nothing consumed yet | | 2 | `[7, 2]` | `4` | total of `[4]` | | 3 | `[2]` | `11` | total of `[4, 7]` | | 4 | `[]` | `13` | total of `[4, 7, 2]` — the answer | At call 4 the remaining input is empty, so by the invariant the accumulator is the answer for the entire original input. It is `13` because every addition has already been performed, one per call, on the way down. ## What the base case returns The base case of the unwinding version returns a **constant**: the answer for empty input. The base case of the accumulator version returns the **accumulator**. This is not a stylistic choice — returning a constant here would throw away everything the recursion has computed and report the answer for empty input no matter what was passed in. The constant has not disappeared, though. It has moved outward, to the caller, where it becomes the **seed** of the very first call. A one-parameter wrapper usually supplies it, so callers never see the extra parameter at all. ## Reading the two shapes side by side | | unwinding form | accumulator-passing form | |---|---|---| | where the combining happens | after each recursive call returns | before each recursive call is made | | what the base case returns | a constant | the accumulator, unchanged | | where the constant lives | in the base case | in the caller, as the seed | | what a return does | combines a value into the pending work | passes the same value along untouched | | order elements are combined in | last consumed first | first consumed first | ## Why the return trip is empty Once the base case produces the accumulator, every frame above it has nothing left to do with that value — no addition, no wrapping, no bookkeeping. Each return simply hands the identical value back to its caller, unchanged, until it reaches the original caller. That is precisely why the recursive call sits in **tail position**: it is the last thing the function does, and its result *is* the function's result. Be careful about what that does and does not promise. The shape guarantees that no work is pending on the way out. Whether a particular runtime turns that into a constant-space loop is a property of the runtime, not of the shape you wrote. ## Where candidates slip - Describing the accumulator as "the answer for what is left" — it is the answer for what is **gone**. - Leaving `return 0` in the base case after adding the parameter, so the function returns the seed's meaning rather than the computed answer. - Believing the additions still happen as the calls unwind, which is the mental model of the version being replaced. - Treating the extra parameter as an optimisation switch rather than as a value with a stated meaning. The usable summary is one sentence: the accumulator is the answer so far, and the base case is where "so far" has become "in total".

  • What invariant would you state to argue that an accumulator-passing sum is correct?
    At every call, the accumulator holds the total of the elements already consumed and the input parameter holds those not yet consumed, so the accumulator plus the total of the remainder always equals the total of the original input. When the remainder is empty its total is zero, which makes the accumulator the answer.
  • Does an accumulator-passing sum compute anything as the calls return?
    No combining happens on the way out. Every addition was performed before the next call was made, so each return hands the identical value back to its caller until it reaches the original one. That is why the value the base case produces is already the final answer rather than a partial one.

saying these in an interview costs you the question

  • Says the accumulator holds the answer for the remaining elements
  • Leaves the base case returning zero and discards the parameter
  • Believes the additions happen as the calls unwind
  • Cannot say what the parameter means at an arbitrary call
  • Treats the extra parameter as a flag rather than a value