Understanding Recursion and Tail Call Optimisation in Elixir

Jun 06, 2016

Table of contents:

1. How does recursion work in Elixir?
2. What is Tail Call Optimisation?
3. Examples of recursion in Elixir
4. Conclusion

Last week we looked at branching and conditionals logic and how we can rewrite these constructs as multi-clause functions to make our code more declarative and easier to understand and read.

If you are coming to Elixir from another programming language you are probably very accustomed to using loops to iterate through a list of items.

Something that may surprise you about Elixir is, there are no constructs for while or do...while.

Instead, Elixir prefers to use recursion to achieve dynamic looping. In today’s tutorial we will look at recursion.

How does recursion work in Elixir?

So if we don’t have the while construct in Elixir, how do you iterate through a list?

The answer is our new favourite partnership of pattern matching and multi-clause functions!

First you define the clause that will be the last step of the process. Typically this will handle the situation when the list is empty.

Next you define more generic clauses that you can call recursively to iterate through the list.

For example, imagine we have a module that will print each element of a list:

defmodule MyList do
  def read([]), do: IO.puts("End of list")

  def read([head | tail]) do
    IO.puts(head)
    read(tail)
  end
end

Firstly, we define a function that will deal with the last step of the process. In this example we have a read/1 function that matches an empty list. If the list is empty we will print a message to alert the user.

Second, we define a more generic function that accepts a non-empty list.

We pattern match the list into the head and the tail and we print the head.

Finally we call the read/1 function again with the tail.

If the tail contains elements it will pattern match against the second definition. But if the list is empty the call to the read/1 function will pattern match to the first definition which will print the final message and end the recursion.

So as you can see, we can effectively loop through the list using pattern matching, multi-clause functions and recursively calling the same function.

Again, as with last week, although this involves writing multiple functions, this approach has many benefits.

Firstly, your code is a lot more declarative. You can see what will happen when the list is empty verses if the list is not empty.

And secondly you can deal with each step of the process as a single, simple function definition.

What is Tail Call Optimisation?

If you’ve ever read into functional programming you may have heard the term “Tail Call Optimisation”. Unless you’ve really been digging into a functional programming language in the past, you have probably no idea what this even means, I know I certainly didn’t!

I’ll try and explain the concept here.

When you recursively call a function, the computer will allocate memory for every element in the list. This is probably going to be fine for a small list, but in the case of a really big list, you might run out of memory!

For example, here is an example of a Module for adding each element of a list together and return the total:

defmodule MyList do
  def sum([]), do: 0

  def sum([head | tail]) do
    head + sum(tail)
  end
end

MyList.sum([1, 2, 3]) |> IO.puts()

As you can see, first we define the empty list clause. In this case we return 0 for an empty list.

Next we define the non-empty clause that will be recursively called. This function splits the list into the head and the tail and then it returns the value of adding the head and the return value from the sum/1 function when given the tail.

If you run this code you should see it produce the correct answer of 6.

So what’s the problem with this and where does Tail Call Optimisation come in?

If you were to run this function with a very big list of numbers you would eventually run out of memory. As I mentioned earlier, this is because the computer needs to allocate memory for each element in the list as the function is called recursively.

The solution to this problem is to slightly rewrite the function to take advantage of Tail Call Optimisation.

Tall Call Optimisation is where if the last thing a function does is call another function, the compiler can jump to the other function and then back again without allocating any additional memory.

The Erlang compiler will do this automatically because it will recognise the tail call, we just need to write out code in a certain way to take advantage of this optimisation.

This is great for recursive functions because it can run for a very large list without allocating any additional memory.

The reason why the example from above does not take advantage of tail call optimisation is because the last thing that occurs in the function is not a call to another function.

def sum([head | tail]) do
  head + sum(tail)
end

As you can see, the last thing that happens is the addition between the return value from the sum/1 call and the head.

Lets rewrite this function to take advantage of tail call optimisation:

defmodule MyList do
  def sum([], accumulator), do: accumulator

  def sum([head | tail], accumulator) do
    sum(tail, head + accumulator)
  end
end

MyList.sum([1, 2, 3], 0) |> IO.puts()

First we define the sum/1 empty list clause that will simply return the accumulator that is passed in.

Next we define the non-empty list clause that will recursively call itself, each time taking the head and adding it to the accumlator until the list is empty.

Examples of recursion in Elixir

Lets take a look at a couple of more examples of writing recursive functions in Elixir.

First, here is an example of doubling each value in a list:

defmodule MyList do
  def double([]), do: []

  def double([head | tail]) do
    [head * 2 | double(tail)]
  end
end

This is pretty similar to the previous examples but instead of passing an accumulator we just return a new list with the head multiplied by 2.

Next, here is an example of only returning the even values from a list:

defmodule MyList do
  def evens([]), do: []

  def evens([head | tail]) when rem(head, 2) == 0 do
    [head | evens(tail)]
  end

  def evens([_ | tail]) do
    evens(tail)
  end
end

Once again we first define the empty-list clause.

Next we define a clause that matches a non-empty list, but only when the head is an even number. We then return a new list with the head and a recursive call with the remaining tail.

Next we define the clause for a non-empty list when the head is not an even number. Here we don’t care about the head so we can just recursively call the evens function with the remaining tail.

Finally, here is an example of a map/2 function that takes a list an an anonymous function that will be applied to each element of the list:

defmodule MyList do
  def map([], _), do: []

  def map([head | tail], func) do
    [func.(head) | map(tail, func)]
  end
end

MyList.map([1, 2, 3], &(&1 * &1))

Once again we first define the empty state clause that will simply return the empty list.

Next we define the general non-empty clause that will call the function on the head and then pass the tail and the function back into the map/2 function to be called recursively until the list is empty.

The anonymous function in this example will simply multiply each element by itself.

If this anonymous function definition looks a bit strange to you, take a look at Functions as First-Class Citizens in Elixir.

Conclusion

Recursion is an important aspect of learning Elixir and is probably not something you do that often if you are coming from from another programming language.

Tail call optimisation is another important thing to understand as you could come across a situation where you are running out or memory due to how memory is allocated for each element of your list.

However, you probably won’t write these types of functions because they’re already available to you via the Enum module. But it’s still worth understanding what’s going on in case you do.