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)
  //=> 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:

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:

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

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

Via Node API

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