Я пытаюсь понять хвостовую рекурсию в Haskell. Я думаю, что понимаю, что это такое и как это работает, но я хотел бы убедиться, что я не испорчен.
Вот "стандартное" факториальное определение:
factorial 1 = 1
factorial k = k * factorial (k-1)
При запуске, например, factorial 3, моя функция вызовет себя 3 раза (дайте или возьмите). Это может создать проблему, если я захочу рассчитать фактор 99999999, поскольку у меня может быть переполнение стека. После того, как я доберусь до factorial 1 = 1, мне придется "вернуться" в стек и умножить все значения, поэтому у меня есть 6 операций (3 для вызова самой функции и 3 для умножения значений).
Теперь я представляю вам еще одну возможную факториальную реализацию:
factorial 1 c = c
factorial k c = factorial (k-1) (c*k)
Этот тоже рекурсивный. Он будет называть себя 3 раза. Но у него нет проблемы с тем, что все еще нужно "возвращаться" для вычисления умножений всех результатов, поскольку я уже передаю результат как аргумент функции.
Это то, что я понял, о том, что такое репликация хвоста. Теперь это кажется немного лучше первого, но вы все равно можете переполнять стек так же легко. Я слышал, что компилятор Haskell будет преобразовывать функции Tail-Recursive в циклы за кулисами. Наверное, это причина, по которой он рассчитывает выполнять хвостовые рекурсивные функции?
Если это причина, то абсолютно нет необходимости пытаться сделать функции tail рекурсивными, если компилятор не собирается делать этот умный трюк - я прав? Например, хотя теоретически компилятор С# мог обнаруживать и преобразовывать хвостовые рекурсивные функции в циклы, я знаю (по крайней мере, это то, что я слышал), что в настоящее время он этого не делает. Таким образом, в настоящее время нет абсолютно никакого смысла в создании рекурсивных функций. Это так?
Спасибо!
