So what is a Tail-Call Optimization and why you should use it?
Well hi there! It’s been a while! 😆
So, recently I am studying in my free time about functional programming, specially using Elixir. At certain point of this journey I came across a very interesting optimization concept, that applies not only to functional programming (which we could say is the cradle of this kind of techniques) but to every recursive function call!
It’s a little tricky to get it in the first time (at least, for me it was 😅), but stick with me in this one, and you’ll get it (I suppose).
Tail-Call Optimization
So, yeah, let’s take a look at what Wikipedia has to say about it:
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail-recursive, which is a special case of direct recursion. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.
A little bit scary, uh? But let me explain in some detail.
(Just to clear things up, I’ll explain with my words, the way a came up with to understand it myself, not necessarily the terms I’ll use reflect the REAL MEANING of what it is).
How it works WITHOUT Tail Call Recursion?
Okay, so you probably already done the classical factorial exercise on recursion, something like this.
So, maybe your call stack, this way, at runtime, would be something like this:
Now, think with me. While the factorial of 3, then 2, then 1 are executing (e.g getting called and evaluated), the state of the call stack have to be kept in memory.
You can’t just ignore that there was an actual call to factorial(4), then to factorial(3), and so on, until you hit the bottom line at factorial(1).
So the memory kept all of this information in the call stack, and that isn’t a big problem in cases of 4-level deep calls. But think about the factorial of 1.000.000?
That’s where the Tail-Call comes into play
Let’s forget about it!
So let’s change things a little, not only our perspective will change, but out language too, as I said, it comes more often in functional languages, and as I also said, I’m into Elixir now (this phrase got a little rude, sorry 🤪)
So, here we go!
Remember how we were just calling the same function before it has ended? Like, to the the actual factorial of 4, we call the other factorials from smaller numbers, and then, as we got its results, we pass it to the factorial of 4 to finish, and this is true to every other call in that stack!
So, what is getting us here, is that would be a lot better if we just don’t need to remember that function’s state, don’t have to wait on other functions’ returns to get our job done, and we’ll do this by calling just ONE FUNCTION AT A TIME, but how?
It is pretty simple, but hard to digest. So, calm down, breath in, and here we go:
Alright, here we go. Besides the “validation” done to get sure the n passed was a integer grater than zero. We pass it to a helper function called “factorial_of”, which is private.
The main goal here is, we won’t call factorial_of a decreasing n parameter and get its results, we will actually pass the state of the parent function call to the new function call via the accumulator variable.
So now, we won’t multiply by the return of a incoming function, we will multiply by the parameter acc and then pass the exact same parameter to the next call, getting sure every call starts and ends right there.
And so, your call stack should be something like this:
See? There’s no more that pyramidal shape in your call stack, you did save a lot of memory usage. Congrats! 👏
