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
function factorial(num, accumulated = 1) { if (num <= 1) { return accumulated; } else { return factorial(num - 1, num * accumulated); // proper tail position }} factorial(10) //=> 3628800factorial(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:
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
$ npm install --save-dev babel-plugin-proper-tail-calls
Usage
Add the following line to your .babelrc file:
babel --plugins proper-tail-calls script.js
Via Node API
;