The solution? A process known as trampolining. It's a way to "hack" the concept of tail-call elimination into a program by using thunks.

A trampoline is a function that takes a function as input and repeatedly executes its returned value until something other than a function is returned. A simple implementation is shown in the following code snippet:

var trampoline = function(f) {   while (f && f instanceof Function) {     f = f.apply(f.context, f.args);   }   return f; }

To actually implement tail-call elimination, we need to use thunks. For this, we can use the bind() function that allows us to apply a method to one object with the this keyword assigned to another. Internally, it's the same as the call keyword, but it's chained to the method and returns a new bound function. The bind() function actually does partial application, though in a very limited way.

var factorial = function(n) {   var _fact = function(x, n) {     if (n == 0) {       // base case       return x;     }     else {       // recursive case       return _fact.bind(null, n*x, n-1);     }   }   return trampoline(_fact.bind(null, 1, n)); }

But writing the fact.bind(null, ...) method is cumbersome and would confuse anybody reading the code. Instead, let's write our own function for creating thunks. There are a few things the thunk() function must do:

With that, we're ready to write the function. We only need a few lines of code to write it.

var thunk = function (fn) {   return function() {     var args = Array.prototype.slice.apply(arguments);     return function() { return fn.apply(this, args); };   }; };

Now we can use the thunk() function in our factorial algorithm like this:

var factorial = function(n) {   var fact = function(x, n) {     if (n == 0) {       return x;     }     else {       return thunk(fact)(n * x, n - 1);     }   }   return trampoline(thunk(fact)(1, n)); }

But again, we can simplify it just a bit further by defining the _fact() function as a thunk() function. By defining the inner function as a thunk() function, we're relieved of having to use the thunk() function both inside the inner function definition and in the return statement.

var factorial = function(n) {   var _fact = thunk(function(x, n) {     if (n == 0) {       // base case       return x;     }     else {       // recursive case       return _fact(n * x, n - 1);     }   });   return trampoline(_fact(1, n)); }

The result is beautiful. What seems like the function _fact() being recursively called for a tail-free recursion is almost transparently processed as an iteration!

Finally, let's see how the trampoline() and thunk() functions work with our more meaningful example of tree traversal. The following is a crude example of how a data tree could be traversed using trampolining and thunks:

var treeTraverse = function(trunk) {   var _traverse = thunk(function(node) {     node.doSomething();     node.children.forEach(_traverse);   }   trampoline(_traverse(trunk)); }

We've solved the issue of tail recursion. But is there an even better way? What if we could simply convert the recursive function to a non-recursive function? Up next, we'll look at how to do just that.