Хвостовая рекурсия в NodeJS

Question

Хвостовая рекурсия в NodeJS

Так что я недавно наткнулся на случай, когда мне нужно было написать код, где callback вызывает себя и так далее, и задавался вопросом о NodeJS и поддержке tail-call, поэтому я нашел этот ответ https://stackoverflow.com/a/30369729 говоря, что да, это поддерживается.

Поэтому я попробовал использовать этот простой код:

"use strict";

function fac(n){

    if(n==1){

        console.trace();

        return 1;

    }

    return n*fac(n-1);

}



fac(5);

Используя узел 6.9.2 на Linux x64 и запустите его как 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 не будет бесполезно заполнен вызовами, в то время как функция ссылается на себя в ответ.

678 3

javascript node.js recursion tail-call-optimization

3 ответов:

Comments

Ничего не найдено.

jfriend00 · Accepted Answer · 2017-01-16 01:19:12

Во-первых, если ваш фактический случай, о котором вы беспокоитесь, - это когда функция вызывает себя из асинхронного обратного вызова, то у вас, вероятно, нет никакого накопления стека в любом случае.

Это потому, что исходная функция уже возвращена и весь стек размотан до вызова асинхронного обратного вызова, поэтому, хотя это визуально выглядит как рекурсия, нет никакого построения стека.

Вот простой пример кода для выполнения нескольких последовательных сетевых запросов, когда функция вызывает сам по себе от асинхронного обратного вызова и нет никакого наращивания стека.
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))
}

nem035 · Accepted Answer · 2017-01-19 21:15:19

То, что у вас есть, не является хвостовым звонком. Хвостовой вызов-это вызов функции, выполняемый какконечное действие другой функции. Хвостовой рекурсивный вызов является тем же самым, за исключением вызова самой функции.
Однако конечным действием вашего кода будет 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);
}
Вот stacktrace из Chrome Canary:

Redu · Accepted Answer · 2017-01-16 00:22:47

Я не уверен, что ваша рекурсивная функция имеет хвостовой вызов. Может быть, вы можете попробовать следующее;
"use strict";
var fac = (n, r = 1) => n === 1 ? r : (r *= n, fac(n-1,r));
console.log(fac(5));