Avoiding Stack Overflow…s

As a recap, a call stack helps interpreters to keep track of its place in a script that calls multiple functions — currently running functions, functions that are called from within other functions, functions that are going to be called next...you get the picture.
Proper Tail Calls (PTC)
Simply put, PTCs are functions that can be executed without growing the stack. You know that you’re making a PTC if :
- Your function is the last thing to be done and evaluated before the
return - The return value of this called function is returned by the calling function
- The calling function is not a generator function
An example of PTC is the below function that is tail recursive:
function factorial(n, total = 1) {
if (n === 0) {
return total
} return factorial(n - 1, n * total)
}
The last thing this function will do is return the result of calling itself — nothing more!
Something to note is that now two arguments are passed to the function:
- The number we want to calculate the next factorial of (n - 1)
- The accumulated total, which is n * total.
But how this function is able to execute without stacking multiple recursive calls?
Let’s see what goes on when we call factorial(4):
factorial(4, 1) // 1 is the default value when nothing gets passed
factorial(3, 4) // This call does not need the previous one, it has all the data it needs
factorial(2, 12) // This call does not need the previous one, it has all the data it needs
factorial(1, 24) // This call does not need the previous one, it has all the data it needs
factorial(0, 24) // -> Returns the total (24) and also does not need the previous oneInstead of stacking n frames, we just need to stack 1, since the subsequent calls don’t depend on the previous ones, which makes our new factorial function have a memory complexity of O(1) instead of O(N). The idea is that if the calling function does not actually do anything else but return to its caller after the called function has returned, the call is basically replaced by a jump and the current stack frame is reused.
Tail Call Optimization (TCO)
Onto optimization. TCO is the moment that an interpreter realizes that the last thing a function needs to do before it is returned, is evaluate another function invocation inside of it.
When you declare a function it’s added to global memory. When invoked, a few things will happen:
- The location to return to is saved on the call stack inside a new stack frame
- The interpreter will jump inside the function’s new execution context
- Any parameters will be initialized within the function’s local variable environment
In the above instance, the call stack takes up space, and if too many functions are pushed onto the call stack before it can pop them off… ‘Maximum call stack size exceeded’! Not cool. With recursion, this error is caused by one of two things — a bad base case or a function that requires too many recursive calls before it can even reach the base case.
An example is a manually written Math.pow() with recursion:
function pow(base, power) {
if (power === 0) return 1;
else
return pow(base, power - 1) * base; //tail call === false
}This will create a new stack frame each time we recursively call pow() until our base case is reached. So…
pow(4, 84599); //bad ideaTo avoid this, we need to remove any unnecessary references to local variables in the return statement. Basically get rid of the ‘* base’.
function pow(base, power) {
if (power <= 0) return 1;
return helper(base, power, base); //tail call === true
}function helper(base, power, num) {
if (power === 1) return num;
else return helper(base, power - 1, base * num);
}
Now the last thing being evaluated before the function returns is a function invocation, and that is exactly what TCO is.
This is just something useful to keep in mind when using recursive function calls, but there are times where iterative calls would be a better bet.
That’s a post for another day, though.

Resources:
http://2ality.com/2015/06/tail-call-optimization.html
https://medium.com/@mlaythe/js-es6-recursive-tail-call-optimization-feaf2dada3f6
