Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В математиці і програмуванні взаємна рекурсія це вид рекурсії коли два математичних або програмних об єкти таких як функ

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

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

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

Приклади

Типи даних

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

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

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

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

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

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

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

(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)))))

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

Складніші приклади

Складнішими прикладами є приклади рекурсивного спуску, які можна реалізувати природним чином, якщо поставити по одній функції для кожного [en] граматики, які потім взаємно рекурсивно викликають одна одну. В загальному випадку це будуть багаторазові рекурсії, коли породжувальні правила комбінують кілька правил. Це можна зробити і без взаємної рекурсії, маючи окремі функції для кожного породжувального правила, але викликаючи одну контрольну функцію або опрацьовуючи всю граматику в одній функції.

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

Існують також алгоритми, які природним чином мають дві фази, такі як мінімакс (min і max), і їх можна реалізувати, створивши для кожної з фаз окремі функції зі взаємною рекурсією, хоча їх також можна скомбінувати в одну функцію з прямою рекурсією.

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

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

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

Поширеність

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  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. . Архів оригіналу за 15 листопада 2020. Процитовано 6 листопада 2020.
  8. «mutual recursion [ 21 червня 2018 у Wayback Machine.]» PlanetMath
  9. (August 1972). (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts. с. 717—740. Архів оригіналу (PDF) за 29 червня 2011. Процитовано 6 листопада 2020. {{}}: Пропущений або порожній |title= (); |first3= з пропущеним |last3= ()

Література

  • 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. — .
  • Graham Hutton. Programming in Haskell. — Cambridge University Press, 2007. — .

Посилання

  • [[https://web.archive.org/web/20201111224941/http://rosettacode.org/wiki/Mutual_recursion Архівовано 11 листопада 2020 у Wayback Machine.] Mutual recursion] at
  • «[[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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V matematici i programuvanni vzayemna rekursiya ce vid rekursiyi koli dva matematichnih abo programnih ob yekti takih yak funkciyi abo tipi danih viznachayutsya v terminah odin odnogo Vzayemna rekursiya poshirena u funkcionalnomu programuvanni i v deyakih galuzyah takih yak metod rekursivnogo spusku de tipi danih ye prirodnim chinom vzayemno rekursivnimi sho ne duzhe poshirene v inshih galuzyah PrikladiTipi danih Najvazhlivishij priklad danih yaki mozhut buti viznacheni za dopomogoyu vzayemnoyi rekursiyi derevo yake mozhna viznachiti v terminah lisu spisku derev U simvolnij formi f t 1 t k t v f Lis f skladayetsya zi spisku derev todi yak derevo t skladayetsya z pari znachennya v i lisu f nashadkiv Ce viznachennya elegantne i jogo legko vikoristovuvati dlya roboti oskilki derevo virazhayetsya v prostih ponyattyah spisku odnogo tipu i pari z dvoh tipiv Ce tip danih pidhodit dlya bagatoh algoritmiv na derevah yaki odnim sposobom opracovuyut znachennya i inshim sposobom opracovuyut rozgaluzhennya Ce vzayemno rekursivne viznachennya mozhna peretvoriti na yedine rekursivne viznachennya vikoristovuyuchi vbudovane viznachennya lisu t v t 1 t k Derevo t ye paroyu znachennya v i spisok derev nashadkiv Ce viznachennya kompaktnishe ale tut ne vse chisto derevo yavlyaye soboyu paru znachennya odnogo tipu ta spisku inshogo tipu sho potrebuye rozkrutki do viznachennya navedenogo vishe U movi Standard ML tipi danih derevo i lis yaksho dozvoliti porozhni dereva mozhna viznachiti vzayemno rekursivno tak 2 datatype a tree Empty Node of a a forest and a forest Nil Cons of a tree a forest Komp yuterni funkciyi Tak samo yak algoritmi na rekursivnih tipah danih mozhna zadati rekursivnimi funkciyami algoritmi na vzayemno rekursivnih strukturah danih mozhna zadati vzayemno rekursivnimi funkciyami Zagalnovidomi prikladi algoritmi na derevah i metod rekursivnogo spusku Yak i u vipadku pryamoyi rekursiyi optimizaciya hvostovoyi rekursiyi neobhidna yaksho glibina rekursiyi velika abo vzagali ne obmezhena Zauvazhimo sho optimizaciya hvostovoyi rekursiyi v zagalnomu vipadku yaksho viklikayetsya ne ta zh sama funkciya sho j originalna yak u hvostovij rekursiyi mozhe viyavitisya skladnishe realizuvati nizh u vipadku optimizaciyi hvostovoyi rekursiyi i efektivna realizaciya vzayemnoyi hvostovoyi rekursiyi mozhe buti vidsutnoyu v movah sho optimizuyut tilki hvostovi vikliki U movah takih yak Paskal v yakih potribni viznachennya ob yektiv persh nizh ob yekt mozhe buti zastosovanij vzayemno rekursivni funkciyi potrebuyut poperednogo ogoloshennya Yak i u vipadku pryamih rekursivnih funkcij mozhut buti korisnimi funkciyi obolonki zi vzayemno rekursivnimi funkciyami viznachenimi yak vkladeni funkciyi v oblasti vidimosti yaksho taka mozhlivist pidtrimuyetsya Ce zokrema korisno dlya spilnogo dostupu do danih mnozhini funkcij bez peredavannya parametriv Osnovni prikladi Standartnij priklad vzayemnoyi rekursiyi yakij prote viznayetsya shtuchnim prijomom viznachaye parne chislo chi ni shlyahom viznachennya dvoh okremih funkcij yaki viklikayut odna odnu i zmenshuyut chislo pid chas kozhnogo vikliku Na 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 Ci funkciyi gruntuyutsya na sposterezhenni sho pitannya 4 parne ekvivalentne pitannyu 3 neparne yakij v svoyu chergu ekvivalentne pitannyu 2 parne i tak dali do 0 Priklad pokazuye vzayemnu odinichnu rekursiyu yaku mozhna legko zaminiti ciklom U comu prikladi vikliki vzayemnoyi rekursiyi ye hvostovimi viklikami i optimizaciya hvostovih viklikiv bazhana shob vikonannya vidbuvalosya za stalogo stekovogo prostoru U C funkciyi zazhadayut O n stekovogo prostoru yaksho ne vikoristovuvati perehodi goto zamist viklikiv funkcij Priklad mozhna peretvoriti na odnu rekursivnu funkciyu is even U comu vipadku is odd mozhna vikoristovuvati yak vbudovanu inline i vona bude viklikati is even ale is even viklikatime tilki sebe Priklad z bilsh zagalnogo klasu prikladiv algoritm roboti z derevami mozhna rozklasti na robotu zi znachennyam i na robotu z gilkami a potim rozbiti na dvi vzayemno rekursivni funkciyi odna z funkcij pracyuye z derevom i viklikaye funkciyu roboti z lisom druga pracyuye z lisom i viklikaye funkciyu dlya dereva dlya kozhnogo elementa lisu Movoyu Python def f tree tree f value tree value f forest tree children def f forest forest for tree in forest f tree tree U comu vipadku funkciya dlya dereva viklikaye funkciyu dlya lisu shlyahom odinichnoyi rekursiyi a os funkciya lisu vikoristovuye dlya dereva bagatokratnu rekursiyu Yaksho vikoristovuvati opisani vishe movoyu Standard ML tipi danih rozmir dereva chislo reber mozhna obchisliti takimi vzayemno rekursivnimi funkciyami 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 Detalnishij priklad movoyu Scheme pidrahovuye chislo listkiv dereva 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 Ci prikladi legko zvodyatsya do odniyeyi rekursivnoyi funkciyi shlyahom vbudovuvannya funkciyi dlya lisu u funkciyu dlya dereva sho chasto na praktici j robitsya Skladnishi prikladi Skladnishimi prikladami ye prikladi rekursivnogo spusku yaki mozhna realizuvati prirodnim chinom yaksho postaviti po odnij funkciyi dlya kozhnogo en gramatiki yaki potim vzayemno rekursivno viklikayut odna odnu V zagalnomu vipadku ce budut bagatorazovi rekursiyi koli porodzhuvalni pravila kombinuyut kilka pravil Ce mozhna zrobiti i bez vzayemnoyi rekursiyi mayuchi okremi funkciyi dlya kozhnogo porodzhuvalnogo pravila ale viklikayuchi odnu kontrolnu funkciyu abo opracovuyuchi vsyu gramatiku v odnij funkciyi Vzayemna rekursiya mozhe takozh buti vikoristana dlya realizaciyi skinchennogo avtomata z odniyeyu funkciyeyu dlya kozhnogo stanu i yedinoyu rekursiyeyu u zmini stanu Ce vimagaye optimizaciyi hvostovoyi rekursiyi yaksho chislo staniv velike abo neobmezhene Takij pidhid mozhna vikoristati yak prostu formu kooperativnoyi bagatozadachnosti Shozhij pidhid do bagatozadachnosti vikoristovuye spivprogrami yaki viklikayut odna odnu de zamist pererivannya shlyahom vikliku inshoyi proceduri odna spivprograma viklikaye inshu ale ne pripinyayetsya a prodovzhuye vikonannya koli viklikana spivprograma povertaye keruvannya Ce dozvolyaye individualnim spivprogramam zberigati stan bez neobhidnosti peredavati parametri abo zberigati spilni zminni Isnuyut takozh algoritmi yaki prirodnim chinom mayut dvi fazi taki yak minimaks min i max i yih mozhna realizuvati stvorivshi dlya kozhnoyi z faz okremi funkciyi zi vzayemnoyu rekursiyeyu hocha yih takozh mozhna skombinuvati v odnu funkciyu z pryamoyu rekursiyeyu Matematichni funkciyi V matematici cholovicha i zhinocha poslidovnosti Gofstedtera ye prikladom pari poslidovnostej cilih chisel yaki ye vzayemno rekursivnimi Fraktali mozhna obchisliti do potribnoyi tochnosti za dopomogoyu rekursivnih funkcij Ce inodi mozhna zrobiti elegantnishe za dopomogoyu vzayemno rekursivnih chisel Dobrim prikladom ye kriva Serpinskogo PoshirenistVzayemna rekursiya poshirena u funkcionalnomu programuvanni i chasto zastosovuyetsya v programah napisanih movami Lisp Scheme ML ta inshimi podibnimi U takih movah yak Prolog vzayemna rekursiya majzhe neminucha Deyaki stili programuvannya ne zaohochuyut vzayemnoyi rekursiyi stverdzhuyuchi sho skladno rozrizniti umovi yaki povernut vidpovid vid umov za yakih kod zaciklitsya bude pracyuvati vichno ne povertayuchi vidpovidi Piter Norvig vkazav na en yakogo slid unikati v bud yakomu razi Vin stverdzhuye Yaksho u vas ye dvi vzayemno rekursivnih funkciyi sho zminyuyut stan ob yekta sprobujte perenesti majzhe vsyu funkcionalnist v odnu z cih funkcij V inshomu vipadku vi zi znachnoyu chastkoyu jmovirnosti otrimayete dublyuvannya kodu TerminologiyaVzayemna rekursiya vidoma takozh yak nepryama rekursiya na vidminu vid pryamoyi rekursiyi koli odna funkciya viklikaye sebe bezposeredno Ce prosto vidminnist v akcentuvanni ale ne riznicya v pidhodi nepryama rekursiya pidkreslyuye vikoristannya individualnoyi funkciyi todi yak vzayemna rekursiya pidkreslyuye vikoristannya naboru funkcij a ne okremoyi individualnoyi funkciyi Napriklad yaksho f viklikaye sebe ce pryama rekursiya Yaksho zh f viklikaye g a potim g viklikaye f yaka v svoyu chergu viklikaye znovu g z tochki zoru funkciyi f samoyi f maye nepryamu rekursiyu Z tochki zoru funkciyi g vona tezh maye nepryamu rekursiyu Ale z tochki zoru naboru funkcij f i g mi mayemo vzayemnu rekursiyu Tak samo nabir troh i bilshe funkcij mozhut viklikati odna odnu vzayemno Zvedennya do pryamoyi rekursiyiMatematichno mnozhina vzayemno rekursivnih funkcij ye primitivno rekursivnimi sho mozhna dovesti za dopomogoyu en dlya chogo buduyetsya funkciya F yaka perelichuye znachennya individualnih rekursivnih funkcij u peremizhnomu poryadku F f1 0 f2 0 f1 1 f2 1 displaystyle F f 1 0 f 2 0 f 1 1 f 2 1 dots i vzayemna rekursiya perepisuyetsya u viglyadi primitivnoyi rekursiyi Bud yaku vzayemnu rekursiyu mizh dvoma procedurami mozhna zvesti do pryamoyi rekursiyi shlyahom vbudovuvannya kodu odniyeyi proceduri v inshu Yaksho ye tilki odne misce de procedura viklikaye inshu ce mozhna zdijsniti bezposeredno yaksho zh takih misc dekilka mozhe znadobitisya dublyuvannya kodu U terminah vikoristannya steka dvi vzayemno rekursivni proceduri zapovnyuyut stek poslidovnistyu viklikiv ABABAB a vbudovuvannya proceduri B v A prizvodit do pryamoyi rekursiyi AB AB AB Alternativno bud yake chislo procedur mozhna zliti v odnu proceduru yaka prijmaye yak argument en abo algebrichnij tip danih sho zberigaye informaciyu pro viklikanu proceduru ta yiyi argumenti Zibrana voyedino procedura vibiraye gilku zalezhno vid argumentiv i vikonuye vidpovidnij kod potim vikoristovuye pryamu rekursiyu dlya vikliku sebe z vidpovidnimi argumentami Takij pidhid mozhna rozglyadati yak urizanij variant en Take zlittya funkcij mozhe buti korisnim koli deyaki funkciyi mozhut viklikatisya zovnishnim kodom tak sho vbudovuvannya odniyeyi proceduri v inshu nemozhlive Takij kod potribno peretvoriti tak shob vikliki procedur vikonuvalisya shlyahom ob yednannya argumentiv u michene ob yednannya yak opisano vishe Inshij variant vikoristannya proceduri obgortki Div takozhRekursiya programuvannya en PrimitkiRubio Sanchez Urquiza Fuentes Pareja Flores 2008 s 235 239 Harper 2005 Date Types Hutton 2007 6 5 Mutual recursion pp 53 55 Mutual Tail Recursion 10 kvitnya 2016 u Wayback Machine and Tail Recursive Functions 10 kvitnya 2016 u Wayback Machine A Tutorial on Programming Features in ATS 27 grudnya 2017 u Wayback Machine Hongwei Xi 2010 Harper 2005 Datatypes Harvey Wright 1999 V Abstraction 18 Trees Mutual Recursion pp 310 313 Arhiv originalu za 15 listopada 2020 Procitovano 6 listopada 2020 mutual recursion 21 chervnya 2018 u Wayback Machine PlanetMath August 1972 PDF Proceedings of the ACM Annual Conference Boston Massachusetts s 717 740 Arhiv originalu PDF za 29 chervnya 2011 Procitovano 6 listopada 2020 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite conference title Shablon Cite conference cite conference a Propushenij abo porozhnij title dovidka first3 z propushenim last3 dovidka LiteraturaManuel Rubio Sanchez Jaime Urquiza Fuentes Cristobal Pareja Flores ACM SIGCSE Bulletin ACM 2008 T 40 S 235 239 Robert Harper 1 Carnegie Mellon University 2005 z dzherela 29 chervnya 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 Posilannya https web archive org web 20201111224941 http rosettacode org wiki Mutual recursion Arhivovano11 listopada 2020 u Wayback Machine Mutual recursion at https web archive org web 20161011013429 https stackoverflow com questions 10295735 example demonstrating good use of mutual recursion Arhivovano11 zhovtnya 2016 u 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 Arhivovano11 zhovtnya 2016 u Wayback Machine Are there any example of Mutual recursion Stack Overflow

Дата публікації:
Топ