NodeJS中的尾递归 [英] Tail recursion in NodeJS

问题描述

所以我最近遇到过这样的情况：我需要编写回调调用自身的代码等等，并且想知道NodeJS和尾调用支持，所以我找到了这个答案https://stackoverflow.com/a/30369729 说是的，支持。

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

 use strict; 
 function fac（n）{
 if（n == 1）{
 console.trace（）; 
返回1; 
} 
返回n * fac（n-1）; 
} 
 
 fac（5）; 
  

在Linux x64上使用节点6.9.2并将其作为节点尾部调用运行。 js --harmony --harmony_tailcalls --use-strict
，结果是：

 跟踪
 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。< ;匿名> （/home/tailcall.js:10:1）
在Module._compile（module.js：570：32）
 at Object.Module._extensions..js（module.js：579：10） ）Module.load的
（module.js：487：32）在tryModuleLoad的
（module.js：446：12）
  

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

NodeJS / JavaScript支持尾递归？
或者我真的必须使用发电机和产量，但问题是我的回调会非常异步并且我无论如何都不会使用返回值，我只需要确保callstack没有当函数引用自身作为回报时，无用地填充调用。

解决方案

首先，如果您的实际案例是您关注的话当一个函数从异步回调调用自身时，那么你可能还没有任何堆栈堆积。

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

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

  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（param）; 
} else {
 / /表示所有通话完成
 progressCallback（null，null）; 
} 
}）; 
} 
 run（startParam）; 
} 
  

先前调用 run（）已经返回并且堆栈已完全展开，所以虽然这看起来像递归，但没有堆栈累积。

---

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

< pre class =snippet-code-js lang-js prettyprint-override> function fac（n）{var total = 1; while（n> 1）{total * = n--; } return total;} //在snippetfor中运行demo（var i = 1; i< = 10; i ++）{console.log（i，fac（i））}

So I recently came across case I needed to write code where callback calls itself and so on and wondered about NodeJS and tail-call support, so I found this answer https://stackoverflow.com/a/30369729 saying that yup, it's supported.

So I tried it with this simple code:

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

fac(5);

Using Node 6.9.2 on Linux x64 and run it as node tailcall.js --harmony --harmony_tailcalls --use-strict and result was:

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)

Which clearly shows callstack gets filled with calls and tail-recursion isn't supported although I use latest NodeJS.

Does NodeJS/JavaScript support tail-recursion at all? Or do I really have to go with generators and yields, but problem here is my callbacks are gonna be heavily asynchronous and I'm not gonna work with return value anyway, I just need to make sure the callstack doesn't get uselessly filled with calls while function refers to itself in return.

解决方案

First off, if your actual case you're concerned about is when a function calls itself from an async callback, then you likely don't have any stack buildup there anyway.

That's because the original function has already returned and the whole stack unwound before the async callback gets called, so though it visually looks like recursion, there is no stack build up.

Here's a simple code example of making multiple sequenced network requests where a function calls itself from an async callback and there is no stack buildup.

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);
}

The prior invocation of run() has already returned and the stack has completely unwound before the async callback is called so while this visually looks like recursion, there is no stack buildup.

---

In the specific code you show, you can avoid the recursion entirely by rewriting using a while loop which would work efficiently in any version of 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中的尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！