# Understanding Recursion and Tail Call Optimisation in Elixir

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")

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
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
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
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.