Tail End Recursion in Elixir

In Elixir the most used tool for iterating through collections is recursion. Most of us know recursion as referencing a function within its own invocation. This function gets called until it arrives at a base terminating case or after it has been called a fixed number of times. An example of a recursive function in elixir would be as follows:

# 1
def multiply_numbers2([head | tail]) when is_number(head) do
multiply_numbers2(tail) * head
end

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

# 3
def multiply_numbers2([]) do
1
end

The problem with this implementation is that at greater collection sizes, the compiler will have to use a linear amount of memory in order to generate the desired outcome. This is because, as written, each following stack directly relies on the output of the stack before it. As a result, the compiler and the garbage collector must keep each previous stack around until the final terminating function call.

Elixir however allows for something called tail end optimization. The idea used by compilers to optimize tail-recursive functions is simple: since the recursive call is the last statement in the function call, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use. We could rewrite the above function as:

# 1
def multiply_numbers(list) do
do_mult_numbers(list, 0)
end

# 2
defp do_mult_numbers([head | tail], prod) when is_number(head) do
do_mult_numbers(tail, prod * head)
end

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

# 4
defp do_mult_numbers([], prod) do
sum
end

Here as we can see, we are making a public call to our private recursive function. Instead of having the math be the last thing we do in our function calls, we make the function call itself be the last thing we do. Since we are keeping track of state between calls with the product variable, there is no reason for the compiler to remember the state of the previous stack. Therefore, we are able to achieve a constant space complexity as opposed to a linear one.

Tail end recursion is a power optimization tool that should be taken advantage of whenever possible!

Full-Stack Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store