Из Википедии, свободной энциклопедии
  (Перенаправлен из взаимно рекурсивного )
Перейти к навигации Перейти к поиску

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

Примеры [ править ]

Типы данных [ править ]

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

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

f: [t [1], ..., t [k]]т: vf

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

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

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

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

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

Тип данных  ' дерево = Слейте | Узел из « в * » в лесу и ' леса = Nil | Cons из « в дерево * » лес

Компьютерные функции [ править ]

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

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

Основные примеры [ править ]

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

bool  is_even ( unsigned  int  n )  {  если  ( n  ==  0 )  вернуть  истину ;  иначе  вернуть  is_odd ( n  -  1 ); }bool  is_odd ( unsigned  int  n )  {  if  ( n  ==  0 )  return  false ;  иначе  вернуть  is_even ( n  -  1 ); }

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

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

def  f_tree ( дерево )  ->  None :  f_value ( дерево . значение )  f_forest ( дерево . дочерние элементы )def  f_forest ( лес )  ->  None :  для  дерева  в  лесу :  f_tree ( дерево )

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

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

весело  size_tree  Пусто  =  0  |  size_tree  ( Node  (_,  f ))  =  1  +  size_forest  f и  size_forest  Nil  =  0  |  size_forest  ( Cons  ( t ,  f ' ))  =  size_tree  t  +  size_forest  f'

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

( определить ( дерево -количество листьев  ) ( if ( лист? дерево ) 1 ( количество листьев-в-лесу ( дочернее дерево ))))      ( Определить ( кол-листы-в-лес  леса )  ( если ( нуль? Лес )  0  ( + ( кол-листы  ( автомобиль лес ))  ( кол-листы-в-леса  ( корд лес )))))

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

Дополнительные примеры [ править ]

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

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

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

Математические функции [ править ]

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

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

Распространенность [ править ]

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

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

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

Терминология [ править ]

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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