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

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

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

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

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