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

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

Примеры

Типы данных

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

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

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

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

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

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

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

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

тип данных 'а дерево = Пустой | Узел из 'а * 'а леси      'а лес = Ноль | Минусы из 'а дерево * 'а лес

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

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

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

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

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

bool даже(беззнаковый int п) {    если (п == 0)        возвращаться истинный;    еще        возвращаться is_odd(п - 1);}bool is_odd(беззнаковый int п) {    если (п == 0)        возвращаться ложный;    еще        возвращаться даже(п - 1);}

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

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

def f_tree(дерево) -> Никто:    f_value(дерево.ценить)    f_forest(дерево.дети)def f_forest(лес) -> Никто:    за дерево в лес:        f_tree(дерево)

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

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

весело size_tree Пустой = 0  | size_tree (Узел (_, ж)) = 1 + size_forest жи size_forest Ноль = 0  | size_forest (Минусы (т, f ')) = size_tree т + size_forest f '

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

(определять (счет-листья дерево)  (если (лист? дерево)      1      (подсчет листьев в лесу (дети дерево))))(определять (подсчет листьев в лесу лес)  (если (ноль? лес)      0      (+ (счет-листья (машина лес))         (подсчет листьев в лесу (CDR лес)))))

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

Дополнительные примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

Математически набор взаимно рекурсивных функций примитивно рекурсивный, что может быть доказано рекурсия курса ценностей,[9] построение единой функции F в котором перечислены значения отдельной рекурсивной функции в следующем порядке: и переписывая взаимную рекурсию как примитивную рекурсию.

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

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

Смотрите также

Рекомендации

  1. ^ Мануэль Рубио-Санчес, Хайме Уркиса-Фуэнтес, Кристобаль Пареха-Флорес (2002), «Нежное введение в взаимную рекурсию», Труды 13-й ежегодной конференции по инновациям и технологиям в образовании в области компьютерных наук, 30 июня - 2 июля 2008 г., Мадрид, Испания.
  2. ^ Харпер 2000, "Типы дат ".
  3. ^ Хаттон 2007, 6.5 Взаимная рекурсия, стр. 53–55.
  4. ^ "Взаимная рекурсия хвоста " и "Хвостовые рекурсивные функции ", Учебник по функциям программирования в ATS, Хунвэй Си, 2010 г.
  5. ^ Харпер 2000, "Типы данных ".
  6. ^ Харви и Райт 1999, V. Абстракция: 18. Деревья: взаимная рекурсия, стр. 310–313.
  7. ^ Абельсон, Гарольд; Сассман, Джеральд Джей; Суссман, Джули (1996). Структура и интерпретация компьютерных программ (PDF). Лондон, Англия: MIT Press. п. 492. ISBN  978-0262510875.
  8. ^ Решение всех головоломок судоку
  9. ^ "взаимная рекурсия ", PlanetMath
  10. ^ О преобразовании косвенной рекурсии в прямую Оуэн Касер, К. Р. Рамакришнан и Шаунак Паваги в Государственный университет Нью-Йорка, Стоуни-Брук (1993)
  11. ^ Рейнольдс, Джон (Август 1972 г.). "Определительные интерпретаторы языков программирования высшего порядка" (PDF). Материалы ежегодной конференции ACM. Бостон, Массачусетс. С. 717–740.

внешняя ссылка