вспомнилось, как в одном из заданий ШАДа меня заставили показать, что (один, конкретный) катаморфизм на бинарных деревьях можно написать с использованием O(log n) памяти в стеке. Я там опёрся на оптимизацию хвостовой рекурсии и делал первый рекурсивный вызов в ту ветку, у которой высота меньше. Такие дела.
7 comments
recommend
bookmark
subscribe
Я ТВОЙ РЕКУРСИЯ
@
ХВОСТ В СТЕКЕ ОПТИМИЗИРОВАЛ
Только хвостовые же!
таки да. Но достаточно умный компилятор может преобразовать даже не-хвостовую рекурсию в итеративный алгоритм :cf:
Фибоначчи мне разверни в цикл, Улидтко :3
Хотя с мемоизацией можно, вполне ня будет.
вспомнилось, как в одном из заданий ШАДа меня заставили показать, что (один, конкретный) катаморфизм на бинарных деревьях можно написать с использованием O(log n) памяти в стеке. Я там опёрся на оптимизацию хвостовой рекурсии и делал первый рекурсивный вызов в ту ветку, у которой высота меньше. Такие дела.
Хм, мне кажется, или так же можно какой-нибудь qsort оптимизировать до использования O(log n) памяти стека?
конечно