• Safe Recursion with Trampoline in JavaScript
  • Original article by Valeriy Baranov
  • The Nuggets translation Project
  • Permanent link to this article: github.com/xitu/gold-m…
  • Translator: Gesj – yean
  • Proofreader: CYZ980908, z0gSh1u

Use the trampoline function in JavaScript for safe recursion

Recursion is not safe in JavaScript, consider using trampoline functions. It turns the recursion into a while loop to get around JavaScript’s limitations in order to prevent overflow.

A typical recursive function is factorial calculation. We call factorial n times to get a result. Each call adds a factorial function to the calling stack.

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(5)); / / 120
Copy the code

Recursion in JavaScript is often a sign that something is wrong with your code and should generally be avoided. Because JavaScript is a stack-based language, there is currently no tail-call optimization. If you run the following code, RangeError will be reported: Maximum Call stack size exceeded, meaning the Maximum call stack size exceeded.

function recursiveFn(n) {
  if (n < 0) return true;
  recursiveFn(n - 1);
}

recursiveFn(100000); // RangeError: Maximum call stack size exceeded
Copy the code

However, there are situations where recursive functions are necessary. For example, traversing a DOM tree or other tree structure.

function traverseDOM(tree) {
  if (isLeaf(tree)) tree.className = 'leaf';
  else for (const leaf of tree.childNodes) traverseDOM(leaf);
}
Copy the code

Trampoline functions – Safe recursion in JavaScript

Using the trampoline function, you can convert a recursive function to a while loop:

function trampoline(f) {
  return function trampolined(. args) {
    let result = f.bind(null. args);while (typeof result === 'function') result = result();

    return result;
  };
}
Copy the code

Let’s rewrite a factorial function using a trampoline function. We need to go to:

  1. Returns a value in the base case.
  2. In other cases return the function to be called.

We also added an accumulator parameter to the internal implementation of _factorial.

const factorial = trampoline(function _factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return (a)= > _factorial(n - 1, n * acc);
});

console.log(factorial(5));
Copy the code

RecursiveFn can be overridden like factorial, but we do not need an accumulator to track the state. This implementation can even safely run millions of iterations.

const recursiveFn = trampoline(function _recursiveFn(n) {
  if (n < 0) return;
  return (a)= > _recursiveFn(n - 1);
});

recursiveFn(100000);
console.log('No range error! ');
Copy the code

The next time you want to use recursion, try the trampoline function.

You can try the trampoline function here at CodePen.

Trampoline function is not a popular technique. Even in Ramda and Lodash, trampoline functions are not provided.

Thanks to Kyle Simpson for providing the inspiration for the trampoline function.

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.