На днях сёрфил глобальное пространство в поисках полезных вещей и наткнулся на статью, которая мне показалась в высшей степени замечательной. Такие вещи как рекурсия и продолжения (continuations) далеко не самые простые вещи в программировании, но вместе с ней мы с вами сможем сделать ещё один шаг в их понимании.
Материал достаточно объемный, поэтому будет разбит на несколько частей. В этой части немного о рекурсии и TCO (tail-call optimization) Ссылка на источник в конце заметки.
Вторая часть
Заключительная часть
__________________________________________________________________________________________
Чем хвостовая рекурсия отличается от обычной? Какое отношение к этому имеют продолжения, что такое CPS, и как нам помогут трамплины? Это вводная статья с примерами на Python и Clojure.
Рекурсия и хвостовая рекурсия
Вот классическая реализация рекурсивного вычисления факториала на Python:
Рекурсия будет "хвостовой", если рекурсивный вызов будет последним действием функции перед возвратом результата. (т.е. находится в "хвосте" функции). Вот версия факториала с хвостовой рекурсией:
Хвостовой вызов не обязательно должен быть рекурсивным, он может вызывать другую функцию, выполнять взаимную рекурсию или какую-нибудь более сложную схему. Каноничным примером взаимной рекурсии является достаточно глупый способ вычислить четное или нечетное входное число:
Все вызовы функций находятся в хвостовой позиции.
Оба этих примера очень просты, потому что содержат только один вызов в каждой функции. Всё становится более сложным, когда функция должна сделать множественные вызовы. Хороший пример - вычисление числа Фибоначчи:
У нас есть 2 рекурсивных вызова fib_rec. Преобразовать эту функцию к хвостовому варианту будет сложнее. Первая попытка:
Последнее действие функции fib_almost_tail - рекурсивный вызов. У нас получилось? Нет, т.к. есть ещё один вызов fib_almost_tail и он не в хвостовой позиции. Более продуманная попытка:
Заметьте, что это преобразование было сложнее чем для факториала. Оно гораздо менее очевидно и нам даже пришлось изменить количество вызовов (один вместо двух как в оригинальной fib_rec). Очевидный вывод - это сложно, оставить только один хвостовой вызов в функции с множественными вызовами.
Взрыв стека
Рекурсивные решения стремятся быть краткими и элегантными. Однако они несут в себе опасность - возможность "взорвать" стек во время выполнения. В Python глубина стека по умолчанию - 1000. Если мы попробуем fact_rec как показано в терминале, в ответ получим:
"Кому нужно высчитывать факториал 1000?" - вопрос логичный. Однако, если используются многочисленные рекурсивные вызовы, вы столкнетесь с проблемами гораздо раньше. Например, при подсчете 50 числа Фибоначчи с помощью fib_rec вам придется очень долго ждать выполнения, хотя запрос кажется не самым серьезным. Причина - экспоненциальная сложность простой реализации.
Функция fib_tail не страдает от этих проблем, т.к. не имеет экспоненциально растущего дерева вызовов, но так же может взорвать вам стек, если будет вызвана для большого числа. Это же высказывание правдиво для fact_tail. Сама по себе хвостовая рекурсия не решает проблему переполнения стека. Нужен ещё один ингридиент, с которым мы коротко разберемся.
Решения: ТСО или преобразование к итерациям
Теперь, вместе с описанными в предыдущей секции проблемами вернемся к хвостовым вызовам. Зачем вообще стоит преобразовывать функции? Дело в том, что в некоторых языках компилятор может автоматически предотвратить наращивание стека, преобразовав хвостовой вызов в прыжок. Этот трюк называется оптимизацией хвостовой рекурсии (TCO: tail-call optimization). Язык программирования Scheme делает это с 1970. С тех же пор Scheme вдохновляет программистов писать рекурсивные алгоритмы, т.к. TCO - это ядро языка. Более молодые языки так же подхватили эту фишку - Lua, Javascript (как только ES6 станет де-факто универсальной версией).
Некоторые языки не поддерживают TCO. Например Python - Гвидо прямо заявляет, что TCO - это "unpythonic" и он не хочет этого. В конце этой статьи я объясню, почему это не такая уж и проблема для Python, как для других языков.
Для примера возьмем Clojure. Он построен на JVM и поэтому использует её семантику для вызовов (по крайней мере если нужно получить какую-то скорость). JVM не имеет полной поддержки TCO, но Clojure подходит к этой проблеме прагматично - он поощряет ручное преобразование TCO с помощью циклов.
Заметьте сходство между этим кодом и Python fib_tail показанным ранее. Это не совпадение! Как только вы преобразуете алгоритм к хвостовому вызову, вам будет очень легко пойти дальше и собрать из него цикл. Эсли бы это не было легко, компилятор не способен был бы делать такие операции уже 40 лет!
В качестве ориентира, fib_iterative на Python:
Немного более неловкая чем реализация на Clojure, но та же самая в сути. Поскольку хвостовой вызов переносит все состояния в аргументах, мы просто используем явные переменные и циклы.
Итеративное решение - наша главная цель. Оно избегает экспоненциального расширения алгоритма и взрыва стека. Единственная проблема - приходится делать преобразования самому. Красота автоматического TCO в том, что вы можете писать свои алгоритмы рекурсивно и получать скорость и характеристики итеративного подхода.
В этот момент вы можете спросить, как преобразовать непрямую/взаимную рекурсию к итеративному решения. Возьмем как пример определение четного/нечентного числа. Хоть это и не представляет проблем для компилятора, может быть достаточно сложным для программиста. Мы дойдем до разбора этого вопроса, когда подойдем к трамплинам.
Более реалистичные примеры
Перед более сложными главами я бы хотел показать чуть более реалистичную ситуацию с элегантным рекурсивным решением, сложно переписываемым на итеративное.
Возьмем сортировку слиянием. Реализация на Python:
В каком-то роде она всегда напоминает мне обратный обход дерева - мы рекурсивно идем влево,затем рекурсивно идем вправо и комбинируем результаты. Такие алгоритмы достаточно непросто преобразовываются в не рекурсивный код. Попробуйте! Возможно вы придете к эмуляции стека или какому-то принципиально новому алгоритму.
Сортировка слиянием - это пример множественной рекурсии, которую мы уже видели в примере с числом Фибоначчи. Другая распространенная проблема - непрямая рекурсия. Её мы видели в примере четный/нечетный.
Чтобы получить более реалистичный пример рассмотрим парсер рекурсивного спуска для этой грамматики
Весь код можно увидеть здесь (<- ссылка на гитхаб автора). parse_expr вызывает parse_term -> parse_term вызывает parse_fector -> parse_factor опять parse_expr. При сложном выражении стек будет содержать множество экземпляров каждой функции.
__________________________________________________________________________________________
На этом на сегодня все, такой вот клиффхэнгер. Что же случится с нашим героем? В следующих частях мы немного познакомимся с продолжениями, трамплином и в заключении будут упомянуты более естественные для Python инструменты решения задач.
Автор оригинала: Eli Bendersky's.
Спасибо за чтение, особенно нетерпеливые могут перейти по ссылке и прочитать всю статью в источнике)
Больше моих переводов и материалов можно найти здесь.
