Recursion over lists

There is no loop keyword for lists — you walk one by recursion. The pattern is always the same: match [head | tail], do something with the head, call yourself on the tail, and stop at the empty list. Sum, map, and length are all this one shape with a different body.

When the recursive call is the very last thing a clause does, it is tail-recursive and runs in constant stack space — a loop in disguise. Select a function to see its clauses and how the list reduces.

Three functions, one shape Direct vs tail-recursive

Three functions, one shape

Each function has a recursive clause for [h | t] and a base clause for []. The recursive clause reduces the problem by one element; the base clause stops it. Select one and read its clauses and result over [12, 8, 30].

The function · select one

The recursive clause shrinks the list by its head; the base clause says what an empty list is worth. Get those two right and the function is correct — there is no third case to forget.

Direct vs tail-recursive

Direct recursion leaves work pending on the way down — h + sum(t) can only finish once sum(t) returns — so the call stack grows with the list. A tail-recursive version carries an accumulator and makes the recursive call its last action, which the BEAM runs as a loop in constant space.

# direct recursion — clear, but the stack grows with the list
def sum([h | t]), do: h + sum(t)
def sum([]), do: 0

# tail-recursive — the recursive call is the last step, so it is a loop
def tsum(list), do: tsum(list, 0)
defp tsum([h | t], acc), do: tsum(t, acc + h)
defp tsum([], acc), do: acc

The idea

Do something with the head, then solve the same problem on the tail — until there is nothing left.

In Elixir

Match [h | t], recurse on t, stop at []; an accumulator turns it into a loop.

Next: complexity & big-O on the BEAM — counting how many cells each walk touches.

References

Primary sources for this lesson, and where it connects in the course.

Sources

List — Elixir documentation — cons-cell lists.
Erlang — Efficiency Guide — complexity on the BEAM.
Okasaki, C. (1996). Purely Functional Data Structures — the foundational text on recursive list and tree structures.