Elixir Recursion

Recursion is a way for a function to call itself with a smaller input until a stopping clause matches. The stopping clause gives the answer for the smallest input.

Factorial stops at zero

The first clause answers 1 for 0, and the guarded clause multiplies n by the factorial of n - 1. Each call moves one step closer to 0.

defmodule Fact do
  def of(0), do: 1
  def of(n) when n > 0, do: n * of(n - 1)
end

IO.puts(Fact.of(0))
IO.puts(Fact.of(5))

A hand written sum walks a list to the empty list

The stopping clause gives 0 for an empty list. The other clause adds the head to the sum of the tail.

defmodule Sum do
  def total([]), do: 0
  def total([head | tail]), do: head + total(tail)
end

IO.puts(Sum.total([]))
IO.puts(Sum.total([10, 20, 30]))

Counting a list adds one for each element

The counting clause ignores the head value and adds 1 for it. The count of the tail supplies the rest of the total.

defmodule Counter do
  def count([]), do: 0
  def count([_head | tail]), do: 1 + count(tail)
end

IO.puts(Counter.count(["a", "b", "c", "d"]))

Example

defmodule Math do
  def factorial(0), do: 1
  def factorial(n) when n > 0, do: n * factorial(n - 1)
end

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

  def count([]), do: 0
  def count([_head | tail]), do: 1 + count(tail)
end

IO.puts(Math.factorial(6))
IO.puts(ListWork.sum([5, 15, 25]))
IO.puts(ListWork.count([5, 15, 25]))

Key points

Recursion: a function calling itself as part of its own result.
Stopping clause: the clause that matches the smallest input and returns a fixed answer.
Smaller input: each new call works on less data than the call before it.
Guard: a when test on a clause can keep the working clause away from the stopping case.
List split: the [head | tail] pattern separates the first element from the rest of a list.
Empty list: the pattern [] is the stopping case for a function that walks a list.

In this example, factorial counts down to its stopping clause at 0 and returns 720 for 6. The sum and count functions walk the same list, one adding each head and the other adding 1 for each element.

Note

in Elixir, recursion with clauses replaces the changing loop counter used in many other languages.

Try it Yourself

Edit the code, then press Run.

Running is simulated

defmodule Math do
  def factorial(0), do: 1
  def factorial(n) when n > 0, do: n * factorial(n - 1)
end

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

  def count([]), do: 0
  def count([_head | tail]), do: 1 + count(tail)
end

IO.puts(Math.factorial(6))
IO.puts(ListWork.sum([5, 15, 25]))
IO.puts(ListWork.count([5, 15, 25]))

Exercise

In def total([]), do: 0 and def total([head | tail]), do: head + total(tail), what does total([7]) return?

7 0 14 1