NodeJS中的尾递归

Question

所以我最近遇到的情况我需要编写回调调用自己的代码等等,并想知道NodeJS和尾调用支持,所以我发现这个答案/sf/answers/2125881061/说是的,它支持.

所以我尝试使用这个简单的代码:

"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)

这清楚地表明callstack充满了调用,虽然我使用最新的NodeJS,但不支持尾递归.

NodeJS/JavaScript是否支持尾递归？或者我真的必须使用生成器和产量,但问题是我的回调将是非常异步的,无论如何我都不会使用返回值,我只需要确保callstack不会无用地填充函数引用自身作为回报.

Answer 1

你有什么不是尾巴调用.尾调用是作为另一个函数的最终动作执行的函数调用.除了函数调用自身之外,尾递归调用是相同的.

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

您可以做的是在此之前计算此信息的步骤:

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的堆栈跟踪: