Tail Call Optimization In Elixir

A tail-recursive function executes itself as the last thing.

def fun(...) do
    ...
    fun(...)
end

Elixir optimizes tail calls by reusing the last stack frame of the function, thus avoiding the typical stack push and reducing the overhead of creating and removing stack frames during function calls.

This function calculates the nth Fibonacci sequence element.

defmodule Fibonacci do
  def nth(n) when n <= 1, do: n

  def nth(n) do
    nth(n - 1) + nth(n - 2)
  end
end

This function is not tail-recursive, as the tail call involves the summation of two functions.

This is (my) tail recursive version of the same function:

defmodule Fibonacci do
  def nth(n) when n <= 1, do: n

  def nth(n) do
    fib(n - 2, 1, 0)
  end

  defp fib(0, minus_1, minus_2) do
    minus_1 + minus_2
  end

  defp fib(n, minus_1, minus_2) do
    fib(n - 1, minus_1 + minus_2, minus_1)
  end
end

This function is tail-recursive, as the tail call directly invokes the function itself.

Let's compare the execution duration of the two functions with the following code one by one.

start_time = :os.system_time(:native)
result = Fibonacci.nth(20)
end_time = :os.system_time(:native)
duration = end_time - start_time
IO.puts("result: #{result} duration: #{duration} nanoseconds")

Output of the first version:

result: 6765 duration: 60000 nanoseconds

Output of the optimized version:

result: 6765 duration: 1000 nanoseconds

The tail-call optimization significantly improved the execution time.

Thanks for reading!