Recursiune reciprocă

În matematică și programare, recursiunea reciprocă este un tip de recursivitate în care două obiecte matematice sau de program, cum ar fi funcții sau tipuri de date, sunt definite unul în termenii celuilalt [1] . Recursiunea reciprocă este obișnuită în programarea funcțională și în unele zone cu probleme, cum ar fi metoda de coborâre recursivă , unde tipurile de date sunt în mod natural recursive reciproc, ceea ce nu este comun în alte domenii.

Exemple

Tipuri de date

Cel mai important exemplu de date care pot fi definite folosind recursiunea reciprocă este un arbore , care poate fi definit în termeni de pădure (o listă de copaci). În formă simbolică:

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

Pădurea f constă dintr-o listă de copaci, în timp ce arborele t constă dintr-o pereche - valoarea v și pădurea f (copii). Această definiție este elegantă și ușor de lucrat, deoarece arborele este exprimat în termeni simpli - o listă de un tip și o pereche de două tipuri. Acest tip de date este potrivit pentru mulți algoritmi de arbore care procesează valorile într-un fel și gestionează ramificarea într-un alt mod.

Această definiție recursivă reciproc poate fi convertită într-o singură definiție recursivă folosind definiția de pădure încorporată: t: v [t[1], ..., t[k]]. Arborele t este o pereche - valoarea v și o listă de copaci (copii). Această definiție este mai compactă, dar nu totul este pur aici - un arbore este o pereche - o valoare de un tip și o listă de alt tip, care va necesita derulare la definiția de mai sus.

În Standard ML , tipurile de date arbore și pădure pot fi definite reciproc recursiv, după cum urmează, dacă sunt permise arbori goali [2] :

tipul de date ' a tree = Gol | Nodul „ a * ” o pădure și „ o pădure = Nil | _ Dezavantajele „ un copac * ” o pădure _

Funcții computer

Așa cum algoritmii pe tipuri de date recursive pot fi definiți prin funcții recursive, algoritmii pe structuri de date reciproc recursive pot fi definiți în mod natural prin funcții recursive reciproce. Exemplele binecunoscute includ algoritmi de arbore și metoda de coborâre recursivă . Ca și în cazul recursiunii directe, optimizarea recursiunii de coadă este necesară dacă adâncimea recursiunii este mare sau nu este limitată deloc. Rețineți că optimizarea recursiunii cozii, în general (dacă funcția apelată nu este aceeași cu funcția originală, ca în recursiunea cozii) poate fi mai dificil de implementat decât în ​​cazul optimizării recursiunii cozii și o implementare eficientă a recursiunii cozii reciproce este posibil să nu fie disponibil în limbi care optimizează numai apelurile de coadă. În limbaje precum Pascal , care necesită definiții de obiect înainte ca un obiect să poată fi utilizat, funcțiile recursive reciproc necesită o declarație înainte .

Ca și în cazul funcțiilor recursive directe, funcțiile wrapper cu funcții recursive reciproc definite ca funcții imbricate domeniu pot fi utile dacă sunt acceptate. Acest lucru este util în special pentru partajarea datelor între mai multe funcții fără a trece parametri.

Exemple de bază

Un exemplu standard de recursivitate reciprocă, care este, desigur, un truc artificial, determină dacă un număr este par sau nu prin definirea a două funcții separate care se apelează reciproc și decrementează numărul la fiecare apel [3] . Pe C:

bool is_even ( unsigned int n ) { dacă ( n == 0 ) returnează adevărat ; altfel returnare este_impar ( n - 1 ); } bool is_odd ( unsigned int n ) { dacă ( n == 0 ) returnează fals ; altfel returnare este_par ( n - 1 ); }

Aceste funcții se bazează pe observația că întrebarea „4 este par?” este echivalent cu întrebarea „3 este impar?”, care este, la rândul său, echivalent cu întrebarea „2 este par”, și așa mai departe până la 0. Exemplul arată recursiunea unitară reciprocă , care poate fi ușor înlocuită cu o buclă. În acest exemplu, apelurile recursive reciproce sunt apeluri de coadă și este de dorit să se optimizeze apelurile de coadă, astfel încât execuția să aibă loc pe un spațiu de stivă constant. În C, funcțiile vor necesita spațiu de stivă O ( n ) cu excepția cazului în care se utilizează salturi (goto) în loc de apeluri de funcție [4] . Exemplul poate fi convertit într-o singură funcție recursivă is_even. În acest caz is_odd, poate fi folosit inline și va apela is_even, dar is_evense va apela numai pe sine.

Un exemplu dintr-o clasă mai generală de exemple, algoritmul arborelui, poate fi descompus într-o operație de valoare și o operație de ramură și apoi poate fi împărțit în două funcții recursive reciproce, una dintre funcții operează pe arbore și apelează funcția forestieră. , al doilea lucrează cu pădurea și apelează funcția pentru arbore pentru fiecare element al pădurii. În limbajul Python:

def f_tree ( copac ): f_valoare ( copac . valoare ) f_forest ( copac . copii ) def f_forest ( forest ): pentru copac din pădure : f_tree ( copac )

În acest caz, funcția arbore apelează funcția forestieră folosind recursiunea unică, dar funcția forestieră folosește recursiunea multiplă în arbore .

Folosind tipurile de date descrise mai sus în Standard ML , dimensiunea arborelui (numărul de muchii) poate fi calculată prin următoarele funcții recursive reciproce [5] :

fun size_tree Gol = 0 | size_tree ( Nodul (_, f )) = 1 + size_forest f și size_forest Nil = 0 | size_forest ( Contra ( t , f' )) = size_tree t + size_forest f'

Un exemplu de schemă mai detaliat care numără numărul de frunze dintr-un copac [6] :

( define ( numărare-frunze de copac ) ( dacă ( frunze? copac ) 1 ( numără-frunze-în-pădure ( copii copac )))) ( define ( numărați-frunze-în pădure ) ( dacă ( nul? pădure ) 0 ( + ( numărați-frunze ( pădure mașină )) ( numărați-frunze-în-pădure ( cdr forest )))))

Aceste exemple sunt ușor reduse la o singură funcție recursivă prin încorporarea funcției de pădure în funcția de arbore, ceea ce se face adesea în practică.

Exemple mai avansate

Exemple mai complexe sunt exemplele de descendență recursivă , care pot fi implementate într-un mod natural, dând o funcție pentru fiecare regulă generativă a gramaticii, care apoi se numesc reciproc recursiv. În general, acestea vor fi recursiuni multiple, atunci când generarea de reguli combină mai multe reguli. Acest lucru se poate face fără recursivitate reciprocă, având funcții separate pentru fiecare regulă de generație, dar apelând o funcție de control sau procesând întreaga gramatică într-o singură funcție.

Recursiunea reciprocă poate fi, de asemenea, utilizată pentru a implementa o mașină de stări cu o funcție pentru fiecare stare și o singură recursivitate per schimbare de stare. Acest lucru necesită optimizarea recursiunii de coadă dacă numărul de stări este mare sau nelimitat. Această abordare poate fi folosită ca o formă simplă de multitasking cooperativ . O abordare similară a multitasking-ului folosește corutine care se apelează reciproc, unde, în loc să fie întreruptă prin apelarea unei alte proceduri, o corutine apelează pe alta, dar nu este întreruptă, ci continuă execuția atunci când corutine apelată revine. Acest lucru permite coroutinelor individuale să salveze starea fără a fi nevoie să treacă parametri sau să salveze variabile partajate.

Există, de asemenea, algoritmi care au în mod natural două faze, cum ar fi minimax (min și max), și aceștia pot fi implementați prin crearea unei funcții recursive reciproce separate pentru fiecare fază, deși pot fi, de asemenea, combinați într-o singură funcție recursivă directă.

Funcții matematice

În matematică , secvențele Hofstadter masculin și feminin sunt un exemplu de pereche de secvențe de numere întregi care sunt reciproc recursive.

Fractalii pot fi calculați (cu precizia necesară) folosind funcții recursive. Acest lucru se poate face uneori mai elegant cu numere recursive reciproc. Curba Sierpinski este un bun exemplu.

Prevalență

Recursiunea reciprocă este utilizată pe scară largă în programarea funcțională și este adesea folosită în programele scrise în Lisp , Scheme , ML și alte limbaje similare . În limbi precum Prolog , recursiunea reciprocă este aproape inevitabilă.

Unele stiluri de programare descurajează recursiunea reciprocă, argumentând că este dificil să se facă distincția între condițiile care vor returna un răspuns de condițiile care vor face ca codul să se execute pentru totdeauna fără a returna un răspuns. Peter Norvig a subliniat modelul de dezvoltare care ar trebui evitat oricum. El afirmă [7] :

Dacă aveți două funcții recursive reciproc care schimbă starea unui obiect, încercați să mutați aproape toată funcționalitatea într-una dintre acele funcții. În caz contrar, este mai probabil să ajungeți la duplicarea codului.

Terminologie

Recursiunea reciprocă este cunoscută și sub denumirea de recursivitate indirectă , spre deosebire de recursiunea directă când o funcție se numește direct. Aceasta este doar o diferență de accent, nu o diferență de abordare - „recursiunea indirectă” subliniază utilizarea unei funcții individuale, în timp ce „recursiunea reciprocă” subliniază utilizarea unui set de funcții mai degrabă decât a unei singure funcții individuale. De exemplu, dacă f se numește singur, este o recursivitate directă. Dacă f îl cheamă pe g și atunci g îl numește pe f, care la rândul său îl cheamă din nou pe g , numai din punctul de vedere al lui f , f are recursivitate indirectă. Din punctul de vedere al funcției g , are și recursivitate indirectă. Dar din punctul de vedere al mulțimii de funcții f și g , avem recursiunea reciprocă. În mod similar, un set de trei sau mai multe funcții se pot apela reciproc.

Reducere la recursivitate directă

Din punct de vedere matematic, un set de funcții recursive reciproce sunt primitiv recursive , ceea ce poate fi demonstrat folosind recursiunea inversă [8] , pentru care se construiește o funcție F care enumerează valorile funcțiilor recursive individuale în ordinea intercalată: și recursiunea reciprocă este rescrisă ca recursivitate primitivă.

Orice recursivitate reciprocă între două proceduri poate fi redusă la recursivitate directă prin introducerea codului unei proceduri în cealaltă. Dacă există un singur loc unde procedura apelează altul, acest lucru se poate face direct, dar dacă există mai multe astfel de locuri, poate fi necesară duplicarea codului. În ceea ce privește utilizarea stivei, două proceduri recursive reciproc umplu stiva cu o secvență de apeluri ABABAB..., iar procedura de încorporare B în A are ca rezultat recursiunea directă (AB)(AB)(AB)...

Alternativ, orice număr de proceduri poate fi îmbinat într-o singură procedură care ia ca argument o uniune etichetată (sau tip de date algebrice ) care stochează informații despre procedura apelată și argumentele acesteia. Procedura asamblată selectează o ramură pe baza argumentelor și execută codul corespunzător, apoi folosește recursiunea directă pentru a se apela cu argumentele corespunzătoare. Această abordare poate fi văzută ca o versiune trunchiată a excluderii funcțiilor [9] . Această îmbinare a funcțiilor poate fi utilă atunci când unele funcții pot fi apelate prin cod extern, astfel încât imbricarea unei proceduri în alta nu este posibilă. Un astfel de cod trebuie convertit astfel încât apelurile de procedură să fie făcute prin concatenarea argumentelor într-o „unire etichetată”, așa cum este descris mai sus. O altă opțiune este utilizarea unei proceduri de împachetare.

Vezi și

Note

  1. ↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008 , p. 235-239.
  2. ↑ Harper, 2005 , „ Tipuri de date ”.
  3. ↑ Hutton, 2007 , 6.5 Recursie reciprocă, pp. 53–55 .
  4. ↑ „ Mutual Tail-Recursive Archived 10 April 2016 at the Wayback Machine ” și „ Tail-Recursive Functions Archived 10 April 2016 at the Wayback Machine ”, A Tutorial on Programming Features in ATS Arhivat 27 decembrie 2017 la Wayback Machine . Hongwei Xi, 2010
  5. ↑ Harper, 2005 , „ Tipi de date ”.
  6. ↑ Harvey, Wright, 1999 , V. Abstraction: 18. Trees: Mutual Recursion, pp. 310–313 .
  7. ↑ Rezolvarea tuturor puzzle-urilor Sudoku . Preluat la 13 ianuarie 2017. Arhivat din original la 15 noiembrie 2020.
  8. ↑ „ recursiunea reciprocă Arhivat 21 iunie 2018 la Wayback Machine „ PlanetMath
  9. ↑ Reynolds, John (august 1972). „Interpreți definiționali pentru limbaje de programare de ordin superior” (PDF) . Actele Conferinței Anuale ACM . Boston, Massachusetts. pp. 717-740. Arhivat pe 29 iunie 2011 la Wayback Machine

Literatură

  • Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores. Buletinul ACM SIGCSE. - ACM, 2008. - T. 40. - S. 235-239.
  • Robert Harper. Programare în Standard ML (Working Drafn din 17 MAI 2005.). — Universitatea Carnegie Mellon, 2005.
  • Brian Harvey, Matthew Wright. Simply Scheme: Introducerea informaticii. - MIT Press, 1999. - ISBN 978-0-26208281-5 .
  • Graham Hutton. Programare în Haskell. - Cambridge University Press, 2007. - ISBN 978-0-52169269-4 .

Link -uri