Uzajamna rekurzija

U matematici i računarstvu, uzajamna rekurzija je oblik rekurzije gde se dve matematičke ili računarske funkcije ili dva objekta, definišu jedan preko drugog. Uzajamna rekurzija se često koristi u funkcionalnom programiranju i u nekim problematičnim oblastima kao što su analizatori rekurzivnim spustom, gde su tipovi podataka prirodno uzajamno rekurzivni, ali se retko koristi u drugim oblastima.

Primeri

Tipovi podataka:

Najvažniji osnovni primer tipova podataka koji se može definisati uzajamnom rekurzijom je stablo, koje može biti definisano uzajamno rekurzivno u terminima šume (lista stabala). Simbolički:

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

t: v f

Šuma f se sastoji od liste stabala, dok se stablo t sastoji od parova vrednosti v i šume f (svoje dece). Ova definicija je elegantna i sa njom se jednostavno radi na apstraktnom nivou (kao kada se dokazuju teoreme o osobinama stabala), jer izražava stablo u jednostavnim terminima: lista jednog tipa, i par drugog tipa. Dalje, poklapa se sa mnogim algoritmima vezanim za stabla, koji se sastoje od toga da se radi jedna stvar sa vrednostima, a druga sa decom.

Ova uzajamno rekurzivna definicija se može napisati i kao rekurzivna definicija umetanjem definicije šume:

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

Stablo t se sastoji od para vrednosti v i liste stabala (njegove dece). Ova definicija je kompaktnija, ali je malo prljavija: drvo se sastoji od para jednog tipa i liste drugog, što zahteva otpetljavanje kako bi se dokazala korektnost.

U ML standardu, stablo i šuma mogu biti uzajamno rekurzivno definisani na sledeći način, dozvoljavajući prazna stabla:

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

Računarske funkcije

Kao što algoritmi rekurzivnih tipova podataka mogu prirodno biti predstavljeni rekurzivnim funkcijama, tako i algoritmi uzajamno rekurzivnih tipova podataka mogu biti prirodno predstavljeni uzajamno rekurzivnim funkcijama. Zajednički primeri uključuju algoritme sa stablima, i analizatorima rekurzivnog spusta. Kao i kod direktne rekurzije, repna rekurzija je nepohodna ukoliko je dubina rekurzije velika ili neograničena, kao kada se koristi uzajamna rekurzija za multitasking. Optimizacija repnom rekurzijom generalno (kada funkcija koja se zove nije ista kao originalna funkcija, kao u repno-rekurzivnim pozivima) može biti teža za implementaciju od specijalnog slučaja optimizacije repnom rekurzijom, i tako efikasnost implementacije uzajamno repne rekurzije može biti odsutna u jezicima koji optimizuju samo repno-rekurzivne pozive. U jezicima kao što je Paskal to zahteva deklaraciju pre upotrebe, uzajamno rekurzivne funkcije zahtevaju deklaraciju unapred.

Kao i kod direktno rekurzivnih funkcija omotač funkcija može biti korisna sa uzajamno rekurzivnim funkcijama definisanim kao ugnježdenim funkcijama u okviru svog polja rada ukoliko je ovo podržano. Ovo je posebno korisno za deljenje stanja između seta funkcija bez prosleđivanja parametara među njima.

Osnovni primeri

Osnovni primer uzajamne rekurzije, koji je doduše veštački, je određivanje da li je nenegativan broj paran ili neparan koristeći dve odvojene funkcije koje pozivaju jedna drugu, smanjujući vrednost argumenta svaki put. U programskom jeziku S:

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);
}

Ove funkcije se baziraju na zapažanju da je pitanje Da li je 4 parno? ekvivalentno pitanju Da li je 3 neparno?, što je ekvivalentno sa Da li je 2 parno?, i sve tako do 0. Ovaj primer se lako može zapisati i iterativno. U ovom slučaju su uzajamno rekurzivni pozivi repno-rekurzivni, i optimizacija repno-rekurzivnih poziva bi bila neophodna kako bi izvršavanje moglo da bude u konstantnom broju stek okvira; u S-u bi to bilo O(n) stek okvira, osim ukoliko bi se koristili skokovi umesto poziva. . Ovo bi moglo da se svede na jednu rekurzivnu funkciju is_even, gde bi is_odd pozivala is_even, ali bi is_even pozivala samo samu sebe umesto funkcije is_odd.

Kao mnogo opštija klasa primera, jedan algoritam za stablo bi mogao da se podeli na njegova ponašanja za vrednosti i ponašanja za decu, i može biti podeljen u dve uzajamno rekurzivne funkcije, jedna koja precizira ponašanje stabla , pozivajući forest funkciju za šumu dece, i jedna koja precizira ponašanje funkcije forest, pozivajući funkciju tree za stablo unutar šume. U programskom jeziku 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 ovom slučaju funkcija f_tree poziva funkciju f_forest rekurzivno, ali funkcija f_forest poziva funkciju f_tree koristeći višestruku rekurziju.

Koristeći Standard ML tipove podataka, veličina stabla (broj čvorova) može biti izračunata koristeći sledeće uzajamno rekurzivne funkcije.

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'

Detaljniji primer u shemi, koji računa broj listova stabla:

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

Ovi primeri se lako svode na običnu rekurziju tako što se forest funkcija inlajnuje u tree funkciju, što se često radi u praksi: direktno rekurzivne funkcije koje rade sa stablima redom obrađuju vrednost čvora i rekurzivno rade sa decom u jednoj funkciji, ne razdvajajući ovo u dve odvojene funkcije.

Napredni primeri

Komplikovaniji primeri su vezani za rekurzivno spuštajuće parsere, koji prirodno mogu da budu implementirani pomoću jedne funkcije za svako pravilo izrade gramatike, koje se posle pozivaju uzajamno rekurzivno; ovo bi generalno bila višestruka rekurzija, pošto pravila izrade kombinuju više delova. Ovo takođe može biti urađeno i bez uzajamne rekurzije, i dalje imajući odvojene funkcije za svako pravilo izrade, ali koje poziva jedna funkcija, ili stvljajući svu gramatiku u jednu funkciju.

Uzajamna rekurzija takođe može služiti za implemenatciju konačnih automata, sa po jednom funkcijom za svako stanje, i jednom rekurzijom za promenu stanja; ovo zahteva optimizaciju repnom rekurzijom ukoliko je broj promena stanja veliki ili neograničen. Ovo se može koristiti kao jednostavni oblik kooperativnog multitaskinga. Sličan pristup multitaskingu može biti sledeci: umesto da se koriste ko-rutine koje pozivaju jedne druge, jedna ko-rutina poziva drugu bez završetka rada, već nastavlja izvršavanje, nakon završetka poziva druge. Ovo omogućava pojedinačnim ko-rutinama da zadrže stanje, bez potrebe da budu prosleđene parametrima ili sačuvane u zajedničkim promenljivama.

Postoje algoritmi koji se sastoje iz dve faze, kao minimaks (min i max), i oni mogu biti implementirani tako što se svaka faza izvršava u zasebnoj funkciji pomoću uzajamne rekurzije, iako mogu biti u jednoj funkciji koja je direktno rekurzivna.

Rasprostranjenost

Uzajamna rekurzija je veoma česta u funkcionalnom programiranju, a često se koristi za programe pisane u jezicima LISP, Scheme, ML. U jezicima kao što su Prolog, uzajamna rekurzija je skoro neizbežna.

Neki stilovi programiranja obeshrabruju upotrebu uzajamne rekurzije, tvrdeći da to može biti zbunjujuće za razlikovanje uslova koji će vratiti odgovor od uslova koji će omogućiti kodu da radi zauvek bez davanja ikakvog odgovora. Piter Norvig ukazuje na obrazac dizajna koji obeshrabruje korišćenje potpuno, sa naznakom:

Ako imate dve uzajamno rekurzivne funkcije gde obe menjaju stanje objekta, pokušajte da premestite gotovo sve funkcionalnosti u samo jednu od funkcija. U suprotnom ćete verovatno samo duplirati kod.

Terminologija

Uzajamna rekurzija je takođe poznata kao indirektna rekurzija, za razliku od direktne rekurzije, gde jedna funkcija poziva sama sebe direktno. Pojam "indirektna rekurzija" naglašava individualnu funkciju, dok "uzajamna rekurzija" naglašava skup funkcija, a ne izdvaja jednu funkciju. Na primer, ako f zove sama sebe, to je direktna rekurzija. Ako umesto toga, f poziva g a zatim g poziva f, što dalje ponovo poziva g, sa tačke gledišta same funkcije f, f je indirektno rekurzivna, dok sa tačke gledišta same funkcije g, g je indirektno rekurzivna, dok sa tačke gledišta gledište obe, f i g su međusobno uzajamno rekurzivne. Slično skup tri ili više funkcija koje pozivaju jedne druge može se nazvati skupom uzajamno rekurzivnih funkcija.

Konverzija u direktnu rekurziju

Matematički, skup uzajamno rekurzivnih funkcija su primitivne rekurzije, što se može dokazati, gradeći jedinstvenu funkciju F koja beleži vrednosti pojedinačnih rekurzivnih funkcija:$F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,$ i prepisujući uzajamne rekurzije kao primitivne rekurzije.

Svaka uzajamna rekurzija između dve procedure može biti konvertovana u direktnu rekurziju inlajnovanjem koda jedne procedure u drugu. Ako postoji samo jedno mesto gde jedna procedura poziva drugu, ovo je jednostavno, ali ako ih ima više može doći do dupliranja koda. U terminima steka poziva, dva uzajamno rekurzivne procedure daju stek ABABAB..., i umetanjem B u А dobijamo direktnu rekurziju (АВ) (АВ) (АВ) ...

Alternativno, bilo koji broj procedura može da se spoji u jednu proceduru koja uzima kao argument varijantu zapisa (ili algebarski tip podataka) koja predstavlja izbor procedure i njenih argumenata; spojena procedura onda pošalje svom argumentu da izvrši odgovarajući kod i koristi direktnu rekurziju da pozove sebe. Ovo se može posmatrati kao ograničena primena defunkcionalizacije. Ovaj prevod možda može biti koristan kada neke od uzajamno rekurzivnih procedura mogu biti pozvane iz spoljašnjeg koda, tako da ne postoji očigledan slučaj za umetanje jedne procedure u drugu. Takav kod onda mora da se promeni, tako da se pozivi procedure dobijaju objedinjavanjem argumenata u varijanti zapisa kao što je opisano; naizmenično, procedure omotači mogu da se koriste za ovaj zadatak.

Vidi još

• Rekurzija (kompjuterske nauke)

Literatura

• Harper, Robert (2000), Programming in Standard ML 
• Harvey, Brian; Wright, Matthew (1999). Simply Scheme: Introducing Computer Science. MIT Press. ISBN 978-0-26208281-5. 
• Hutton, Graham (2007). Programming in Haskell. Cambridge University Press. ISBN 978-0-52169269-4. 

Spoljašnje veze

• Mutual recursion at Rosetta Code
• "Example demonstrating good use of mutual recursion"
• "Are there any example of Mutual recursion?", Stack Overflow