您的位置:首页 » 分类: JavaScript & 实用函数方法 » 文章: JavaScript 中的递归和尾调用

JavaScript 中的递归和尾调用

小编推荐:掘金是一个高质量的技术社区,从 ECMAScript 6 到 Vue.js,性能优化到开源类库,让你不错过前端开发的每一个技术干货。各大应用市场搜索「掘金」即可下载APP,技术干货尽在掌握..

如果你已经有一段时间的 JavaScript 开发经验,你很有可能会遇到递回这个定义,给定一个数字来阶乘,n! = n * (n - 1) * ... * 1 就是一个标准的递回例子。

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

上面所示的例子是阶乘函数最简单的实现。

为了更加完整的理解,我们来看看当 n = 6 时是如何运行的:

  • factorial(6)
    • 6 * factorial(5)
    • 5 * factorial (4)
      • 4 * factorial(3)
      • 3 * factorial(2)
        • 2 * factorial(1)
        • 1 * factorial(0)
          • 1
        • (恢复先前的执行) 1 * 1 = 1
        • (恢复…) 2 * 1 = 2
      • (…) 3 * 2 = 6
      • … 4 * 6 = 24
    • 5 * 24 = 120
    • 6 * 120 = 720
  • factorial(6) = 720

现在,我们必须非常小心的去了解发生了什么事,所以我们可以明白接下来会发生什么。

当我们调用一个函数时,会发生许多事。调用函数后必须保存返回的位置,以及当前的信息(即 n的值)。然后为新函数分配内存空间,并产生一个新的 frame(栈帧) 。

这是继续下去,我们继续堆叠这些 frame(栈帧),然后我们释放堆栈,用它们返回的值替换函数调用。

要注意的另一件事是,我们的 function 处理过程中产生的的形状。如果我将此形状叫做递归,您可能不会感到惊讶。因此,我们有一个递归过程。

我们来看看这个函数的第二个实现

function factorial(n, res) {
    if (n === 0) {
        return res;
    }
    return factorial(n - 1, res * n);
}

我们可以通过定义一个内部函数来进一步封装功能。

function factorial(n) {
    function inner_factorial(n, res) {
        if (n === 0) {
            return res;
        }
        return inner_factorial(n - 1, res * n);
    }
    return inner_factorial(n, 1);
}

让我们看一下它是如何执行的:

  • factorial(6)
    • 使用 (n = 6, res = 1) 调用内部匿名函数 (iaf)
    • iaf(5, 1 * 6)
      • iaf(4, 6 * 5)
      • iaf(3, 30 * 4)
        • iaf(2, 120 * 3)
        • iaf(1, 360 * 2)
          • iaf(0, 720)
          • 720
          • 720
        • 720
        • 720
      • 720
      • 720
    • 720
    • iaf (6, 1) = 720
  • factorial(6) = 720

您可能会注意到,展开堆栈后,我们不需要执行任何计算。我们只是返回一个值。但是,按照我们的规则,我们不得不将 state 储存为 frame(栈帧),即使它在这个中 chain 最后没有被任何的使用。

然而,我们的规则并不适用于所有语言。实际上,在 Scheme 中,这样的 chain 必须通过尾调用优化。这确保我们的 stack 不会被不必要的 frame(栈帧)填充。因此,我们先前的计算会看到这种方式︰

  • factorial(6)
  • iaf(6, 1)
  • iaf(5, 6)
  • iaf(4, 30)
  • iaf(3, 120)
  • iaf(2, 360)
  • iaf(1, 720)
  • iaf(0, 720)
  • 720

实上,看起来实在很像:

res = 1;
n = 6;

while(n > 1) {
    res = res * n;
    n--;
}

意思是,我们确实有一个反覆运算的处理,即使我们使用递归。这是多么酷啊?

好消息是 ES6 的 feature。只要你在尾递归调用,而且你的函数是 strict(严格) 模式,尾调用优化将储存并且踢除 maximum stack size exceeded 错误。

英文原文:http://www.jstips.co/en/javascript/recursion-iteration-and-tail-calls-in-js/

正文完。下面还有一个推广让最好的人才遇见更好的机会!

互联网行业的年轻人,他们面对着怎样的职业瓶颈、困惑与未来选择?过去,这鲜有人关心。资深的职场人,也多半优先选择熟人去推荐机会。

100offer致力于改变现状,帮互联网行业最好的人才发现更好的机会。使用 100offer.com 或 100offer App ,可以一周内获得中国、美国等数千家优质企业的工作机会。

马上去遇见更好的机会
推广结束

关注WEB前端开发官方公众号

关注国内外最新最好的前端开发技术干货,获取最新前端开发资讯,致力于打造高质量的前端技术分享公众号

发表评论

电子邮件地址不会被公开。 必填项已用*标注