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

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

Примеры

Типы данных

Подробное рассмотрение темы: Рекурсивный тип данных

Наиболее важный пример данных, которые могут быть определены с помощью взаимной рекурсии — дерево, которое может быть определено в терминах леса (списка деревьев). В символической форме: 

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

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

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

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

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

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

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

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

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

Стандартный пример взаимной рекурсии, который является, по общему признанию, искусственным приёмом, определяет, число чётно или нет, путём определения двух раздельных функций, вызывающих друг друга и уменьшающих число при каждом вызове[3]. На 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) стекового пространства, если не использовать переходы (goto) вместо вызовов функций [4]. Пример можно преобразовать в одну рекурсивную функцию is_even. В этом случае is_odd, можно использовать как встроенную (inline) и она будет вызывать is_even, но is_even будет вызывать только себя.

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

 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

 def f_forest(forest):
     for tree in forest:
         f_tree(tree)

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

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

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'

Более детальный пример на языке Scheme, подсчитывающий число листьев дерева[6]: 

(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), и они могут быть имплементированы путём создания для каждой фазы отдельной функции с взаимной рекурсией, хотя они также могут быть скомбинированы в одну функцию с прямой рекурсией.

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

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

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

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

Взаимная рекурсия широко распространена в функциональном программировании и часто применяется в программах, написанных на языках Лисп, Scheme, ML и других подобных языках. В таких языках, как Пролог, взаимная рекурсия почти неизбежна.

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

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

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

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

Сведение к прямой рекурсии

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

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

Альтернативно, любое число процедур можно слить в одну процедуру, которая принимает в качестве аргумента меченое объединение (или алгебраический тип данных), хранящее информацию о вызываемой процедуре и её аргументах. Собранная воедино процедура выбирает ветку в зависимости от аргументов и выполняет соответствующий код, затем использует прямую рекурсию для вызова себя с подходящими аргументами. Такой подход можно рассматривать как усечённый вариант исключения функций[англ.] [9]. Такое слияние функций может быть полезно, когда некоторые функции могут вызываться внешним кодом, так что встраивание одной процедуры в другую невозможно. Такой код требуется преобразовать так, что вызовы процедур выполнялись путём объединения аргументов в «меченое объединение», как описано выше. Другой вариант — использование обёртывающей процедуры.

См. также

Примечания

  1. ↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008, с. 235-239.
  2. ↑ Harper, 2005, "Date Types".
  3. ↑ Hutton, 2007, 6.5 Mutual recursion, pp. 53–55.
  4. ↑ "Mutual Tail-Recursion Архивная копия от 10 апреля 2016 на Wayback Machine" and "Tail-Recursive Functions Архивная копия от 10 апреля 2016 на Wayback Machine", A Tutorial on Programming Features in ATS Архивная копия от 27 декабря 2017 на Wayback Machine, Hongwei Xi, 2010
  5. ↑ Harper, 2005, "Datatypes".
  6. ↑ Harvey, Wright, 1999, V. Abstraction: 18. Trees: Mutual Recursion, pp. 310–313.
  7. ↑ Solving Every Sudoku Puzzle. Дата обращения: 13 января 2017. Архивировано 15 ноября 2020 года.
  8. ↑ "mutual recursion Архивная копия от 21 июня 2018 на Wayback Machine" PlanetMath
  9. ↑ Reynolds, John (August 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717—740. Архивировано из оригинала (PDF) 29 июня 2011. Дата обращения: 13 января 2017.

Литература

  • Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores. ACM SIGCSE Bulletin. — ACM, 2008. — Т. 40. — С. 235-239.
  • Robert Harper. Programming in Standard ML (Working Drafn of MAY 17, 2005.). — Carnegie Mellon University, 2005.
  • Brian Harvey, Matthew Wright. Simply Scheme: Introducing Computer Science. — MIT Press, 1999. — ISBN 978-0-26208281-5.
  • Graham Hutton. Programming in Haskell. — Cambridge University Press, 2007. — ISBN 978-0-52169269-4.

Ссылки