Вопрос о статье «Оптимизация хвостового звонка»

Question

У меня есть вопрос относительно это статья.

Между этим кодом

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

и этот код

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) Я не понимаю, насколько это помогает. У второго фрагмента просто есть хвостовой звонок, который создает меньше накладных расходов, потому что он вычисляет то, что ему нужно, прежде чем он снова вызовет себя, или есть что -то большее, что мне не хватает?

Насколько я понимаю, хвостовой вызов все еще не устранен, просто оптимизирован.

2) и почему должно быть odds а также odds1 тем не мение? Мне все еще не ясно.

Answer 1

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

Насколько я понимаю, хвостовой вызов все еще не устранен, просто оптимизирован.

Если конец процедуры выглядит так:

push args
call foo
return

Тогда компилятор может оптимизировать это, чтобы просто

jump startOfFoo

Устранение процедуры вызов полностью.

И почему все равно должны быть шансы и шансы1? Мне все еще не ясно.

«Контракт» odds Указывает только два аргумента - третий аргумент - это просто деталь реализации. Таким образом, вы скрываете это внутренним методом и представляете «обертку» в качестве внешнего API.

Вы могли бы позвонить odds1 что-то типа oddsImpl И я думаю, что это сделало бы это яснее.

Answer 2

Первая версия не хвост рекурсив потому что после получения ценности odds(n - 1, p - 1) он должен тогда умножить его на (n / p), вторая версия перемещает это в расчет параметров для odds1 Функция, чтобы сделать его должным образом хвостом рекурсивным.

Если вы посмотрите на стек вызовов, то первые пойдут так:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

тогда как второй будет:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

Поскольку вы просто возвращаете значение рекурсивного вызова, компилятор может легко оптимизировать это:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

Причина иметь odds а также odds1 это просто для предоставления начального значения аккумулятора, когда другой код вызывает эту функцию.

Answer 3

Оптимизация хвостовой рекурсии заключается в следующем, в первом примере, поскольку вы не можете рассчитать результат умножения return (n / p) * odds(n - 1, p - 1) До тех пор, пока вы не назвали шансы (N-1), интерперитор должен удерживать нашу текущую позицию в памяти (в стеке) и открыть новый вызов.

Рекурсивно это произойдет и в следующем звонке, а также в том, что после него и так далее. Таким образом, к тому времени, когда мы достигнем конца нашей рекурсии, у нас есть N, и начинаем возвращать значения и рассчитывать продукты.

Во втором примере, поскольку выполненная оператор возврата просто return odds1(n - 1, p - 1, (n / p) * acc) Мы можем рассчитать аргументы функции и просто вызвать SADES1 (N-1) не удерживая нашу нынешнюю позицию. Анкет Вот где оптимизация, потому что теперь мне не нужно помнить, где я каждый раз, когда я открываю новый кадр в стеке.

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

1. соль
2. ингредиенты на следующей странице

На следующей странице есть

1. перец
2. ингредиенты на следующей странице

и т.д. Как сказать, что такое все ингредиенты? Вы должны вспомнить, что вы видели на каждой странице!

Хотя второй пример больше похож на следующий список ингредиентов:

1. соль
2. Забудьте об этом, просто используйте то, что вы видите на следующей странице

На следующей странице есть:

1. соль
2. перец
3. Забудьте об этом, просто используйте то, что вы видите на следующей странице

и т. д. К тому времени, когда вы достигнете последней страницы (обратите внимание, что аналогия точна в том, что оба принимают одинаковое количество вызовов функций), у вас есть все ингредиенты, без необходимости «держать в памяти» то, что вы видели на каждой странице, Потому что это все на последней странице!