Кіріспе

Өзін-өзі шақыратын функцияларды пайдалану

Компьютерлік ғылымда рекурсия – бұл шешімі сол мәселенің кішірек мысалдарының шешімдеріне байланысты болатын есептеу мәселесін шешу әдісі. Рекурсия мұндай рекурсивті мәселелерді өз кодын ішінде өзін-өзі шақыратын функцияларды пайдалану арқылы шешеді. Бұл тәсілді көптеген мәселелерге қолдануға болады, және рекурсия – компьютерлік ғылымның орталық идеяларының бірі. Көптеген компьютерлік бағдарламалау тілдері функциялардың өз кодтарының ішінде өздерін шақыруына мүмкіндік беру арқылы рекурсияны қолдайды. Кейбір функционалдық бағдарламалау тілдері (мысалы, Clojure) ешқандай циклдық конструкцияны анықтамайды, бірақ кодты қайта-қайта шақыру үшін тек рекурсияға сүйенеді. Есептеуге қабілеттілік теориясында осы рекурсивті тілдердің Тьюринг толық екендігі дәлелденген; бұл олардың императивті тілдер сияқты қуатты екендігін (оларды бірдей мәселелерді шешу үшін қолдануға болады) білдіреді. Өзін-өзі ішінде қайта-қайта шақыру функциясы шақыру стегінің мөлшері барлық шақырулардың кіріс мөлшерлерінің қосындысына тең болуына себеп болуы мүмкін. Одан кейін, итерация арқылы оңай шешілетін мәселелер үшін рекурсия әдетте тиімділігі төмен болады, ал кейбір мәселелер үшін құйрық шақыруды оңтайландыру сияқты алгоритмдік немесе компиляторды оңтайландыру әдістері қарапайым рекурсивті іске асырудан есептеу өнімділігін жақсарта алады.

Рекурсивті функциялар мен алгоритмдер

Алгоритмдерді жобалаудың кең таралған тәсілі – мәселені бастапқы мәселеге ұқсас кіші мәселелерге бөлу, оларды шешу және нәтижелерді біріктіру болып табылады. Бұл көбінесе "бөліп-бас иелену" әдісі деп аталады; егер бұрын шешілген кіші мәселелердің нәтижелерін сақтайтын іздеу кестесімен қолданылса (оларды қайта-қайта шешуден және артық есептеу уақытын жұмсаудан сақтау үшін), онда бұл динамикалық бағдарламалау немесе жадқа сақтау (мемоизация) деп аталады.

Негізгі жағдай

Рекурсивті функцияның анықтамасында бір немесе бірнеше базалық жағдай болады, яғни функция нәтижені тривиальды түрде (қайта шақырылмай) шығаратын кіріс(тер), сондай-ақ бір немесе бірнеше рекурсивті жағдай болады, яғни бағдарламаның өзін қайта шақыратын кіріс(тер). Мысалы, факториал функциясы 1=0! = 1 және барлық n > 0 үшін 1=n! = n(n − 1)! теңдеулері арқылы рекурсивті түрде анықталуы мүмкін. Екі теңдеудің ешқайсысы жеке-жеке толық анықтаманы құрамайды; біріншісі – базалық жағдай, ал екіншісі – рекурсивті жағдай. Базалық жағдай рекурсия тізбегін үзеді, сондықтан оны кейде «аяқтау жағдайы» деп те атайды. Рекурсивті жағдайлардың міндеті күрделі кірістерді қарапайымдауға айналдыру болып табылады. Дұрыс жобаланған рекурсивті функцияда, әрбір рекурсивті шақырумен кіріс мәселесі солайша қарапайымдалуы керек, әрі қарай базалық жағдайға жетуге болады. (Қалыпты жағдайларда аяқталмауы тиіс функциялар – мысалы, кейбір жүйелік және серверлік процестер – бұл ережеден тыс). Базалық жағдайды жазуды ұмыту немесе оны дұрыс тексермеу шексіз циклға алып келуі мүмкін. Кейбір функциялар үшін (мысалы, 1=[[e (математикалық тұрақты)] үшін қатарды есептейтін функциялар үшін) кіріс деректерімен түсіндірілген нақты базалық жағдай болмайды; мұндай жағдайларда базалық жағдайды белгілейтін «тоқтату критерийін» ұсыну үшін параметр (мысалы, біздің қатарлы мысалымызда қосылатын мүшелер саны) қосуға болады. Мұндай мысалға көбірек табиғи түрде ко-рекурсия арқылы қарастырылады, онда шығыстағы тізбекті мүшелер ішінара сомалар болып табылады; оны «n-ші мүшені (n-ші ішінара соманы) есептеңіз» деп айту үшін индекстеу параметрін пайдалану арқылы рекурсияға айналдыруға болады.

Рекурсивті дерек түрлері

Көптеген компьютерлік бағдарламалар шексіз үлкен көлемдегі деректерді өңдеуге немесе жасауға міндетті. Рекурсия – бағдарламашыға деректің нақты көлемі белгісіз болған жағдайда оны бейнелеу тәсілі болып табылады: бағдарламашы осы деректі өзіне сілтеме жасайтын анықтама арқылы сипаттай алады. Өзіне сілтеме жасайтын анықтамалардың екі түрі бар: индуктивті және коиндуктивті анықтамалар.

Бір рекурсия және бірнеше рекурсия

Тек бір ғана өзіндік сілтемесі бар рекурсия бір рекурсия деп аталады, ал бірнеше өзіндік сілтемесі бар рекурсия бірнеше рекурсия деп аталады. Бір рекурсияның стандартты мысалдары тізімді аралау, мысалы сызықтық іздеу, немесе факториал функциясын есептеуді қамтиды, ал бірнеше рекурсияның стандартты мысалдары, мысалы тереңдікке бірінші іздеуде, ағаш аралауды қамтиды. Бір рекурсия көбінесе бірнеше рекурсияға қарағанда тиімдірек болады және оны, әдетте, сызықтық уақытта орындалатын және тұрақты кеңістік қажет ететін итеративтік есептеумен алмастыруға болады. Көп рекурсия, керісінше, экспоненциалды уақыт пен кеңістік талап етуі мүмкін және ол негізінен рекурсивті болып табылады, оны нақты стексіз итерациямен алмастыру мүмкін емес. Бірнеше рекурсияны кейде бір рекурсияға (жақсырақ болса, содан кейін итерацияға) түрлендіруге болады. Мысалы, Фибоначчи тізбегін есептеуде әр мәнге екі алдыңғы мән қажет болғандықтан бірнеше итерация қажет, бірақ оны екі тікелей мәнді параметр ретінде жіберу арқылы бір рекурсия арқылы есептеуге болады. Бұл бастапқы мәндерден құрылатын және әр қадамда екі тікелей мәнді қадағалайтын corecursion ретінде табиғи түрде бейнеленеді. Күрделірек мысал – итеративтік ағаш аралауды қамтамасыз ететін, тігілген екілік ағашты пайдалану.

Тікелей емес рекурсия

Рекурсияның ең қарапайым мысалдары, және осы жерде ұсынылған мысалдардың көпшілігі, функцияның өзін-өзі шақыруымен тікелей рекурсияны көрсетеді. Тікелей емес рекурсия функцияны өзі емес, оның шақырған басқа функция шақырғанда (тікелей немесе жанама жолмен) пайда болады. Мысалы, егер f функциясы f функциясын шақырса, онда бұл тікелей рекурсия, бірақ егер f функциясы g функциясын шақырса, ал g функциясы f функциясын шақырса, онда бұл f функциясының жанама рекурсиясы болып табылады. Үш немесе одан да көп функциядан тұратын тізбектер де болуы мүмкін; мысалы, 1-функция 2-функцияны шақырады, 2-функция 3-функцияны шақырады, ал 3-функция қайтадан 1-функцияны шақырады. Жанама рекурсияны өзара рекурсия деп те атайды, бұл көбірек симметриялы термин, бірақ бұл әртүрлі ұғым емес, тек баса назар аударудағы айырмашылық. Яғни, егер f функциясы g функциясын шақырса, содан кейін g функциясы f функциясын шақырса, ол өз кезегінде g функциясын қайта шақырса, f функциясының тұрғысынан алғанда, f жанама түрде рекурсияланып отыр, ал g функциясының тұрғысынан алғанда, ол жанама түрде рекурсияланып отыр, ал екеуінің тұрғысынан алғанда, f және g функциялары бір-біріне өзара рекурсияланып отыр. Сол сияқты, бір-бірін шақыратын үш немесе одан да көп функциялар жиынтығын өзара рекурсивті функциялар жиынтығы деп атауға болады.

Анонимді рекурсия

Рекурсия көбінесе функцияны аты бойынша нақты шақыру арқылы жасалады. Дегенмен, рекурсияны ағымдағы контекстке сүйене отырып, функцияны жасырын түрде шақыру арқылы да жүзеге асыруға болады, бұл анонимді функциялар үшін ерекше пайдалы және анонимді рекурсия деп аталады.

Қаптаманың қызметі

Wrapper функциясы - тікелей шақырылатын, бірақ өзін рекурсиялық түрде шақырмайтын, керісінше рекурсияны жүзеге асыратын жеке көмекші функцияны шақыратын функция. Wrapper функцияларын параметрлерді тексеру үшін (сол арқылы рекурсивті функция оларды жіберіп алғанын), инициализация жасау үшін (жадты бөлу, айнымалыларды бастамалау), әсіресе "рекурсия деңгейі" сияқты қосалқы айнымалылар немесе жадқа сақтау үшін ішінара есептеулер үшін, сондай-ақ ерекше жағдайларды және қателерді басқару үшін қолдануға болады. Ішкі функцияларды қолдайтын тілдерде көмекші функция wrapper функцияның ішінде орналастырылып, ортақ кеңістікті пайдалана алады. Ішкі функциялар болмаған жағдайда, көмекші функциялар жеке функция ретінде жасалады (мүмкіндігі болса, тікелей шақырылмайтындықтан) және ақпарат wrapper функциясымен сілтеме арқылы беріледі.

Гибридті алгоритм

Рекурсивті алгоритмдер кішкентай деректер үшін жиі тиімсіз болады, себебі қайта-қайта функция шақырулар мен қайтарулардың қосымша шығындары болады. Сондықтан рекурсивті алгоритмдерді тиімді іске асыру көбінесе рекурсивті алгоритммен басталады, бірақ кіріс дерек көлемі кішкентай болғанда басқа алгоритмге ауысады. Маңызды мысал – біріктіру сұрыптау, ол деректер жеткілікті кішкентай болғанда рекурсивті емес енгізу сұрыптауға ауысу арқылы іске асырылады, мысалы, плиткалы біріктіру сұрыптауында. Гибридтік рекурсивті алгоритмдерді одан әрі жетілдіруге болады, мысалы, гибридтік біріктіру/енгізу сұрыптауынан туындаған Timsort алгоритмі.

Экспрессивтік күш

Қазіргі кезде қолданылып жүрген бағдарламалау тілдерінің көпшілігі рекурсивті функциялар мен процедураларды тікелей анықтауға мүмкіндік береді. Мұндай функция шақырылғанда, бағдарламаның орындалу ортасы функцияның әртүрлі мысалдарының жағдайын қадағалайды (көбінесе шақыру стегін пайдаланады, бірақ басқа әдістер де қолданылуы мүмкін). Кез келген рекурсивті функцияны рекурсивті шақыруларды итеративті басқару құрылымдарымен алмастыру және шақыру стегін бағдарламамен тікелей басқарылатын стек арқылы модельдеу арқылы итеративті функцияға түрлендіруге болады. Керісінше, компьютермен есептелуге болатын барлық итеративті функциялар мен процедураларды (Тьюринг толықтығын қараңыз) рекурсивті функциялар арқылы көрсетуге болады; while және for циклдары сияқты итеративті басқару құрылымдары функционалдық тілдерде рекурсивті нысанда жиі қайта жазылады. Дегенмен, практикада мұндай қайта жазу құйрық шақыруды жоюға байланысты, ол барлық тілдерде де қолдау көрсетілмейді. C, Java және Python – бұл барлық функциялық шақыруларды, соның ішінде құйрық шақыруларды, циклдік құрылымдарды пайдаланғанда қажет болмайтын стекке жад бөлуге себеп болатын кең таралған тілдер; осы тілдерде рекурсивті нысанда қайта жазылған жұмыс істейтін итеративті бағдарлама шақыру стегінің сыйымдылығын асып кетуі мүмкін, бірақ құйрық шақыруды жою тілдің сипаттамасында көрсетілмеген мүмкіндік болуы мүмкін, сондай-ақ бір тілдің әртүрлі нұсқалары құйрық шақыруды жою қабілеттері бойынша өзгеше болуы мүмкін.

Орындау мәселелері

Итеративті циклдық конструкцияларды қолдайтын тілдерде (мысалы, C және Java), рекурсивті бағдарламалар көбінесе уақыт және жад ресурстарын көп жұмсайды, себебі стекті басқаруға қосымша шығындар кетеді және функцияны шақыру салыстырмалы түрде баяу болады. Ал функционалдық тілдерде функцияны шақыру (әсіресе, соңғы шақыру) әдетте өте жылдам операция болып табылады, сондықтан айырмашылық көбінесе байқалмайды. Мысалы, жоғарыда келтірілген "факториал" мысалының рекурсивті және итеративті түрде іске асырылуы арасындағы өнімділік айырмашылығы қолданылған компиляторға тікелей байланысты. Циклдық конструкцияларға басымдық берілген тілдерде итеративті нұсқа рекурсивті нұсқадан бірнеше есе жылдам болуы мүмкін. Функционалдық тілдерде екі нұсқаның арасындағы жалпы уақыт айырмашылығы мардымсыз болуы мүмкін; тіпті, кішкентай сандарды емес, үлкен сандарды бірінші көбейтуге кеткен уақыт (осы жердегі итеративті нұсқа осылай істейді) итерацияны таңдау арқылы үнемделген уақыттан асып түсуі мүмкін.

Қорытынды кеңістік

Кейбір бағдарламалау тілдерінде шақыру стегінің ең үлкен мөлшері үйіндідегі бос орыннан әлдеқайда аз, ал рекурсивті алгоритмдер итеративті алгоритмдерге қарағанда көбірек стек кеңістігін қажет етеді. Сондықтан, мұндай тілдер стек ағынынан сақтану үшін рекурсия тереңдігіне шектеу қоюы мүмкін; Python осындай тілдердің бірі. Құйрық рекурсиясының ерекше жағдайына қатысты төмендегі ескертуге назар аударыңыз.

Қауіптілік

Рекурсивті алгоритмдер стек ағынына ұшырауы мүмкін болғандықтан, олар патологиялық немесе қасақана жасалған кіріске осал болуы мүмкін. Кейбір зиянды бағдарламалар бағдарламаның шақыру стегіне бағытталды және стектің табиғатындағы рекурсиядан пайдаланады. Зыянды бағдарламалардың болмауына қарамастан, шексіз рекурсия нәтижесінде туындаған стек ағыны бағдарлама үшін өлімге алып келуі мүмкін, ал қателіктерді өңдеу логикасы тиісті процестің тоқтатылуын болдырмауы мүмкін.

Қайталанатын көбейту проблемалары

Көп рекурсивті мәселелер бұрынғы күйін қадағалау қажеттілігінен туындайтын өзінен-өзі рекурсивті болып келеді. Мысалы, тереңдікке бірінші іздеу сияқты ағаш бойынша жүріп өту; рекурсивті де, итеративтік әдістер де қолданылса да, олар тізімдегі элементтерді қарау және сызықтық іздеумен салыстырылады, бұл бір реттік рекурсия және осылайша табиғи түрде итеративтік әдіс. Басқа мысалдарға Quicksort сияқты «бөліп талқандау» алгоритмдері және Аккерман функциясы жатады. Бұл алгоритмдердің бәрін нақты стек көмегімен итеративті түрде жүзеге асыруға болады, бірақ стекпен жұмыс істеуге жұмсалатын бағдарламашының күші және нәтижедегі бағдарламаның күрделілігі итеративті шешімнің кез келген артықшылығынан басым болуы мүмкін.

Рефакторингтік рекурсия

Рекурсивті алгоритмдерді рекурсивті емес баламаларымен алмастыруға болады. Рекурсивті алгоритмдерді алмастырудың бір жолы – оларды стек жадының орнына үйінді жадыны қолдану арқылы модельдеу. Басқа нұсқа – толығымен рекурсивті емес әдістерге негізделген алмастыру алгоритмін жасау, бұл қиындық тудыруы мүмкін. Мысалы, Рич Салцтың wildmat алгоритмі сияқты, жабайы символдарды сәйкестендіруге арналған рекурсивті алгоритмдер бұрын кең таралған болатын. Осы мақсатқа арналған Краустың жабайы символдарды сәйкестендіру алгоритмі сияқты рекурсивті емес алгоритмдер рекурсияның кемшіліктерінен құтылу үшін жасалды және тек тесттерді жинау және өнімділікті бағалау сияқты техникаларға негізделіп, біртіндеп жақсартылды.