The list leaves a trail of breadcrumbs

A list has left one item on the doorstep and asked us to look after the remainder.

This is enough information to write a surprising number of useful functions.

Name the two shapes

A list is either empty or has a first element and a remaining list:

sum(values: List(Int)) -> Int {
  match values {
    [] -> 0
    [head, ..tail] -> head + sum(tail)
  }
}

main() {
  assert sum([]) == 0
  assert sum([2, 3, 5]) == 10
}

The empty case supplies an answer without making another call. The other case removes one element before delegating the remainder.

The pattern match explains both the stopping condition and why the recursive input is smaller. Merely calling the same function again would explain neither.

Watch the work waiting behind us

In that first version, addition still has to happen after the recursive call returns. Each caller is waiting to add its own head to the answer.

An accumulator moves the partial answer into the arguments:

sum_loop(values: List(Int), total: Int) -> Int {
  match values {
    [] -> total
    [head, ..tail] -> sum_loop(tail, total + head)
  }
}

main() {
  assert sum_loop([2, 3, 5], 0) == 10
}

Now the recursive call is the final operation in its branch. The BEAM can execute tail calls without keeping a growing chain of callers waiting for work afterwards.

Choose the identity deliberately

The initial 0 is not arbitrary decoration. It is the identity for addition: starting with it does not change the sum. A product would need a different identity, and a search might return an Option instead of an integer.

That is a useful way to reason about the stopping case. What answer represents having no more input to process?

Recursion is easier to trust when the explanation is local: these are the possible shapes, this branch stops, and this branch makes measurable progress.

The breadcrumbs lead somewhere because we leave one fewer of them on each visit.

— Peregrine Finch