Рекурсивные функции, переполнение стека и Y-комбинаторы

Question

У меня есть рекурсивная функция (на C #), которую мне нужно вызвать около 800 миллионов раз;это, очевидно, обычно приводит к переполнению стека примерно после 900-го вызова.Я использовал это в нескольких циклах, но рекурсивный шаблон намного проще и чище в обслуживании.

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

Есть ли у кого-нибудь опыт использования y-комбинатора?Я все еще застряну в переполнении стека?

Рассмотрим простой пример факториала.Факториал для большинства чисел больше 5000 вызовет переполнение стека.Если бы я правильно использовал y-комбинатор в этом сценарии, исправило бы это переполнение стека?

Это не кажется тривиальным в реализации, поэтому я хочу подтвердить это, прежде чем потратить усилия / ресурсы на разработку и изучение y-комбинатора.

Answer 1

Нет, использование Y-комбинатора не поможет в вашей ситуации.Если вам нужно сделать что-то 800 миллионов раз, вы можете (а) выполнить рекурсию или (б) выполнить цикл (или, я полагаю, (в) написать 800 миллионов вызовов вашей функции).Поскольку Y-комбинатор не зацикливается, он должен проходить рекурсию.

Цикл - это то, что вы ищете, если только вы не используете среду выполнения, которая предлагает правильную хвостовую рекурсию (например, Scheme).

Тем не менее, реализация Y-комбинатора с нуля на выбранном вами языке - отличное упражнение.

Answer 2

Комбинаторы Y полезны, но я думаю, вам действительно нужна оптимизация хвостовой рекурсии , которая исключает использование стека для хвостовых рекурсивных функций.Хвостовая рекурсия возможна только тогда, когда результат каждого рекурсивного вызова немедленно возвращается вызывающей стороной и никогда не требует дополнительных вычислений после вызова.К сожалению, C # не поддерживает оптимизацию хвостовой рекурсии, однако вы можете эмулировать ее с помощью трамплина , который позволяет выполнить простое преобразование из метода хвостовой рекурсии в метод, обернутый в трамплин.

родовое слово

Answer 3

Вы можете использовать батут, как в Reactive Extension, я попытался объяснить это в своем блоге http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Одно из решений - преобразовать ваши функции для использования цикла и явной структуры данных context . Контекст представляет собой то, что люди обычно называют стеком вызовов. Вы можете найти мой ответ на другой вопрос о преобразовании в хвостовую рекурсию полезно. Соответствующие шаги от 1 до 5; 6 и 7 относятся к этой конкретной функции, тогда как ваша кажется более сложной.

Однако "простой" альтернативой является добавление счетчика глубины к каждой из ваших функций; когда он достигает некоторого предела (определяемого экспериментально), порождает новый поток для продолжения рекурсии с новым стеком. Старый поток блокируется, ожидая, пока новый поток отправит ему результат (или, если хотите, результат или исключение для повторного вызова). Счетчик глубины возвращается к 0 для новой резьбы; когда он достигнет предела, создайте третий поток и так далее. Если вы кэшируете потоки, чтобы не оплачивать затраты на создание потока чаще, чем необходимо, надеюсь, вы получите приемлемую производительность без необходимости радикальной реструктуризации вашей программы.