#recursion #functional-programming #f# #tail-recursion #biginsight-examples
#рекурсия #функциональное программирование #f# #хвостовая рекурсия #biginsight-примеры
Вопрос:
Разработчикам программного обеспечения на функциональных языках программирования сказали, что хвостовые рекурсивные вызовы лучше, чем нерекурсивные. Классическим примером в учебниках является хвостовая рекурсивная факториальная функция (написанная на F #)
let rec faci n r =
if n = 0 then r else faci (n-1) (r * n)
по сравнению с его нерекурсивной контрчастью.
let rec facr n =
if n = 0 then 1 else n * facr(n-1)
Относительно ясно, что faci above не нуждается в дополнительном фрейме стека при вызове самого себя, как facr это было бы. Но я ищу более яркий пример, предпочтительный в F #, из которого можно продемонстрировать, почему хвостовые рекурсивные функции лучше, чем нерекурсивные. В идеале улучшение можно визуализировать, например, с помощью профилировщика памяти или путем печати некоторой отладочной информации. Есть идеи о таком примере?
Комментарии:
1. Хвостовая рекурсия зависит от аккумулятора. Если накопитель представляет собой всего лишь одно вычисленное значение, как в вашем примере, хвостовая рекурсия требует меньше памяти. Однако, если он накапливает результат каждого рекурсивного шага без потери информации (например, в списке), вы, по сути, обмениваете стек вызовов на кучу. Тем не менее, это может быть более эффективным для памяти.
2. Полезно это знать. Спасибо!
3. tbh, это может быть не так просто, как вы думаете. Например, некоторые хвостовые вызовы будут оптимизированы компилятором в цикл. Рекурсивные функции лучше, только если они хвостовые рекурсивные, иначе они съедят ваш стек на обед.
4. Я бы согласился с вышесказанным, я бы продемонстрировал это, продемонстрировав факториал с использованием цикла (в C #), а затем факториал рекурсивно.