Вопрос к статье "Оптимизация вызовов в хвосте"

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

Первая версия не является хвостовой рекурсией , потому что после получения значения 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 2

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

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

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

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

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

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

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

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

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

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

следующая страница имеет:

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

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

Answer 3

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

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

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

push args
call foo
return

Тогда компилятор может оптимизировать это до

jump startOfFoo

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

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

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

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