September 13, 2020

Recursion in Elixir

As Elixir is a purely functional language, it doesn’t have loops. Instead, it uses a wide variety of recursive functions to achieve the same or better results.

Below is an example of a list and calculating it's length. This shows how recursive functions can be used to work like a loop.

Tail Call Optimization

A traditional function stack looks like this, with each member of the list becoming another function on the stack:

┌────────────────────────┐
│ length([1, 2, 3, 4], 0)│ <── Each member of the list
├────────────────────────┤ becomes a function on
│ length([2, 3, 4], 1)   │ the stack
├────────────────────────┤
│ length([3, 4], 2)      │
├────────────────────────┤
│ length([4], 3)         │
├────────────────────────┤
│ length([], 4)          │
└────────────────────────┘

A tail call optimized function stack, like that used in Elixir, looks like this:

┌────────────────────────┐       ┌────────────────────────┐
│ length([1, 2, 3, 4], 0)│ <──── │ length([2, 3, 4], 1)   │
└────────────────────────┘       ├────────────────────────┤
│ length([3, 4], 2)      │
├────────────────────────┤
│ length([4], 3)         │
├────────────────────────┤
│ length([], 4)          │
└────────────────────────┘

Function calls on the stack are replaced, so there is only one function on the stack at a time.

Requirements for Tail Call Optimization

In order to be tail call optimized, a function must call itself as the last operation. This is not a proper tail call:

def join([h|t]) do
  h <> " " <> join(t)
end

But this is:

def join([h|t], string) do
  string = string <> " " <> h
  join(t, string)
end

So, now let's look at some examples of a list (MyList) and calling different recursive functions that allow us to work with the list's data.

MyList.length/1

defmodule MyList do
  def length(list) do
    length(list, 0)
  end

  defp length([], count) do
    count
  end

  defp length([_|t], count) do
    length(t, count + 1)
  end
end

MyList.each/2

defmodule MyList do
  def each([], _fun) do
    :ok
  end

  def each([h|t], fun) do
    fun.(h)
    each(t, fun)
  end
end

Usage:

MyList.each [1, 2, 3], fn(num) ->
  IO.puts(num)
end

# 1
# 2
# 3
# => :ok

MyList.map/2

defmodule MyList do
  def map(list, fun) do
    do_map(list, fun, [])
  end

  defp do_map([], _fun, acc) do
    :lists.reverse(acc)
  end

  defp do_map([h|t], fun, acc) do
    result = fun.(h)
    acc = [result | acc]
    do_map(t, fun, acc)
  end
end

The final do_map clause could also be shortened like this:

defp do_map([h|t], fun, acc) do
  do_map(t, fun, [fun.(h) | acc])
end

Usage:

list = [
  {"Nolan", 30},
  {"Alex", 32}
]

MyList.map list, fn({name, _age}) ->
  name
end

# => ["Nolan", "Alex"]

tags: recursion programming functions elixir code