Узајамна рекурзија

У математици и рачунарству, узајамна рекурзија је облик рекурзије где се две математичке или рачунарске функције или два објекта, дефинишу један преко другог. Узајамна рекурзија се често користи у функционалном програмирању и у неким проблематичним областима као што су анализатори рекурзивним спустом, где су типови података природно узајамно рекурзивни, али се ретко користи у другим областима.

Примери

Типови података:

Најважнији основни пример типова података који се може дефинисати узајамном рекурзијом је стабло, које може бити дефинисано узајамно рекурзивно у терминима шуме (листа стабала). Симболички:

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

t: v f

Шума f се састоји од листе стабала, док се стабло t састоји од парова вредности v и шуме f (своје деце). Ова дефиниција је елегантна и са њом се једноставно ради на апстрактном нивоу (као када се доказују теореме о особинама стабала), јер изражава стабло у једноставним терминима: листа једног типа, и пар другог типа. Даље, поклапа се са многим алгоритмима везаним за стабла, који се састоје од тога да се ради једна ствар са вредностима, а друга са децом.

Ова узајамно рекурзивна дефиниција се може написати и као рекурзивна дефиниција уметањем дефиниције шуме:

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

Стабло t се састоји од пара вредности v и листе стабала (његове деце). Ова дефиниција је компактнија, али је мало прљавија: дрво се састоји од пара једног типа и листе другог, што захтева отпетљавање како би се доказала коректност.

У ML стандарду, стабло и шума могу бити узајамно рекурзивно дефинисани на следећи начин, дозвољавајући празна стабла:

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

Рачунарске функције

Као што алгоритми рекурзивних типова података могу природно бити представљени рекурзивним функцијама, тако и алгоритми узајамно рекурзивних типова података могу бити природно представљени узајамно рекурзивним функцијама. Заједнички примери укључују алгоритме са стаблима, и анализаторима рекурзивног спуста. Као и код директне рекурзије, репна рекурзија је непоходна уколико је дубина рекурзије велика или неограничена, као када се користи узајамна рекурзија за мултитаскинг. Оптимизација репном рекурзијом генерално (када функција која се зове није иста као оригинална функција, као у репно-рекурзивним позивима) може бити тежа за имплементацију од специјалног случаја оптимизације репном рекурзијом, и тако ефикасност имплементације узајамно репне рекурзије може бити одсутна у језицима који оптимизују само репно-рекурзивне позиве. У језицима као што је Паскал то захтева декларацију пре употребе, узајамно рекурзивне функције захтевају декларацију унапред.

Као и код директно рекурзивних функција омотач функција може бити корисна са узајамно рекурзивним функцијама дефинисаним као угњежденим функцијама у оквиру свог поља рада уколико је ово подржано. Ово је посебно корисно за дељење стања између сета функција без прослеђивања параметара међу њима.

Основни примери

Основни пример узајамне рекурзије, који је додуше вештачки, је одређивање да ли је ненегативан број паран или непаран користећи две одвојене функције које позивају једна другу, смањујући вредност аргумента сваки пут. У програмском језику С:

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. Овај пример се лако може записати и итеративно. У овом случају су узајамно рекурзивни позиви репно-рекурзивни, и оптимизација репно-рекурзивних позива би била неопходна како би извршавање могло да буде у константном броју стек оквира; у С-у би то било O(n) стек оквира, осим уколико би се користили скокови уместо позива. . Ово би могло да се сведе на једну рекурзивну функцију is_even, где би is_odd позивала is_even, али би is_even позивала само саму себе уместо функције is_odd.

Као много општија класа примера, један алгоритам за стабло би могао да се подели на његова понашања за вредности и понашања за децу, и може бити подељен у две узајамно рекурзивне функције, једна која прецизира понашање стабла , позивајући forest функцију за шуму деце, и једна која прецизира понашање функције forest, позивајући функцију tree за стабло унутар шуме. У програмском језику Python:

 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

 def f_forest(forest):
     for tree in forest:
         f_tree(tree)

У овом случају функција f_tree позива функцију f_forest рекурзивно, али функција f_forest позива функцију f_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'

Детаљнији пример у схеми, који рачуна број листова стабла:

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

Ови примери се лако своде на обичну рекурзију тако што се forest функција инлајнује у tree функцију, што се често ради у пракси: директно рекурзивне функције које раде са стаблима редом обрађују вредност чвора и рекурзивно раде са децом у једној функцији, не раздвајајући ово у две одвојене функције.

Напредни примери

Компликованији примери су везани за рекурзивно спуштајуће парсере, који природно могу да буду имплементирани помоћу једне функције за свако правило израде граматике, које се после позивају узајамно рекурзивно; ово би генерално била вишеструка рекурзија, пошто правила израде комбинују више делова. Ово такође може бити урађено и без узајамне рекурзије, и даље имајући одвојене функције за свако правило израде, али које позива једна функција, или ствљајући сву граматику у једну функцију.

Узајамна рекурзија такође може служити за имплеменатцију коначних аутомата, са по једном функцијом за свако стање, и једном рекурзијом за промену стања; ово захтева оптимизацију репном рекурзијом уколико је број промена стања велики или неограничен. Ово се може користити као једноставни облик кооперативног мултитаскинга. Сличан приступ мултитаскингу може бити следеци: уместо да се користе ко-рутине које позивају једне друге, једна ко-рутина позива другу без завршетка рада, већ наставља извршавање, након завршетка позива друге. Ово омогућава појединачним ко-рутинама да задрже стање, без потребе да буду прослеђене параметрима или сачуване у заједничким променљивама.

Постоје алгоритми који се састоје из две фазе, као минимакс (min и max), и они могу бити имплементирани тако што се свака фаза извршава у засебној функцији помоћу узајамне рекурзије, иако могу бити у једној функцији која је директно рекурзивна.

Распрострањеност

Узајамна рекурзија је веома честа у функционалном програмирању, а често се користи за програме писане у језицима LISP, Scheme, ML. У језицима као што су Пролог, узајамна рекурзија је скоро неизбежна.

Неки стилови програмирања обесхрабрују употребу узајамне рекурзије, тврдећи да то може бити збуњујуће за разликовање услова који ће вратити одговор од услова који ће омогућити коду да ради заувек без давања икаквог одговора. Питер Норвиг указује на образац дизајна који обесхрабрује коришћење потпуно, са назнаком:

Ако имате двe узајамно рекурзивне функције где обе мењају стање објекта, покушајте да преместите готово све функционалности у само једну од функција. У супротном ћете вероватно само дуплирати код.

Терминологија

Узајамна рекурзија је такође позната као индиректна рекурзија, за разлику од директне рекурзије, где једна функција позива сама себе директно. Појам "индиректна рекурзија" наглашава индивидуалну функцију, док "узајамна рекурзија" наглашава скуп функција, а не издваја једну функцију. На пример, ако f зове сама себе, то је директна рекурзија. Ако уместо тога, f позива g а затим g позива f, што даље поново позива g, са тачке гледишта саме функције f, f је индиректно рекурзивна, док са тачке гледишта саме функције g, g је индиректно рекурзивна, док са тачке гледишта гледиште обе, f и g су међусобно узајамно рекурзивне. Слично скуп три или више функција које позивају једне друге може се назвати скупом узајамно рекурзивних функција.

Конверзија у директну рекурзију

Математички, скуп узајамно рекурзивних функција су примитивне рекурзије, што се може доказати, градећи јединствену функцију F која бележи вредности појединачних рекурзивних функција:$F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,$ и преписујући узајамне рекурзије као примитивне рекурзије.

Свака узајамна рекурзија између две процедуре може бити конвертована у директну рекурзију инлајновањем кода једне процедуре у другу. Ако постоји само једно место где једна процедура позива другу, ово је једноставно, али ако их има више може доћи до дуплирања кода. У терминима стека позива, два узајамно рекурзивне процедуре дају стек ABABAB..., и уметањем B у А добијамо директну рекурзију (АВ) (АВ) (АВ) ...

Алтернативно, било који број процедура може да се споји у једну процедуру која узима као аргумент варијанту записа (или алгебарски тип података) која представља избор процедуре и њених аргумената; спојена процедура онда пошаље свом аргументу да изврши одговарајући код и користи директну рекурзију да позове себе. Ово се може посматрати као ограничена примена дефункционализације. Овај превод можда може бити користан када неке од узајамно рекурзивних процедура могу бити позване из спољашњег кода, тако да не постоји очигледан случај за уметање једне процедуре у другу. Такав код онда мора да се промени, тако да се позиви процедуре добијају обједињавањем аргумената у варијанти записа као што је описано; наизменично, процедуре омотачи могу да се користе за овај задатак.

Види још

• Рекурзија (компјутерске науке)

Литература

• 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. 

Спољашње везе

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