Хвостовая рекурсия в Хаскеле
Я пытаюсь понять хвостовую рекурсию в Хаскеле. Я думаю, что понимаю, что это такое и как это работает, но я хотел бы убедиться, что я не все испортил.
Вот «стандартное» факториальное определение:
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 # мог обнаруживать и преобразовывать хвостовые рекурсивные функции в циклы, я знаю (по крайней мере, то, что я слышал), что в настоящее время он этого не делает. Таким образом, в настоящее время абсолютно бессмысленно делать функции хвостовыми рекурсивными. Это оно?
Спасибо!