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

В математиці і програмуванні взаємна рекурсія — це вид рекурсії, коли два математичних або програмних об'єкти, таких як функції або типи даних, визначаються в термінах один одного. Взаємна рекурсія поширена у функціональному програмуванні і в деяких галузях, таких як метод рекурсивного спуску, де типи даних є природним чином взаємно рекурсивними, що не дуже поширене в інших галузях.

Приклади

Типи даних

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

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

Ліс f складається зі списку дерев, тоді як дерево t складається з пари — значення v і лісу f (нащадків). Це визначення елегантне і його легко використовувати для роботи, оскільки дерево виражається в простих поняттях — списку одного типу і парі з двох типів. Це тип даних підходить для багатьох алгоритмів на деревах, які одним способом опрацьовують значення і іншим способом опрацьовують розгалуження.

Це взаємно рекурсивне визначення можна перетворити на єдине рекурсивне визначення, використовуючи вбудоване визначення лісу: t: v [t[1], ..., t[k]].

Дерево t є парою — значення v і список дерев (нащадків). Це визначення компактніше, але тут не все чисто — дерево являє собою пару — значення одного типу та списку іншого типу, що потребує розкрутки до визначення, наведеного вище.

У мові Standard ML типи даних «дерево» і «ліс», якщо дозволити порожні дерева, можна визначити взаємно рекурсивно так:

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

Комп'ютерні функції

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

Як і у випадку прямих рекурсивних функцій, можуть бути корисними функції-оболонки зі взаємно рекурсивними функціями, визначеними як вкладені функції в області видимості, якщо така можливість підтримується. Це, зокрема, корисно для спільного доступу до даних множини функцій без передавання параметрів.

Основні приклади

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

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, підраховує число листків дерева:

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

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

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

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

Поширеність

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

Деякі стилі програмування не заохочують взаємної рекурсії, стверджуючи, що складно розрізнити умови, які повернуть відповідь, від умов, за яких код зациклиться (буде працювати вічно, не повертаючи відповіді). Пітер Норвіг вказав на шаблон розробки, якого слід уникати в будь-якому разі. Він стверджує:

Якщо у вас є дві взаємно рекурсивних функції, що змінюють стан об'єкта, спробуйте перенести майже всю функціональність в одну з цих функцій. В іншому випадку ви зі значною часткою ймовірності отримаєте дублювання коду.

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

Взаємна рекурсія відома також як непряма рекурсія, на відміну від прямої рекурсії, коли одна функція викликає себе безпосередньо. Це просто відмінність в акцентуванні, але не різниця в підході — «непряма рекурсія» підкреслює використання індивідуальної функції, тоді як «взаємна рекурсія» підкреслює використання набору функцій, а не окремої індивідуальної функції. Наприклад, якщо f викликає себе, це пряма рекурсія. Якщо ж f викликає g, а потім g викликає f, яка, в свою чергу, викликає знову g, з точки зору функції f самої, f має непряму рекурсію. З точки зору функції g вона теж має непряму рекурсію. Але з точки зору набору функцій f і g ми маємо взаємну рекурсію. Так само, набір трьох і більше функцій можуть викликати одна одну взаємно.

Зведення до прямої рекурсії

Математично, множина взаємно рекурсивних функцій є примітивно рекурсивними, що можна довести за допомогою зворотної рекурсії, для чого будується функція F, яка перелічує значення індивідуальних рекурсивних функцій у переміжному порядку: $F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,$ і взаємна рекурсія переписується у вигляді примітивної рекурсії.

Будь-яку взаємну рекурсію між двома процедурами можна звести до прямої рекурсії шляхом вбудовування коду однієї процедури в іншу. Якщо є тільки одне місце, де процедура викликає іншу, це можна здійснити безпосередньо, якщо ж таких місць декілька, може знадобитися дублювання коду. У термінах використання стека дві взаємно рекурсивні процедури заповнюють стек послідовністю викликів ABABAB…, а вбудовування процедури B в A призводить до прямої рекурсії (AB)(AB)(AB)…

Альтернативно, будь-яке число процедур можна злити в одну процедуру, яка приймає як аргумент мічене об'єднання (або алгебричний тип даних), що зберігає інформацію про викликану процедуру та її аргументи. Зібрана воєдино процедура вибирає гілку залежно від аргументів і виконує відповідний код, потім використовує пряму рекурсію для виклику себе з відповідними аргументами. Такий підхід можна розглядати як урізаний варіант виключення функцій. Таке злиття функцій може бути корисним, коли деякі функції можуть викликатися зовнішнім кодом, так що вбудовування однієї процедури в іншу неможливе. Такий код потрібно перетворити так, щоб виклики процедур виконувалися шляхом об'єднання аргументів у «мічене об'єднання», як описано вище. Інший варіант — використання процедури-обгортки.

Див. також

• Рекурсія (програмування)
• Циклічна залежність

Література

• Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores. ACM SIGCSE Bulletin. — ACM, 2008. — Т. 40. — С. 235-239.

• Robert Harper. [1] — Carnegie Mellon University, 2005. Архівовано з джерела 29 червня 2020
• 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.

Посилання

• [[https://web.archive.org/web/20201111224941/http://rosettacode.org/wiki/Mutual_recursion Архівовано 11 листопада 2020 у Wayback Machine.] Mutual recursion] at Rosetta Code
• «[[https://web.archive.org/web/20161011013429/https://stackoverflow.com/questions/10295735/example-demonstrating-good-use-of-mutual-recursion Архівовано 11 жовтня 2016 у Wayback Machine.] Example demonstrating good use of mutual recursion]», «[[https://web.archive.org/web/20161011013320/https://stackoverflow.com/questions/2725038/are-there-any-example-of-mutual-recursion Архівовано 11 жовтня 2016 у Wayback Machine.] Are there any example of Mutual recursion?]», Stack Overflow