Iteration, recursion, and tail-call optimization in Elixir
Tags: elixir, beginners, programming
Published: 2019-03-19 13:52:37

---
title: Iteration, recursion, and tail-call optimization in Elixir
description: "It’s time for another Elixir Alchemy! This week, we’ll dive into recursion in Elixir to find the fastest looping method. (Spoiler: it depends). 🎢"
tags: elixir, beginners, programming
cover_image: https://blog.appsignal.com/images/blog/2019-03/turbo.jpg
published: true
canonical_url: https://blog.appsignal.com/2019/03/19/elixir-alchemy-recursion.html
---

Elixir uses recursion for looping over data structures like lists. Although most of it's hidden away through higher-level abstractions on the `Enum` class, in some cases writing a recursive function yourself can be more performant. In this episode of Elixir Alchemy, we’ll try to find some of these cases.

Along the way, we’ll learn about body-recursive and tail-recursive functions. Although the latter is often touted as being faster, we’ll also look at cases where that’s not necessarily true. Let’s dive right in!

## Enumeration

Elixir provides functions on the `Enum` module to enumerate over collections.

``` elixir
def sum_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.reduce(0, fn n, sum -> n + sum end)
end
```

This example takes a list and returns the sum of all numbers in that list. Because there might be non-numeric items in the input list, it uses `Enum.filter/2` to select only the items that `is_number/1` returns true on. After that, the remaining values are added together through `Enum.reduce/3`.

``` elixir
sum_numbers1([1, 2, "three", 4, %{}]) # => 7
```

While this solution works, it iterates over the whole list twice to get to the result. To make this more performant, we might instead choose to write a recursive function that can do this in one go.

## Recursion

A recursive function can do both tasks (removing the non-numeric items and adding the rest together) in one run. It will call itself for every item in the list, and use pattern matching to decide what to do with each item.

``` elixir
# 1
def sum_numbers2([head | tail]) when is_number(head) do
  sum_numbers2(tail) + head
end

# 2
def sum_numbers2([_head | tail]) do
  sum_numbers2(tail)
end

# 3
def sum_numbers2([]) do
  0
end
```

Instead of using the functions provided by the `Enum` module, this solution calls itself until the list is empty. It does so using three function heads:

1. When the first item in the list (the *head*) is a number, we'll call `sum_numbers2/1` with the rest of list (anything but the head, called the *tail*). This call returns a number we'll add our current head to.
2. When the head is *not* a number, we'll drop it by calling the `sum_numbers2/1` function with just the tail.
3. When the list is empty, we'll return 0.

``` elixir
sum_numbers2([1, 2, "three", 4, %{}]) # => 7
```

When calling this function with `[1, 2, "three", 4, %{}]`, the `sum_numbers2/1` function is called repeatedly in the following order to get to the result:

- `sum_numbers2([1, 2, "three", 4, %{}])`
- `sum_numbers2([2, "three", 4, %{}]) + 1`
- `sum_numbers2(["three", 4, %{}]) + 1 + 2`
- `sum_numbers2([4, %{}]) + 1 + 2`
- `sum_numbers2([%{}]) + 1 + 2 + 4`
- `sum_numbers2([]) + 1 + 2 + 4`
- `0 + 1 + 2 + 4`

This list shows the how the function is simplified until we get to a result, which shows the function being called six times. Once for each item, plus once more for the empty list at the end.

Because the function calls itself for each iteration, each item in the list causes a [stack frame](https://en.wikipedia.org/wiki/Call_stack#STACK-FRAME) to be added to the call stack. That’s because each item warrants a call to a function, which needs to be executed to claim its result. Adding a stack frame to the call stack requires some memory to be allocated, and can cause some overhead.

## Tail recursion and tail-call optimization

To keep the memory footprint to a minimum, some languages—like Erlang and thus Elixir—implement tail-call optimization. With a small rewrite of our code, we can prevent the stack frame being added and that memory allocated.

``` elixir
# 1
def sum_numbers3(list) do
  do_sum_numbers3(list, 0)
end

# 2
defp do_sum_numbers3([head | tail], sum) when is_number(head) do
  do_sum_numbers3(tail, sum + head)
end

# 3
defp do_sum_numbers3([_head | tail], sum) do
  do_sum_numbers3(tail, sum)
end

# 4
defp do_sum_numbers3([], sum) do
  sum
end
```

This example is yet another implementation of the function from before. However, this example is tail-recursive, meaning it doesn’t need to await a call to itself before continuing. It does so by keeping an accumulator (`sum`) that keeps the current value instead of stacking function calls.

1. The `sum_numbers3/1` function is the public function, which calls the private `do_sum_numbers3/2` function with the passed list and an accumulator of `0` to start with.
2. Much like the previous example, `do_sum_numbers3/2`'s first function head matches lists with a numeric *head*. It calls itself with the list's *tail*, and the *head* added to the accumulator.
3. When the *head* is not a number, the third function head drops it by calling itself with the *tail* and the current accumulator, without changing anything.
4. Finally, the exit clause returns the accumulator.

By calling itself at the end of the function and passing the accumulator with all calculated values, the Erlang VM can execute a trick called tail-call optimization, which allows it to circumvent adding new stack frames. Instead, it uses the current frame by jumping back up to the beginning of the function.

Tail call optimization allows functions calling themselves without running into stack problems. 

``` elixir
def sleep, do: sleep
```

This example implements a function that continually calls itself. Without tail-call optimization, this function would produce a stack error.

## Which is faster?

We've written three implementations of the same function. The first used `Enum.filter/2` and `Enum.reduce/3` to filter and sum the list, and iterated over the list twice. To fix that, we used a recursive function that did it in one go, which we further improved using tail-call optimization.

``` elixir
letters = Enum.map(?a..?z, fn x -> <<x::utf8>> end)
numbers = Enum.to_list(0..10_000)
list = Enum.shuffle(letters ++ numbers)

Benchee.run(
  %{
    "Enum.filter/2 and Enum.reduce/3" => fn -> Recursion.sum_numbers1(list) end,
    "Body-recursive" => fn -> Recursion.sum_numbers2(list) end,
    "Tail-recursive" => fn -> Recursion.sum_numbers3(list) end
  },
  time: 10,
  memory_time: 2
)
```

To benchmark our solutions, we'll use [Benchee](https://github.com/PragTob/benchee). We'll prepare a shuffled list of strings and numbers for each function to sum for ten seconds.

```
Name                                      ips        average  deviation         median         99th %
Tail-recursive                       107.35 K        9.32 μs    ±21.39%           9 μs          14 μs
Body-recursive                        55.65 K       17.97 μs   ±662.77%          14 μs          34 μs
Enum.filter/2 and Enum.reduce/3       20.86 K       47.94 μs    ±51.46%          46 μs          85 μs

Comparison:
Tail-recursive                       107.35 K
Body-recursive                        55.65 K - 1.93x slower
Enum.filter/2 and Enum.reduce/3       20.86 K - 5.15x slower

Memory usage statistics:

Name                               Memory usage
Tail-recursive                              0 B
Body-recursive                              0 B
Enum.filter/2 and Enum.reduce/3         16064 B
```

In this test on this machine, we see that the body-recursive version is almost three times as fast as the original implementation that used `Enum.filter/2` and `Enum.reduce/3`. The tail-recursive version was almost twice as fast ad the body-recursive one.

## Is tail-call recursion always faster?

While the results of that benchmark look quite convincing, tail-recursion isn't always faster than body recursion. In fact, that's one of the [7 myths of Erlang performance](http://erlang.org/doc/efficiency_guide/myths.html).

While tail-recursive calls are usually faster for list reductions—like the example we’ve seen before—body-recursive functions can be faster in some situations. That's often true when mapping over a list, where the function takes a list and returns a list without reducing it to a single value.

``` elixir
def double_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.map(fn n -> n * 2 end)
end

def double_numbers2([]) do
  []
end

def double_numbers2([head | tail]) when is_number(head) do
  [head * 2 | double_numbers2(tail)]
end

def double_numbers2([_head | tail]) do
  double_numbers2(tail)
end

def double_numbers3(list) do
  list
  |> do_double_numbers3([])
  |> Enum.reverse()
end

defp do_double_numbers3([], acc) do
  acc
end

defp do_double_numbers3([head | tail], acc) when is_number(head) do
  do_double_numbers3(tail, [head * 2 | acc])
end

defp do_double_numbers3([_head | tail], acc) do
  do_double_numbers3(tail, acc)
end
```

This example is a lot like the example we've seen before, but instead of adding all numbers together and reducing them to a single number, the `double_numbers/1` function doubles all numbers and returns them in a list.

Like before, we have three implementations. The first uses `Enum.filter/2` and `Enum.map/2` to iterate over the list twice, the second is body-recursive and the last is tail-recursive. Before returning, the tail-recursive function needs to reverse the list, because the values get prepended to the accumulator.

**Note**: Check out the [example project](https://github.com/jeffkreeftmeijer/elixir-recursion-example) for a comparison of more possible implementations, like list comprehensions and a tail-recursive version that doesn't reverse the list.

```
Name                                   ips        average  deviation         median         99th %
body-recursive                     36.86 K       27.13 μs    ±39.82%          26 μs          47 μs
tail-recursive                     27.46 K       36.42 μs  ±1176.74%          27 μs          80 μs
Enum.filter/2 and Enum.map/2       12.62 K       79.25 μs   ±194.81%          62 μs         186 μs

Comparison:
body-recursive                     36.86 K
tail-recursive                     27.46 K - 1.34x slower
Enum.filter/2 and Enum.map/2       12.62 K - 2.92x slower

Memory usage statistics:

Name                            Memory usage
body-recursive                      15.64 KB
tail-recursive                      20.09 KB - 1.28x memory usage
Enum.filter/2 and Enum.map/2        31.33 KB - 2.00x memory usage
```

When running a benchmark for each of these implementations, we can see that the body-recursive version is fastest in this case. Having to reverse the list in the tail-recursive version negates the improved performance tail-call optimization adds in this specific case.

## As always, it depends

This concludes our look into recursion in Elixir. As a rule of thumb; tail-recursive functions are faster if they don't need to reverse the result before returning it. That's because that requires another iteration over the whole list. Tail-recursive functions are usually faster at reducing lists, like our first example.

Which is the best approach depends on the situation. For mission-critical loops, writing a benchmark to measure which solution is faster is usually your best bet, as it's not immediately obvious which will perform better.

To learn more about recursion, also be sure to read [this overview](https://blog.appsignal.com/2019/03/19/elixir-alchemy-recursion.html) of the available methods, and when to use which. If you liked this article, don't forget to [subscribe to the mailing list](https://blog.appsignal.com/elixir-alchemy) if you'd like to read more Elixir Alchemy!