JavaScript中的递归、PTC、TCO和STC

正文

请到「今天看啥」查看全文

如果想了解更多关于递归的实践和有趣应用，请参考树和图相关算法的工作原理。

递归与调用栈

通常，在使用递归的时候，一般都会产生一个函数调用栈，其中每个函数都需要使用前一次自我调用的结果。

想要更好地理解调用栈的原理，或者如何看懂栈追踪信息， 请参考这篇文章。

为说明使用递归时的调用栈是什么样的，我们以简单的 factorial 函数作例子。

以下是它的代码：

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

    return n * factorial(n - 1)
}

接下来，我们调用它看看 3 的阶乘。

通过前面的例子我们知道， 3 的阶乘要计算 factorial(2) 、 factorial(1) 和 factorial(0) 并将它们的结果相乘。这意味着，要计算 3 的阶乘，需要额外调用3次 factorial 函数。

以上每次调用都会把一个新的栈帧推到调用栈上，而所有调用都进栈后的结果大致如下：

factorial(0) // The factorial of 0 is 1 by definition (base case)
factorial(1) // This call depends on factorial(0)
factorial(2) // This call depends on factorial(1)
factorial(3) // This first call depends on factorial(2)

现在，我们添加对 console.trace 的调用，以便调用 factorial 函数时在调用栈中看到当前的栈帧。

更改后的代码应该是这样的：

function factorial(n) {
    console.trace()
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

factorial(3) // Let's call the factorial function and see what happens

下面我们就来运行代码，分析打印出的每一段调用栈信息。

这是第一段：

Trace
    at factorial (repl:2:9)
    at repl:1:1 // Ignore everything below this line, it's just implementation details
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
    at emitOne (events.js:101:20)

看到了吧，第一个调用栈只包含对 factorial 函数的第一次调用，也就是 factorial(3) 。接下来就有意思了：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at repl:1:1 // Ignore everything below this line, it's just implementation details
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)

这次我们在上一次调用基础上又调用了 factorial 函数。这个调用是 factorial(2) 。

这是调用 factorial(1) 时的栈：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)

我们看到，这在之前调用的基础上又增加了一次调用。

最后是调用 factorial(0) 时的调用栈：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

正像我在本节开始时说的一样，调用 factorial(3) 需要进一步调用 factorial(2) 、 factorial(1) 和 factorial(0) 。这就是 factorial 函数在调用栈中现身4次的原因。

看到这里，读者应该注意到递归调用过多的问题了：调用栈会越来越大，最终可能导致 Stack Buffer Overflow 。只要栈达到容量上限，多一个调用就会造成溢出。

如果你想知道自己JavaScript运行环境中的栈有多少个帧，那我强烈推荐 Dr. Axel Rauschmayer（我是他的忠实粉丝）的方法。

请到「今天看啥」查看全文