Взаємна рекурсія

Найважливіший приклад даних, які можуть бути визначені за допомогою взаємної рекурсії — дерево, яке можна визначити в термінах лісу (списку дерев). У символьній формі:

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), і їх можна реалізувати, створивши для кожної з фаз окремі функції зі взаємною рекурсією, хоча їх також можна скомбінувати в одну функцію з прямою рекурсією.

В математиці чоловіча і жіноча послідовності Гофштадтера є прикладом пари послідовностей цілих чисел, які є взаємно рекурсивними.

Фрактали можна обчислити (до потрібної точності) за допомогою рекурсивних функцій. Це іноді можна зробити елегантніше за допомогою взаємно рекурсивних чисел. Добрим прикладом є крива Серпінського.