[译] 使用JavaScript中的蹦床函数实现安全递归

原文转载自 「掘金掘金翻译计划」 ( https://juejin.im/post/5ec3eec2f265da76d318644e ) By Huup_We

预计阅读时间 0 分钟(共 0 个字, 0 张图片, 0 个链接)

使用JavaScript中的蹦床函数实现安全递归

来自[Charles Cheng](https://unsplash.com/@charlesc7?utm_source=medium&utm_medium=referral) 在 [Unsplash](https://unsplash.com?utm_source=medium&utm_medium=referral)

在 JavaScript 中使用递归是不安全的,请考虑使用蹦床函数。它将递归转化为 while 循环去绕过 JavaScript 的限制,目的是为了防止溢出。

一个典型的递归函数就是阶乘计算。我们调用 factorial 函数 n 次来得到一个结果。每次调用都会向调用的堆栈添加一个 factorial 函数。

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

console.log(factorial(5)); // 120
复制代码

JavaScript 中的递归通常是代码出现问题的象征,通常应该避免使用。因为 JavaScript 是一种基于堆栈的语言,但目前没有尾调用优化。如果你运行了以下代码,将会报错 RangeError: Maximum call stack size exceeded,意思是超过最大调用堆栈大小。

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

recursiveFn(100000); // RangeError: Maximum call stack size exceeded
复制代码

不过,也有需要使用递归函数的情况。例如,遍历 DOM 树或其他的树形结构。

function traverseDOM(tree) {
  if (isLeaf(tree)) tree.className = 'leaf';
  else for (const leaf of tree.childNodes) traverseDOM(leaf);
}
复制代码

蹦床函数 —— JavaScript中的安全递归方式

使用 蹦床函数,你可以将递归函数转化为 while 循环:

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

    while (typeof result === 'function') result = result();

    return result;
  };
}
复制代码

让我们用 蹦床函数 去重写一个 阶乘 函数。我们需要去:

  1. 在基本情况下返回一个值。
  2. 在其他情况下返回要调用的函数。

我们还为 _factorial 的内部实现添加了累加器参数。

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

console.log(factorial(5));
复制代码

recursiveFn 可以像 factorial一样被重写,但我们不需要累加器去跟踪状态。这个实现方式甚至可以安全的运行数百万次的迭代。

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

recursiveFn(100000);
console.log('No range error!');
复制代码

下一次你想使用递归的时候,试试 蹦床函数 吧!

你可以尝试 蹦床函数 在这里 CodePen


蹦床函数并不是一种流行的技术。即使在 ramda 和 lodash 中,也没有提供蹦床函数。

感谢 Kyle Simpson 为我提供了蹦床函数的灵感。

如果发现译文存在错误或其他需要改进的地方,欢迎到 掘金翻译计划 对译文进行修改并 PR,也可获得相应奖励积分。文章开头的 本文永久链接 即为本文在 GitHub 上的 MarkDown 链接。


掘金翻译计划 是一个翻译优质互联网技术文章的社区,文章来源为 掘金 上的英文分享文章。内容覆盖 AndroidiOS前端后端区块链产品设计人工智能等领域,想要查看更多优质译文请持续关注 掘金翻译计划官方微博知乎专栏

more_vert