Почему этот код вызывает переполнение стека?

Question

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

def factorial(n)
  (n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end

Почему следующее также вызывает переполнение?

def factorial(n, k)
  (n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end

Answer 1

Ваш второй алгоритм создает n длинную цепочку лямбда-процедур, каждая из которых содержит ссылку на предыдущую. Я не знаю точно, что делает Ruby, но на должном хвост-рекурсивном языке стек не будет переполнен в вашем втором алгоритме, потому что k.call в лямбде также находится в хвостовой позиции. Если, как показывает эксперимент Брайана, Ruby не имеет правильных хвостовых вызовов, n длинная цепочка вложенных вызовов лямбды переполнит стек, когда вызывается начало цепочки, даже несмотря на то, что Ruby достаточно умен для преобразования хвостовой рекурсивный вызов factorial в цикл (= оптимизация хвостового вызова).

Answer 2

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

Answer 3

По той же причине у первого переполнение стека ... Слишком большой стек вызовов.

Answer 4

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