This article orignially appeared on Michael Nunez's personal blog in January 2017.
Today, we’ll discuss Tail Call Optimization, and how it is useful in very complex problems that we may run into on a day to day basis.
According to Wikipedia:
"In computer science, a tail call is a subroutine call performed as the final action of a procedure. If a tail might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion."
Tail recursion is calling a function that will return the same function with different variables. Rather than adding a new function call to the stack, it will return the function with the new variables.
In the example, we will use Fibonacci written in both Ruby and Elixir. We will also optimize the Elixir example to use Tail Call Optimization.
In Ruby, the code looks like this:
This app simply starts a timer, get’s the Fibonacci number to the
n’s place. When we run it to the 40th place, we get following:
In Elixir, we have a similar solution:
Very similar to the ruby example, the timer starts, calls the
getNumber function, and returns the number.
One noticeable difference is that it took 15 longer for the ruby solution to find the same Fibonacci number!
But we can definitely make this faster with Tail Call Optimization. We will make some changes to our
It is very common practice to have an interface of
getNumber with an arity 1, that then calls a private function with a greater arity to facilitate the Tail Call Optimization pattern.
The very first function of
getNumber(n) calls the private function with a variable signature containing the place in the Fibonacci sequence, the starting number, and it’s previous number. Since the first number is 0, and the next number 1, we can use those to start our Fibonacci function.
Here’s where the magic happens! When we call
defp getNumber(n, next, result)we call the very same function, but with different parameters.
do: getNumber(n-1, next+result, next). It subtracts 1 from the sequence, since we’re counting down to zero, it adds the result to the next number, and the next number becomes the result. Since the function is calling itself, it doesn’t have to place a new function in the stack. It calls the same function with new parameters.
defp getNumber(0, _, result), do: result states that when the number has reached zero, return the result.
OK speedy, let’s see you try a bigger number!
o.O! Wise guy, eh?!
This is getting out of hand…
In fact, I was able to go up to 100,000! Check it out!!
Pretty amazing stuff!!
Finally getting the hang of Tail Call Optimization! Let me know what you think, and what other real world solutions would you use it in!
Want more ways to simplify your next software development project? Check out Stride's collection of free open source tools today and see how they can help you.