Tail-call optimization

March 9, 2021

Yesterday I learned about tail-call optimization in recursive functions:

https://dino.codes/posts/tail-call-optimization-in-elixir/

The long and short of it is we can use accumulator variables to cut the number of instructions executed on recursive calls. I’m gonna use an Elixir example since optimizations in C depend a lot on the compiler:

https://stackoverflow.com/questions/3514283/c-tail-call-optimization

defmodule UnoptimizedSum do
  def call(list), do: sum(list)

  defp sum([]), do: 0
  defp sum([head | tail]), do: head + sum(tail)
end

In UnoptimizedSum, we only start adding the values after the last sum() call:

UnoptimizedSum.call([5, 4, 3, 2, 1])
= 5 + UnoptimizedSum.sum([4, 3, 2, 1])
= 5 + (4 + UnoptimizedSum.sum([3, 2, 1]))
= 5 + (4 + (3 + UnoptimizedSum.sum([2, 1])))
= 5 + (4 + (3 + (2 + UnoptimizedSum.sum([1]))))
= 5 + (4 + (3 + (2 + (1 + UnoptimizedSum.sum([])))))
= 5 + (4 + (3 + (2 + (1 + 0))))
= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3))
= 5 + (4 + 6)
= 5 + 10
= 15

This means that the compiler will execute two instructions for every element of the list: one for the sum call and one for the addition.

defmodule OptimizedSum do
  def call(list), do: sum(list, 0)

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

Now in OptimizedSum, we add the values on every recursive call:

OptimizedSum.call([5, 4, 3, 2, 1])
= OptimizedSum.sum([4, 3, 2, 1], 5)
= OptimizedSum.sum([3, 2, 1], 9)
= OptimizedSum.sum([2, 1], 12)
= OptimizedSum.sum([1], 14)
= OptimizedSum.sum([], 15)
= 15

and we execute half the instructions for the same operation. I thought it was a really neat trick and I’m gonna try and use it more often.

Today I’ll keep on studying Elixir and working on printf.