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

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

Примеры

Типы данных

Наиболее важным базовым примером типа данных, который может быть определен посредством взаимной рекурсии, является дерево , которое может быть определено взаимно рекурсивно в терминах леса (списка деревьев). Символически:

f: [t[1], ..., t[k]]
t: v f

Лес f состоит из списка деревьев, а дерево t состоит из пары значения v и леса f (его потомков). Это определение элегантно, и с ним легко работать абстрактно (например, при доказательстве теорем о свойствах деревьев), поскольку оно выражает дерево в простых терминах: список одного типа и пара двух типов. Кроме того, он соответствует многим алгоритмам на деревьях, которые состоят из выполнения одного действия со значением и другого действия с дочерними элементами.

Это взаимно рекурсивное определение можно преобразовать в однократно рекурсивное определение, вставив определение леса:

t: v [t[1], ..., t[k]]

Дерево t состоит из пары значения v и списка деревьев (его дочерних элементов). Это определение более компактно, но несколько запутано: дерево состоит из пары одного типа и списка другого, которые требуют распутывания для подтверждения результатов.

В стандартном ML типы данных tree и forest могут быть взаимно рекурсивно определены следующим образом, что позволяет использовать пустые деревья:

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

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

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

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

Основные примеры

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

bool is_even(unsigned int n) {
    if (n == 0)
        return true;
    else
        return is_odd(n - 1);
}

bool is_odd(unsigned int n) {
    if (n == 0)
        return false;
    else
        return is_even(n - 1);
}

Эти функции основаны на наблюдении, что вопрос равен 4? эквивалентно 3 нечетным? , что, в свою очередь, эквивалентно равен 2? и так далее до 0. Этот пример представляет собой взаимную одиночную рекурсию , и его можно легко заменить итерацией. В этом примере взаимно рекурсивные вызовы являются хвостовыми вызовами , и оптимизация хвостовых вызовов будет необходима для выполнения в постоянном пространстве стека. В C это заняло бы пространство стека O ( n ), если бы оно не было переписано для использования переходов вместо вызовов. Это можно свести к одной рекурсивной функции is_even. В этом случае, is_oddкоторый может быть встроен, вызовет is_even, но is_evenвызовет только себя.

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

def f_tree(tree) -> None:
    f_value(tree.value)
    f_forest(tree.children)

def f_forest(forest) -> None:
    for tree in forest:
        f_tree(tree)

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

Используя приведенный выше тип данных Standard ML, размер дерева (количество узлов) можно вычислить с помощью следующих взаимно рекурсивных функций:

fun size_tree Empty = 0
  | size_tree (Node (_, f)) = 1 + size_forest f
and size_forest Nil = 0
  | size_forest (Cons (t, f')) = size_tree t + size_forest f'

Более подробный пример на схеме подсчета листьев дерева:

(define (count-leaves tree)
  (if (leaf? tree)
      1
      (count-leaves-in-forest (children tree))))

(define (count-leaves-in-forest forest)
  (if (null? forest)
      0
      (+ (count-leaves (car forest))
         (count-leaves-in-forest (cdr forest)))))

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

Продвинутые примеры

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

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

Есть также некоторые алгоритмы, которые естественно имеют две фазы, такие как минимакс (min и max), которые могут быть реализованы, если каждая фаза находится в отдельной функции с взаимной рекурсией, хотя они также могут быть объединены в одну функцию с прямой рекурсией.

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

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

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

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

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

Некоторые стили программирования не поощряют взаимную рекурсию, утверждая, что может сбивать с толку различение условий, которые возвращают ответ, от условий, которые позволили бы коду работать вечно, не давая ответа. Питер Норвиг указывает на шаблон проектирования, который полностью препятствует использованию, заявляя:

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

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

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

Преобразование в прямую рекурсию

Математически набор взаимно рекурсивных функций является примитивно рекурсивным , что может быть доказано рекурсией курса значений , построением единственной функции F, которая перечисляет значения отдельной рекурсивной функции по порядку: и переписыванием взаимной рекурсии как примитивной рекурсии . ${\ Displaystyle F = f_ {1} (0), f_ {2} (0), f_ {1} (1), f_ {2} (1), \ точки,}$

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

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

Languages

In other projects