Кіріспе

Бір-біріне анықталған екі функция.

Математика мен компьютерлік ғылымда өзара рекурсия – екі математикалық немесе есептеу нысаны, мысалы функциялар немесе дерек түрлері, бір-бірі арқылы анықталатын рекурсияның бір түрі. Өзара рекурсия функционалдық бағдарламалауда және кейбір мәселелер саласында, мысалы рекурсивті түсірілім талдағыштарында (parsers), онда дерек түрлері табиғи түрде өзара рекурсивті болып келеді, жиі кездеседі.

Компьютерлік функциялар

Рекурсивті деректер түрлеріндегі алгоритмдер рекурсивті функциялар арқылы табиғи түрде берілгендей, өзара рекурсивті деректер құрылымдарындағы алгоритмдер де өзара рекурсивті функциялар арқылы табиғи түрде беріледі. Көрінетін мысалдарға ағаштардағы алгоритмдер және рекурсивті түсірілім анализаторлары (parsers) жатады. Тікелей рекурсиядағыдай, рекурсия тереңдігі үлкен немесе шексіз болса, құйрық шақыруларын оңтайландыру қажет, мысалы, көп тапсырмалылық үшін өзара рекурсияны қолдануда. Жалпы құйрық шақыруларын оңтайландыру (шақырылған функция бастапқы функциядан өзгеше болғанда, құйрық рекурсивті шақырулардағыдай) құйрық рекурсивті шақыруларды оңтайландырудың арнайы жағдайына қарағанда жүзеге асыруы қиын болуы мүмкін, сондықтан өзара құйрық рекурсиясын тиімді жүзеге асыру, тек құйрық рекурсивті шақыруларды ғана оңтайландыратын тілдерде болмауы мүмкін. Паскаль сияқты, қолдану алдында декларациялауды талап ететін тілдерде, өзара рекурсивті функцияларға алдын ала декларациялау қажет, себебі оларды анықтағанда алға сілтеме жасаудан қашуға болмайды. Тікелей рекурсивті функциялар сияқты, орауыш функция (wrapper function) пайдалы болуы мүмкін, егер тіл қолдаса, өзара рекурсивті функциялар оның аумағындағы ішкі функциялар ретінде анықталады. Бұл, функциялар жиынтығында параметрлерді бір-біріне жібермей, жағдайды бөлісу үшін өте пайдалы.

Жоғары үлгілер

Күрделірек мысал рекурсивті түсу анализаторлары (parsers) арқылы беріледі, оларды грамматиканың әрбір өндіріс ережесі үшін бір функцияны қарастыру арқылы табиғи түрде жүзеге асыруға болады, содан кейін олар өзара рекурсияға түседі; әдетте, бұл көп рекурсия болады, себебі өндіріс ережелері көбінесе бірнеше бөлікті біріктіреді. Бұл өзара рекурсиясыз да іске асырылуы мүмкін, мысалы, әр өндіріс ережесі үшін жеке функцияларды сақтап, бірақ оларды бір басқарушы функция арқылы шақыру немесе барлық грамматиканы бір функцияға біріктіру арқылы. Өзара рекурсия сонымен қатар шекті күй машинасының (finite state machine) іске асыруын қамтамасыз етеді, әр күй үшін бір функция және күйді өзгерту кезінде бір рекурсия; егер күйлердің өзгеру саны көп немесе шексіз болса, бұл жағдайда құйрық шақыруларын оңтайландыру қажет. Бұл – кооперативтік көп тапсырмалылықтың (cooperative multitasking) қарапайым түрі. Көп тапсырмалылыққа ұқсас тәсіл – бір-бірін шақыратын корутиналарды (coroutines) пайдалану, онда бір корутина екіншісіне өту арқылы аяқталмайды, бірақ басқа ретті шақыру арқылы тоқтамай, орындауды қайта бастайды. Бұл жеке корутиналарға күйді сақтауға мүмкіндік береді, оны параметрлер арқылы берудің немесе ортақ айнымалыларда сақтаудың қажеті болмайды. Сонымен қатар, табиғи түрде екі фазадан тұратын, мысалы, минимакс (минималды және максималды) сияқты алгоритмдер бар, оларды әр фазаны жеке функцияда өзара рекурсия арқылы іске асыруға болады, бірақ оларды тікелей рекурсия арқылы бір функцияға біріктіруге де болады.

Математикалық функциялар

Математикада Хофштадтер әйел және ер адам тізбектері – бір-біріне рекурсивті түрде анықталған бүтін сандар тізбектерінің жұбына мысал. Фракталдарды рекурсивті функциялар арқылы (берілген ажыратымдылыққа дейін) есептеуге болады. Мұны кейде бір-біріне рекурсивті функциялар арқылы әлдеқайда ыңғайлырақ жасауға болады; Сиерпински қисығы осыған жақсы мысал.

Ауру таралуы

Өзара рекурсия функционалдық бағдарламалауда өте жиі кездеседі және LISP, Scheme, ML және ұқсас бағдарламалау тілдерінде жазылған бағдарламалар үшін көбінесе қолданылады. Мысалы, Абельсон мен Суссман LISP-ті eval apply циклы арқылы іске асыру үшін мета-циклді бағалаушының қалай қолданылатынын сипаттайды. Prolog сияқты тілдерде өзара рекурсиядан қашу мүмкін емес. Кейбір бағдарламалау стильдері өзара рекурсияны ұнатпайды, себебі ол жауап беретін жағдайларды, жауап бермей, мәңгілікке орындалуы мүмкін жағдайлардан ажыратуды қиындатады деп санайды. Питер Норвиг пайдалануды толығымен болдырмайтын дизайн үлгісіне сілтеме жасайды: text=Егер сізде бір-біріне рекурсивті шақыратын екі функция болса, және екеуі де объектінің күйін өзгертеді, онда барлық мүмкіндіктерді бір функцияға жылжытуға тырысыңыз. Әйтпесе, сіз кодты екі рет жазуға келуіңіз мүмкін.

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

Өзара рекурсия тікелей рекурсияға қарама-қарсы, бір функция өзін тікелей шақыратын, жанама рекурсия деп те аталады. Бұл тек қана баса назар салудың айырмашылығы, жаңа түсінік емес: "жанама рекурсия" жеке функцияны ерекшелейді, ал "өзара рекурсия" функциялар жиынтығына назар аударады және жеке функцияны бөліп көрсетпейді. Мысалы, егер f өзін өзі шақырса, ол тікелей рекурсия болады. Егер f, g-ді шақырса, содан кейін g, f-ты шақырса, ал f қайтадан g-ді шақырса, f тұрғысынан алғанда f жанама рекурсия жасайды, g тұрғысынан алғанда g жанама рекурсия жасайды, ал екеуінің тұрғысынан алғанда f және g бір-біріне өзара рекурсия жасайды. Сол сияқты, бір-бірін шақыратын үш немесе одан да көп функциялар жиынтығы өзара рекурсивті функциялар жиынтығы деп аталады.

Тікелей рекурсияға айналу

Математикалық тұрғыдан, өзара рекурсивті функциялар жиынтығы бастапқы рекурсивті болып табылады, бұл мәндердің рекурсиясы арқылы дәлелдеуге болады, жеке рекурсивті функциялардың мәндерін ретпен тізімдейтін F функциясын құрастыру арқылы: және өзара рекурсияны бастапқы рекурсия ретінде қайта жазу. Екі процедура арасындағы кез келген өзара рекурсияны бір процедураның кодын екіншісіне ендіру арқылы тікелей рекурсияға айналдыруға болады. Егер бір процедура екіншісін шақыратын бір ғана орын болса, бұл оңай, бірақ бірнеше орын болса, кодты қайталау қажет болуы мүмкін. Шақыру стегі тұрғысынан, екі өзара рекурсивті процедура ABABAB стегін тудырады, ал B-ді A-ға ендіру тікелей рекурсияны (AB)(AB)(AB) түрінде береді. Сонымен қатар, кез келген сандағы процедураларды бір процедураға біріктіруге болады, ол аргумент ретінде процедураның таңдалуын және оның аргументтерін көрсететін вариантты жазбаны (немесе алгебралық деректер типін) қабылдайды; біріктірілген процедура содан кейін тиісті кодты орындау үшін өз аргументі бойынша жіберіледі және қажет болған жағдайда өзін шақыру үшін тікелей рекурсияны қолданады. Бұл функцияларды жоюдың шектеулі қолданылуы ретінде қарастырылуы мүмкін. Бұл аударма өзара рекурсивті процедуралардың кез келгенін сыртқы код шақыруға болатын жағдайда пайдалы болуы мүмкін, сондықтан бір процедураны екіншісіне ендірудің анық себебі болмайды. Мұндай кодты кейін сипатталғандай аргументтерді вариантты жазбаға біріктіру арқылы процедура шақыруларын орындау үшін өзгерту қажет; немесе, бұл міндет үшін орауыш процедураларды пайдалануға болады.