Recursion instead of loops

There is no loop to write

Elixir has no counter to bump and no while. The repeat you know from other languages is written as a function that calls itself on a smaller piece of the data, and the smallest piece — the empty list — is the end of the story. This is not a workaround for a missing feature; it is what the data asks for, because a list in Elixir really is a chain of head and tail. The empty list is the one shape with no head, and it is the only place a walk can stop without doing more work.

You have seen a comprehension shape with for, and it exists here — but its job is to build a new collection from an old one, not to repeat a step until something changes. When the question is whether to keep going, recursion is the tool.

One clause per shape of the data

Every recursive function on a list has two heads. The empty list is the answer for nothing left, and it stops the walk: def total([]), do: 0. The list with at least one item takes the head, works on it, and asks the same question of the tail: def total([head | tail]), do: head + total(tail). Two lines, and any length of list is covered. The pair clause does not need to know the length; it takes one item and trusts the recursive call with the rest, which is the whole reason two clauses are enough.

Once that shape is clear, whole families of functions fall out of it: count by adding one instead of the head, double everything by building a new list from doubled heads, find the biggest by comparing the head with the best of the tail. The clause for the empty list is where you decide what an empty collection means, and the clause for the pair is where one step is described.

Accumulators, and why the language is happy to do this

An accumulator is a second argument that carries the answer so far. Walking a list forwards and putting each item on the front of a list builds it backwards — which is cheap, because the front is where a list grows — so the finished result is turned around once at the end with Enum.reverse. That reversal is idiomatic, not a mistake to apologise for.

Recursion is cheap here for two reasons. When the very last thing a function does is call itself, there is nothing left to do afterwards, so the runtime can reuse the same spot instead of stacking up one step per item — a tail call. And because a value is never changed in place, each step builds one new link and shares everything else with the older list, so a walk over a long list does not copy it. That sharing is what makes the recursion cheap in memory as well as in stack: each step adds one link and leaves the rest of the chain alone.

Four walks over a list

defmodule Words do
  # A recursive function has one clause per shape of list.
  def total([]), do: ""
  def total([only]), do: only
  def total([head | tail]), do: head <> " " <> total(tail)

  def longest([only]), do: only

  def longest([head | tail]) do
    rest = longest(tail)

    if String.length(head) >= String.length(rest) do
      head
    else
      rest
    end
  end
end

three = ["one", "two", "three"]
pair = ["one", "two"]

IO.puts(Words.total(three))
IO.puts(Words.longest(["one", "seven", "four"]))
IO.inspect(Enum.map(pair, fn w -> String.length(w) end))

The shape of a call stack

When a function calls itself, each call gets its own frame holding its arguments and the place to return to. A non-tail call has to keep that frame because there is still work to do after the inner call returns — adding the head, for instance. A tail call has nothing left to do, so the runtime can reuse the frame instead of stacking a new one.

That is why an accumulator matters: it moves the work to before the call, so the recursive call is the last thing. The answer travels forward in the argument rather than being rebuilt on the way back. The function is still recursive, but it uses one frame for the whole walk.

Try these next

• Write sum/1 and count/1 for a list, then rewrite count with an accumulator.
• Write a recursive max/1 and check it against Enum.max.
• Trace power(2, 4) by hand and then add a tail-recursive version.