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

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

Примеры

Типы данных

Дополнительная информация: Рекурсивный тип данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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);
}

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

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

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)))))

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

Расширенные примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Обнаружение цикла (теория графов)
• Рекурсия (информатика)
• Круговая зависимость

Ссылки

• Харпер, Роберт (2000), Программирование на стандартном машинном обучении
• Харви, Брайан; Райт, Мэтью (1999). Просто схема: введение в информатику . МТИ Пресс. ISBN  978-0-26208281-5 .
• Хаттон, Грэм (2007). Программирование на Хаскеле . Издательство Кембриджского университета. ISBN  978-0-52169269-4 .

Внешние ссылки

• Взаимная рекурсия в Rosetta Code
• « Пример, демонстрирующий хорошее использование взаимной рекурсии », « Есть ли какой-нибудь пример взаимной рекурсии? », Stack Overflow на русском