Введение

Взаимная рекурсия

В математике и информатике взаимная рекурсия — это форма рекурсии, при которой два математических или вычислительных объекта, такие как функции или типы данных, определяются через друг друга. Взаимная рекурсия широко распространена в функциональном программировании и в некоторых областях, таких как рекурсивные нисходящие парсеры, где типы данных естественно определяются взаимно рекурсивно.

Функции компьютера

Точно так же, как алгоритмы для рекурсивных типов данных могут быть естественным образом представлены рекурсивными функциями, алгоритмы для взаимно рекурсивных структур данных могут быть естественным образом представлены взаимно рекурсивными функциями. Типичные примеры включают алгоритмы для деревьев и рекурсивные нисходящие парсеры. Как и в случае прямой рекурсии, оптимизация хвостового вызова необходима, если глубина рекурсии велика или не ограничена, например, при использовании взаимной рекурсии для многозадачности. Следует отметить, что оптимизация хвостового вызова в общем случае (когда вызываемая функция не совпадает с исходной функцией, как при хвостовой рекурсии) может быть сложнее в реализации, чем оптимизация хвостовой рекурсии как частного случая, и поэтому эффективная реализация взаимной хвостовой рекурсии может отсутствовать в языках, оптимизирующих только хвостовую рекурсию. В языках, таких как Паскаль, которые требуют объявления перед использованием, взаимно рекурсивные функции требуют предварительного объявления, поскольку при их определении невозможно избежать прямой ссылки. Как и в случае с непосредственно рекурсивными функциями, может быть полезна функция-обертка, в которой взаимно рекурсивные функции определяются как вложенные функции в ее области видимости, если это поддерживается. Это особенно полезно для обмена состоянием между набором функций без необходимости передачи параметров между ними.

Усовершенствованные примеры

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

Математические функции

В математике последовательности Хофштадтера «Женская» и «Мужская» являются примером пары целочисленных последовательностей, определенных рекурсивно по отношению друг к другу. Фракталы могут быть вычислены (до заданного разрешения) с помощью рекурсивных функций. Иногда это можно сделать более изящно, используя взаимно рекурсивные функции; кривая Серпинского – хороший тому пример.

Распространенность

Взаимная рекурсия очень распространена в функциональном программировании и часто используется в программах, написанных на LISP, Scheme, ML и подобных языках программирования. Например, Абельсон и Суссман описывают, как метациркулярный интерпретатор можно использовать для реализации LISP с циклом eval-apply. В таких языках, как Prolog, взаимная рекурсия почти неизбежна. Некоторые стили программирования не рекомендуют использовать взаимную рекурсию, утверждая, что может быть сложно отличить условия, которые вернут результат, от условий, которые приведут к бесконечному выполнению кода без получения результата. Питер Норвиг указывает на шаблон проектирования, который полностью исключает её использование, заявляя: text=Если у вас есть две взаимно рекурсивные функции, обе изменяющие состояние объекта, постарайтесь перенести почти всю функциональность в одну из них. В противном случае вы, скорее всего, в конечном итоге будете дублировать код.

Терминология

Взаимная рекурсия также известна как косвенная рекурсия, в отличие от прямой рекурсии, когда одна функция вызывает себя напрямую. Это просто разница в акценте, а не другое понятие: "косвенная рекурсия" подчеркивает отдельную функцию, в то время как "взаимная рекурсия" подчеркивает набор функций и не выделяет какую-либо отдельную функцию. Например, если функция f вызывает саму себя, это прямая рекурсия. Если же вместо этого f вызывает g, а затем g вызывает f, которая, в свою очередь, снова вызывает g, то с точки зрения только f, f косвенно рекурсирует, а с точки зрения только g, g косвенно рекурсирует, в то время как с точки зрения обоих, f и g взаимно рекурсируют друг на друга. Аналогично, набор из трех или более функций, которые вызывают друг друга, можно назвать набором взаимно рекурсивных функций.

Переход на прямой рекурсионный метод

Математически, множество взаимно рекурсивных функций является примитивно рекурсивным, что может быть доказано с помощью рекурсии по ходу значений, путем построения единственной функции F, которая перечисляет значения отдельных рекурсивных функций в порядке: и переписывает взаимную рекурсию как примитивную рекурсию. Любую взаимную рекурсию между двумя процедурами можно преобразовать в прямую рекурсию, встраивая код одной процедуры в другую. Если существует только одно место, где одна процедура вызывает другую, это просто, хотя при наличии нескольких таких мест это может привести к дублированию кода. С точки зрения стека вызовов, две взаимно рекурсивные процедуры создают стек ABABAB, а встраивание B в A приводит к прямой рекурсии (AB)(AB)(AB).

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