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

#javascript #рекурсия

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

function foo(x, acc) {
  if (x < 2) {
    return acc;
  }
  return foo(x - 1, acc * x);
}
foo(100000, 1); // Maximum call stack size exceeded

    

Ответы

Ответ 1

Стандарт содержит следующее упоминание


  Tail Position calls are only defined in strict mode code because of a common non-standard
language extension (see 9.2.7) that enables observation of the chain of caller contexts.





  Хвостовые вызовы могут быть определены только в strict mode, из-за нестандартного
расширения языка (см 9.2.7), которое позволяет следить за цепочкой вызываемых контекстов.


Таким образом в соответствии со стандартом, хвостая рекурсия в строгом режиме будет
обработана правильно.

Поддерживаемость на данный момент оставляет желать лучшего



Ну и да, как уже упоминалось: в примере в вопросе не хвостовая рекурсия, для нее
нужно добавить return, а так же указать strict mode, в итоге код должен принять следующий вид

function foo(x, acc) {
  'use strict'
  if (x < 2) {
    return acc;
  }
  return foo(x - 1, acc * x);
}


Ответ 2

В ES5 не обещали, но в ES6 уже сработает (см. поддержку браузеров в соседнем ответе,
если коротко - нет поддержки):

function foo(x, acc) {
  "use strict";
  if (x < 2) {
    return acc;
  }
  return foo(x - 1, acc * x);
}

console.log(foo(10000000, 1));


(с добавлением return к хвостовому вызову foo)

Пример рабочий:
http://www.es6fiddle.net/irddgyju/

babel превратил этот код в:

function foo(_x, _x2) {
  var _again = true;

  _function: while (_again) {
    var x = _x,
        acc = _x2;
    _again = false;

    if (x < 2) {
      return acc;
    }
    _x = x - 1;
    _x2 = acc * x;
    _again = true;
    continue _function;
  }
}


По стандарту "use strict" обязателен в этом случае, хотя babel и без этого пережевал.


Ответ 3

Возможно не дам ответ на вопрос, но постараюсь натолкнуть на мысль. Добавьте вывод
в консоль console.log(acc); после foo(x - 1, acc * x); и посмотрите какой будет результат
и сколько такой скрипт будет отрабатывать. Уже при foo(10000, 1); в консоли вы увидите
что acc = Infinity, а скрипт будет работать более 2 минут, а при foo(100000, 1); Вы
получите ошибку "Maximum call stack size exceeded".