PROPER TAIL CALLS

A tail call happens when a function Foo calls a function Bar as its final action. At that point Foo stops and passes the execution to function Bar and disappears not having to do anything from there onwards.

The process of one function calling another may end up creating a new stack frame, if the first function returns a result to the second.

function factorial(n) {
    function recur(n, acc) {
        if (n === 0) {
            return acc;
        } else {
            return recur(n-1, n*acc);
        }
    }
    return recur(n, 1);
}

factorial(100000);

After factorial calls recur, it has nothing else to do. In such situations, the program does not need to return to the calling function when the called function ends. Therefore, after the tail call, the program does not need to keep any information about the calling function in the stack. ES6 takes advantage of this fact and actually do not use any extra stack space when doing a tail call. We say that those implementations support proper tail calls (PTC).

Because a proper tail call uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. For instance, we can call the following function with any number as argument; it will never overflow the stack:

function foo(n) {
  if (n > 0) {
    return foo(n - 1);
  }
}

What qualifies to be a tail call?

A subtle point when we use proper tail calls is what is a tail call. Some obvious candidates fail the criteria that the calling function has nothing to do after the call. For instance, in the following code, the call to bar is not a tail call:

function foo(n) {
  bar(n);
  return;
}

The problem in that example is that, after calling bar, foo still has to discard occasional results from bar before returning. Similarly, all the following calls fail the criteria:

return bar(n) + 1; // must do the addition
return n || bar(n);    // must adjust to 1 result
return n && bar(n);       // must adjust to 1 result

Here is another scenario:

function sum(...values) {
  return values.shift() + sum(...values);
}

In the above scenario + operation is executed after the recursive call, which disqualifies it to be a proper tail call (PTC).

To change the above function to make a proper tail call, introduce a helper function with an accumulator parameter.

function sum(...values) {
   function sumTo(acc, values) {
       return sumTo(acc + values.shift(), values); // tail-recursive call
   }
   return sumTo(0, values);
 }

Without proper tail calls, each user move would create a new stack level. After some number of moves, there would be a stack overflow. With proper tail calls, there is no limit to the number of moves that a user can make, because each move actually performs a goto to another function, not a conventional call.