NodeJS 中的尾递归

Question

所以我最近遇到了一个案例，我需要编写回调调用自身的代码等等，并且想知道 NodeJS 和尾调用支持，所以我找到了这个答案说是的，它受支持。

所以我用这个简单的代码试了一下：

"use strict";
function fac(n){
    if(n==1){
        console.trace();
        return 1;
    }
    return n*fac(n-1);
}

fac(5);

在 Linux x64 和运行上使用 Node 6.9.2 作为 node tailcall.js --harmony --harmony_tailcalls --use-strict 结果是：

Trace
    at fac (/home/tailcall.js:4:11)
    at fac (/home/tailcall.js:7:11)
    at fac (/home/tailcall.js:7:11)
    at fac (/home/tailcall.js:7:11)
    at fac (/home/tailcall.js:7:11)
    at Object.<anonymous> (/home/tailcall.js:10:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)

虽然我使用最新的 NodeJS，但它清楚地表明调用堆栈充满了调用并且不支持尾递归。

NodeJS/JavaScript 完全支持尾递归吗？还是我真的必须使用生成器和收益，但这里的问题是我的回调将是高度异步的，无论如何我都不会使用 return 值，我只需要确保调用堆栈不会当函数在 return.

中引用自身时，会无用地充满调用

Answer 1

我不确定你的递归函数是否有尾调用。也许您可以尝试以下方法；

"use strict";
var fac = (n, r = 1) => n === 1 ? r : (r *= n, fac(n-1,r));
console.log(fac(5));

Answer 2

你那里没有 tail-call。尾调用是作为另一个函数的最终操作执行的函数调用。 tail-recursive 调用是相同的，除了函数调用自身。

但是，您的代码的最终操作是 n*fac(n-1)，而不是 fac(n-1)。这不是递归尾调用，因为当前堆栈在计算递归调用时仍需要记住 n，以便它知道要乘以哪些数字。

您可以做的是在前 1 步计算此信息：

const fac = (n, result = 1) =>
  n === 1
    ? result
    : fac(n - 1, n * result);

console.log(fac(5)); // 120

或者根据您的代码：

function fac(n, result = 1) {
  // base case
  if (n === 1) {
    return result;
  }

  // compute the next result in the current stack frame
  const next = n * result;

  // propagate this result through tail-recursive calls
  return fac(n - 1, next);
}

这是来自 Chrome Canary 的堆栈跟踪：

Answer 3

首先，如果您关心的实际情况是某个函数从异步回调中调用自身，那么您可能在那里根本没有任何堆栈堆积。

那是因为在异步回调被调用之前，原始函数已经返回并且整个堆栈展开，所以虽然它在视觉上看起来像递归，但没有堆栈建立起来。

这是一个简单的代码示例，它发出多个有序的网络请求，其中一个函数从异步回调中调用自身并且没有堆栈堆积。

function getPages(baseURL, startParam, endParam, progressCallback) {

    function run(param) {
         request(baseURL + param, function(err, response, body) {
             if (err) return progressCallback(err);
             ++param;
             if (param < endParam) {
                 progressCallback(null, body);
                 // run another iteration
                 // there is no stack buildup with this call
                 run(param);
             } else {
                 // indicate completion of all calls
                 progressCallback(null, null);
             }
         });
    }
    run(startParam);
}

run() 的先前调用已经返回，并且在调用异步回调之前堆栈已完全展开，因此虽然这在视觉上看起来像递归，但没有堆栈堆积。

在您显示的特定代码中，您可以通过使用 while 循环重写来完全避免递归，该循环在任何版本的 Javascript:

中都可以有效地工作

function fac(n){
    var total = 1;
    while (n > 1) {
        total *= n--;
    }
    return total;
}

// run demo in snippet
for (var i = 1; i <= 10; i++) {
    console.log(i, fac(i))
}

NodeJS 中的尾递归

Tail recursion in NodeJS

javascript

node.js

recursion

tail-call-optimization