4

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

function foo(x, acc) {
  if (x < 2) {
    return acc;
  }
  return foo(x - 1, acc * x);
}
foo(100000, 1); // Maximum call stack size exceeded
2
  • 3
    а кто-то гарантирует оптимизацию хвостовой рекурсии в javascript?
    – Grundy
    2 авг 2016 в 11:01
  • да даже если была бы, все равно return нужен на вызов foo в конце 2 авг 2016 в 11:14

3 ответа 3

3

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

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);
}
5
  • Поясни хоть ты мне, для нее нужно добавить return - так в примере ТС оно есть.. Где тут добавлено return? 2 авг 2016 в 11:40
  • Да он поправил уже 2 авг 2016 в 11:41
  • @VladimirGamalian аааа. а то я сижу кукую и не понимаю ответов 2 авг 2016 в 11:41
  • @АлексейШиманский, ага, можно просто список редакций глянуть :)
    – Grundy
    2 авг 2016 в 11:43
  • @АлексейШиманский просто нам нужно было как-то наполнять ответ, вот и делаем вид, что не видели правок ) 2 авг 2016 в 11:45
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 и без этого пережевал.

12
  • возможно в браузерах либо еще не реализовано, либо не во всех
    – Grundy
    2 авг 2016 в 11:23
  • @Grundy es6 все равно бабелить перед продакшном, так что наверное ок все 2 авг 2016 в 11:24
  • @VladimirGamalian, во первых не все возможно адекватно "забабелить". Это - нельзя Во вторых, я стандарт щас прочитал, оптимизация рекурсии strict mode толкьо должно работать. 2 авг 2016 в 11:26
  • @VladimirGamalian я что-то не вижу разницы с примером ТС. почему у него не работает, а тут должно? 2 авг 2016 в 11:27
  • kangax.github.io/compat-table/es6 - tail call optimization. Почти никто не умеет 2 авг 2016 в 11:27
0

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

1
  • 1
    Бессмысленный ответ. @Kot и так знает что копится стек. Вопрос был почему js не преобразует рекурисю в цикл (в случае "хвостовой рекурсии" это вполне возможно, и делается во многих языках, автоматически, на уровне компилятора или интерпретатора). Более того, с недавнего времени, это должно поддерживаться и в js.
    – Arnial
    2 авг 2016 в 12:51

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.