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

Question

Так что недавно я столкнулся с вопросом о том, что мне нужно написать код, где сам обратный вызов вызывает и так далее, и задался вопросом о NodeJS и поддержке tail-call, поэтому я нашел этот ответ /questions/7907762/optimizatsiya-hvostovogo-vyizova-nodejs-vozmozhno-ili-net/7907771#7907771 говорящий, что да, он поддерживается,

Итак, я попробовал это с этим простым кодом:

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

fac(5);

Используя Node 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 не заполняется бесполезно вызывает пока функция ссылается на себя в ответ.

Answer 1

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

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

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

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

Answer 2

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

Однако последнее действие вашего кода 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

Я не уверен, что у вашей рекурсивной функции есть хвостовой вызов. Может быть, вы можете попробовать следующее;

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