Proper Tail Calls in JavaScript

Proper tail calls are recursive function calls that do not need to allocate extra stack space proportional to recursion depth. They are a part of the ECMAScript 6 standard but are currently only supported in Safari. This plugin implements proper tail calls through a technique called function trampolining. Using the proper-tail-calls plugin, a program could make an unbounded number of consecutive tail calls without unboundedly growing the stack.

Example

``JavaScript
function factorial(num, accumulated = 1) {
if (num <= 1) {
return accumulated;
} else {
return factorial(num - 1, num * accumulated); // proper tail position
}
}

factorial(10)
//=> 3628800
factorial(32687)
//=> RangeError: Maximum call stack size exceeded

const { code } = babel.transform(factorial.toString(), {
plugins: ["proper-tail-calls"]
})

factorial = Function(${code} return factorial)()
factorial(32687)
//=> Infinity
`

How It Works

Recursive calls that are in a proper tail position will be trampolined. Instead of recursing directly, the recursive call is deferred and a wrapper function is returned.

The factorial example above transpiles to:

`JavaScript
var factorial = _trampoline(function factorial(num, accumulated = 1) {
if (num <= 1) {
return accumulated;
} else {
return () => {
return factorial(num - 1, num * accumulated);
}
}
})

function _trampoline(fn) {
return function trampolined(...args) {
let result = fn(...args);
while (typeof result === 'function') {
result = result();
}

return result;
};
}
`

Installation

`sh
$ npm install --save-dev babel-plugin-proper-tail-calls
`

Usage

Add the following line to your .babelrc file:

`json
{
"plugins": ["proper-tail-calls"]
}
`

`sh
babel --plugins proper-tail-calls script.js
`

$3

`javascript
require("@babel/core").transform("code", {
plugins: ["proper-tail-calls"]
});
``