Я пытаюсь понять хвостовую рекурсию в Хаскеле. Я думаю, что понимаю, что это такое и как это работает, но я хотел бы убедиться, что я не все испортил.

Вот «стандартное» факториальное определение:

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 раза. Но у него нет проблемы с тем, чтобы по-прежнему приходиться «возвращаться» для вычисления умножения всех результатов, поскольку я уже передаю результат в качестве аргумента функции.

Это, насколько я понял, что такое Tail Recursion. Теперь он кажется немного лучше, чем первый, но вы все равно можете легко переполняться стеками. Я слышал, что компилятор Haskell преобразует функции Tail-Recursive в циклы for за кулисами. Я предполагаю, что это является причиной, почему стоит выполнять хвостовые рекурсивные функции?

Если это и есть причина, то нет никакой необходимости пытаться сделать функции хвостовыми рекурсивными, если компилятор не собирается делать этот умный трюк - я прав? Например, хотя в теории компилятор C # мог обнаруживать и преобразовывать хвостовые рекурсивные функции в циклы, я знаю (по крайней мере, то, что я слышал), что в настоящее время он этого не делает. Таким образом, в настоящее время абсолютно бессмысленно делать функции хвостовыми рекурсивными. Это оно?

Спасибо!