In this article, we’ll be talking about a widespread concept of Functional Programming called Tail Call Recursion (or Tail Call Optimization or just Tail Call). If you have been around FP for some time, you might have already come across this concept, but if not or you want to know more, climb aboard and let’s get into it.

What tail-recursive functions are?

The first time I saw this concept was when reading Joe Armstrong’s book "Programming Erlang: Software for a concurrent world". In this context, he was using it on Erlang processes that ran in a recursion that never stops. Below we can see his words about tail calls:

A tail-recursive function can be compiled so that the last function call in a sequence of statements can be replaced by a simple jump to the start of the function being called. This means that a tail-recursive function can loop forever without consuming stack space.

That makes sense. If we need to run a function forever we need to save our stack and tail calls are what should do the trick for us.

Right after that, studying another language (Elixir) the concept of tail-recursive functions came up again, but this time with a different perspective. For this case, tail-calls could be used not just to save stack, but also to save heap memory as well, and beyond that: they should be faster than a recursive-body function. After running some tests I got some quite unexpected results.

Before talking about these tests and their results, let’s know what a tail-recursive function looks like in its form.

Tail-recursive and body-recursive shapes

defmodule Factorial do
  def body_recursive_factorial(0), do: 1
  def body_recursive_factorial(n) when n > 0, do: n * body_recursive_factorial(n-1)

  def tail_recursive_factorial(n), do: tail_recursive_factorial(n, 1)
  def tail_recursive_factorial(0, acc), do: acc 
  def tail_recursive_factorial(n, acc) when n > 0, do: tail_recursive_factorial(n-1, n*acc) 
end

In the code above, both body_recursive_factorial and tail_recursive_factorial calculate the factorial for a given number. The first does it more conventionally, whereas the second does it differently: it uses tail-recursion accumulators.

Note: When you use accumulators, you’ll fall into using tail-recursive functions.

The misconceptions about tail-recursive functions

Assuming tail-recursive functions will be better than body-recursive functions is a common mistake that some beginners books and tutorials make.

In the book Learn Functional Programming with Elixir, there is a comparison between the two types of factorial functions. The results presented are very interesting. As suggested by the author, I implemented two functions, one using tail-recursion and the other not, and ran them by time looking at the memory usage with Activity Monitor of MacOS and the results were quite similar to each other.

To get more precise results I used a Benchee and ran these two functions with different inputs. The results can be found at https://gist.github.com/geeksilva97/909ebb54029033dea0afbd0206e853ea. As you can see, there’s not much difference between them. Both reach memory peaks of ~6GB when calculating the factorial of 150.000, for instance.

Researching about tail-recursion in Erlang/Elixir I found some interesting discussions and documents. I started by reading the The Seven Myths of Erlang Performance again and I was led to this great blog post about tail-recursion specifically. Starting from these two links I found a discussion involving Robert Virding (co-creator of Erlang) where he makes it very clear when he says:

…the main case where is TCO is critical is in process top-loops. These functions never return (unless the process dies) so they will build up a stack never to release it. Here you have to get it right. There are no alternatives. The same applies if your top-loop is composed of a set of mutually calling functions. There there are no alternatives. Sorry for pushing this again, and again, but it is critical.

In other cases my way of choosing is the one that gives me the most intelligible code. And that varies depending on what the function is supposed to do and how I choose to do it.

I agree with Armstrong’s quote mentioned earlier. So, let’s back to the title of this post. Based on these rich discussions we can conclude that tail-recursion isn’t enough. Sometimes tail functions might perform better, sometimes they won’t.

What shall we do?

This article is not intended to be a silver bullet. It’s all about bringing up some experiments that I did and some researches that led to other experiments done by more experienced people. The goal is to open your eyes to this possible trap you might fall into.

As a beginner in functional programming, prefer to stay safe. If I could advise you, I would say "Don’t assume, prove it." I think it should be done for (almost) every situation.

Sometimes it will not be a choice, but when it is, you could list the pros and cons of writing a function in a specific way. Following Robert’s advice prefer to make code clear, understandable, and more:

[…] I agree that you should know what it gives you and why and when it is important. There are many cases where you end up with TCO as a result of a solution you chose for other reasons. For example often when you carry values around in accumulators you end up with a tail-recursive function even if this was not the goal.
And the efficiency always needs to be measured. Saving stack can however save you Garbage Collection even if you may not save memory.

Summary

In this article, we learned a little about tail recursion and discussed its effectiveness.

Our conclusions were based on our tests and some quotes from books and forums involving not only the creators of Erlang but the creator of Elixir as well.

The bottom line of the article is: Don’t blindly believe the information you find in books, blog posts, or anything like that. Be critical and do your experiments. Try as many cases as you can (especially if you’re a beginner) and if you get unexpected results, try to find out why. If you can’t figure out why find out someone who can.

I plan on trying more experiments, even on other OTP versions. If I get some interesting results I’ll make sure to bring them back here and update the article.

Let me know if you have any questions and If you liked this content consider sharing it with your friends.

That’s all. See ya!

References

• TAIL CALL OPTIMIZATION IN ELIXIR & ERLANG – NOT AS EFFICIENT AND IMPORTANT AS YOU PROBABLY THINK
• Tail Call Optimization in Elixir & Erlang – not as efficient and important as you probably think
• Discussion about tail-recursion in Elixir lang repository
• Erlang’s Tail Recursion is Not a Silver Bullet
  

We want to work with you. Check out our "What We Do" section!