Consider the following function that calculates the factorial of a number:
The function above was implemented iteratively, that is, it uses a loop to calculate the factorial of a number. However, it is possible to implement the same function recursively (that is, a function that references itself):
A call stack is a data structure that stores information about a program's functions. When a function is called, it is added to the execution stack, as well as all the functions it calls. When a function returns, it is removed from the execution stack. Each function added to the stack is called a stack frame.
In order to understand what is happening, let's try to represent, graphically, how the calculation of the factorial of 6 is done with the iterative function:
Now, compare it with the substitution model for calculating the factorial of 6 using the recursive function:
Note that, in the iterative function, the arrow shape is linear and we can see the state of each variable at each step. In addition, at each iteration of our loop, a calculation is performed and the variables stored in memory are updated. In the recursive function, the arrow shape is exponential and we cannot see the state of all variables in the first half of the processing. In addition, each time the function is executed, more memory needs to be used to store the resulting values of each execution.
while condition is added to the stack, where its calculation is performed, the
result variable is updated, and then the executed code block of the
while is removed from the stack. This is done until the while condition is false, that is, until the value of
n is less than or equal to 1.
In the recursive function, each call to the
factorial function is added to the stack as many times as necessary until the if condition is false, that is, until the value of
n is less than or equal to 1. This means that, to calculate the factorial of 6, the
factorial function is added to the stack 6 times before being executed. And that's why, when we try to calculate the factorial of a large number (100,000, for example), we encounter the error
RangeError: Maximum call stack size exceeded: there is not enough space in the stack to store all the calls to the
Introducing Tail Call Optimization
As defined by Dr. Axel Rauschmayer:
[...] whenever the last thing a function does is call another function, then this last function does not need to return to its caller. As a consequence, no information needs to be stored on the call stack and the function call is more like a goto (a jump). This type of call is called a tail call; not increasing the stack is called tail call optimization (TCO).
Now, we have discovered that our factorial calculation function is not tail recursive. But how can we make it tail recursive? With the help of another function:
Now, our function is tail recursive: the last thing it does is call a function (and not calculate an expression, as in the first implementation). Now, let's see the substitution model for calculating the factorial of 6 with our new
The performance is superior to our first implementation, although it still doesn't beat the performance of the iterative function. However, we still encounter the error
RangeError: Maximum call stack size exceeded. But why does this happen? Because, despite our function being tail recursive, current versions of Node.js and browsers (with the exception of Safari) do not implement Tail Call Optimization (despite its inclusion in the EcmaScript specification since 2015).
But how will we solve this problem? With the help of another function, of course! For that, we will rely on the Trampoline pattern:
Our trampoline function consists of a loop that invokes a function that wraps another function (what we call a thunk) until there are no more functions to execute. Let's see how the implementation of our factorial function would look like with the Trampoline pattern:
And now, we can call our factorial function with a large number, without encountering the error
RangeError: Maximum call stack size exceeded. Of course, depending on the factorial we want to calculate, we will encounter an Infinity, as it is a very large number (a number greater than Number.MAX_SAFE_INTEGER: 253 - 1). In this case, we can use BigInt:
Typing our function
And finally, let's add the necessary types to our factorial function: