Elixir by Example

Recursion

Edit any cell and run it in your browser Download source

Elixir has no for/while loops that mutate a counter. Repetition is recursion: a function that calls itself on a smaller problem, with one clause for the base case.

defmodule MyList do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

IO.inspect(MyList.sum([1, 2, 3, 4]), label: "sum")
sum: 10

Pattern matching on [head | tail] and [] picks the clause. The base case comes first so it's obvious when recursion stops.

defmodule Countdown do
  def run(0), do: IO.puts("liftoff!")

  def run(n) when n > 0 do
    IO.puts(n)
    run(n - 1)
  end
end

Countdown.run(3)
3
2
1
liftoff!

A tail call is one where the recursive call is the very last thing the function does. The BEAM reuses the stack frame, so it runs in constant stack space. The usual trick is an accumulator argument.

defmodule Fact do
  def of(n), do: of(n, 1)

  defp of(0, acc), do: acc
  defp of(n, acc) when n > 0, do: of(n - 1, acc * n)
end

IO.inspect(Fact.of(20), label: "20!")
20!: 2432902008176640000

Integers are arbitrary precision, so this doesn't overflow; it just gets big.

IO.inspect(Fact.of(30), label: "30!")
30!: 265252859812191058636308480000000

Building a list? Prepend while recursing (cheap) and reverse once at the end (one pass).

defmodule Doubler do
  def double(list), do: double(list, [])

  defp double([], acc), do: Enum.reverse(acc)
  defp double([h | t], acc), do: double(t, [h * 2 | acc])
end

IO.inspect(Doubler.double([1, 2, 3]), label: "doubled")
doubled: [2, 4, 6]

In everyday code you rarely write this by hand: Enum and Stream already implement these loops.

IO.inspect(Enum.sum([1, 2, 3, 4]), label: "Enum.sum")
Enum.sum: 10

Pitfall: "always make it tail-recursive" is a myth carried over from older advice. Since OTP R12, body recursion like MyList.sum/1 is often just as fast, and for building lists it can beat the accumulator-plus-Enum.reverse/1 version. Tail recursion matters for infinite loops, like a process's receive loop, which must never grow the stack.

Pitfall: forgetting the base case, or a guard like when n > 0, gives you an infinite loop or a FunctionClauseError on input you didn't expect (Countdown.run(-1)). Guard against bad input at the edge.

Improve this page on GitHub