skip to content

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

level: middleimportance: should knowfreq 45%

answer

  1. ask what empty input should return
  2. the value the step leaves unchanged
  3. sum and product need different ones
  4. some steps have no neutral value
  5. then start from the first element

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.

solid answer

~40 s

Two questions give the same answer and either one is a valid check. First: what should the function return for empty input? Second: what value does the combining step leave unchanged? For a product that is `1`, for a sum `0`, for building a sequence the empty sequence. Seeding a product with `0` is the classic error — every product then comes out zero, because the seed is combined in like any other factor. Not every combining step has such a neutral value, though: a maximum over numbers that may be negative has none you can write down, so the rewrite seeds the accumulator with the **first** element and recurses on the rest, which makes non-empty input a precondition the wrapper has to enforce.

code

pseudocode · 11 lines
pseudocode
function maxFrom(values, best)
    if values is empty
        return best
    if first(values) > best
        return maxFrom(rest(values), first(values))
    return maxFrom(rest(values), best)

function maxOf(values)
    if values is empty
        error "no maximum for empty input"
    return maxFrom(rest(values), first(values))

go deeper

for a junior

Memorise the two everyday seeds and why they differ: a sum starts at zero, a product starts at one. If you can say what the function should return for empty input, you have the seed.

for a middle

Explain the seed as the neutral value of the combining step, and be ready for the case where none exists — seed from the first element and state the non-empty precondition out loud.

for a senior

The judgment to show is that a wrong seed is a silent defect that passes typical tests. Say how you would choose the input that exposes it: all-negative data for a maximum, empty input for everything.

for a principal

The design call is whether to widen the accumulator's type so a neutral value exists, buying a total function at the cost of an extra case in every combining step, or to keep the precondition at the boundary.

## The seed is not arbitrary The accumulator starts at some value, and that value is part of the answer. It is combined with the first element exactly as every later element is, so a wrong seed produces a wrong result quietly — no error, no crash, just a number that is off. ## Two checks that agree - **The empty-input check.** Ask what the function should return when given nothing at all. A sum of nothing is `0`; a product of nothing is `1`; a concatenation of nothing is the empty sequence; a count of nothing is `0`. That value is the seed. - **The neutral-value check.** Ask which value the combining step leaves its other operand unchanged by. Adding `0` changes nothing; multiplying by `1` changes nothing; prepending to the empty sequence yields a one-element sequence. That value is the seed. They agree because they are the same fact seen from two sides, and having both is useful: the first is easier to reason about for a sequence-building accumulator, the second for an arithmetic one. There is also a third check, specific to a rewrite rather than to a fresh function: **the seed is the constant the original base case returned.** If the unwinding version ended in `return 0`, the accumulator version starts at `0`. | combining step | neutral value | seed | what a wrong seed does | |---|---|---|---| | addition | `0` | `0` | a non-zero seed shifts every total by it | | multiplication | `1` | `1` | a seed of `0` makes every product zero | | counting | `0` | `0` | a seed of `1` reports one element too many | | prepending to a sequence | empty sequence | empty sequence | a non-empty seed leaves stray elements in the result | | maximum over a bounded range | the range's minimum | that minimum | a seed above some elements hides them | | maximum over an unbounded range | none available | the first element | a seed of `0` reports `0` for all-negative input | ## When there is no neutral value This is the case worth being able to discuss, because it is where a rule applied blindly breaks. A maximum over ordinary numbers has no neutral value you can write as a literal — the value that leaves every comparison unchanged would have to be smaller than every possible input. Where the value range has a defined minimum you can use it; where it does not, you have two honest options: 1. **Seed from the first element** and recurse on the rest. The function then only makes sense for non-empty input, and the wrapper enforces that — by rejecting empty input, or by returning a value that models absence rather than a number. 2. **Make the accumulator a richer type** that can represent "nothing seen yet", so the combining step has something neutral to start from. This costs an extra case in the step but restores the simple rule. The second option is what the first one is hiding: you are re-introducing a neutral value by widening the accumulator's type until one exists. ## More than one accumulator Nothing limits the rewrite to a single extra parameter. A mean over a sequence needs two running values, a total and a count, each with its own seed of `0`; the base case returns a combination of the two rather than one of them. The rule for choosing seeds is unchanged, applied once per accumulator. ## The failure this prevents A wrong seed is a silent defect: the shape is right, the traversal is right, the tests on typical input may even pass. Seeding a maximum with `0` works for every test whose data happens to contain a positive number, and reports `0` the first time a real all-negative batch arrives. Naming the empty-input answer explicitly, before writing the seed, is the habit that catches it. ## Where candidates slip - Reusing `0` for every accumulator because it is the seed they have written most often. - Asserting that the seed is arbitrary because "the first step overwrites it" — the first step *combines* with it. - Assuming every combining step has a neutral value, then producing a maximum that cannot go below zero. - Being unable to say what the function should return for empty input, which is the same as being unable to choose the seed.

  • What do you do when the combining step has no neutral value to seed with?
    Seed the accumulator with the first element and recurse on the rest, which makes non-empty input a precondition the wrapper enforces. The alternative is to widen the accumulator so it can represent "nothing seen yet", which gives the step a neutral starting value again at the cost of an extra case inside it.
  • When would a rewrite carry more than one accumulator?
    Whenever the answer depends on several running values at once — a mean needs a running total and a running count, each seeded independently at zero, and the base case returns the two combined. The rule for choosing each seed is unchanged; it is applied once per accumulator.

saying these in an interview costs you the question

  • Seeds a product accumulator with zero
  • Assumes the seed is arbitrary because the first step overwrites it
  • Seeds a maximum with zero over possibly negative values
  • Cannot say what the function should return for empty input
  • Believes every combining step has a neutral value