Кіріспе

Өзін-өзі ұқсас түрде қайталау процесі

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

Бейресми анықтама

Рекурсия – процедураның бір қадамы өзінің өзін шақыруын қамтитын жағдайда жүзеге асылатын процесс. Мұндай рекурсияға түсетін процедура «рекурсивті» деп аталады. Рекурсияны түсіну үшін процедура мен оның іске қосылуы арасындағы айырмашылықты білу қажет. Процедура – белгілі бір ережелерге негізделген қадамдар жиынтығы, ал процедураны іске қосу – осы ережелерді орындау және қадамдарды жүзеге асыру процесі. Рекурсия, процедураның сипаттамасында басқа процедураны іске қосуға жасалған сілтемемен байланысты болғанымен, олардан ерекшеленеді. Егер процедура осылай анықталса, дереу шексіз цикл туындауы мүмкін; рекурсияны анықтамада тек қана дұрыс пайдалануға болады, егер белгілі бір жағдайларда осы қадам орындалмай, процедура аяқталуы мүмкін болса. Дұрыс анықталғанның өзінде, рекурсивті процедураны адамдарға орындау қиын, себебі ол жаңа және бұрынғы, ішінара орындалған процедура шақыруларын ажыратуды талап етеді; бұл процедураның бірнеше бірдей нұсқасының қаншалықты орындалғанын қадағалауды қажет етеді. Осы себепті, рекурсивті анықтамалар күнделікті жағдайларда сирек кездеседі.

Тіл бойынша

Лингвист Ноам Чомский, сондай-ақ көптеген басқалар, тілдегі грамматикалық сөйлемдер санының жоғарғы шегінің болмауы және грамматикалық сөйлем ұзындығының жоғарғы шегінің болмауы (бір сөйлемді айтуға жұмсалатын уақыт сияқты нақты шектеулерден басқа) табиғи тілдегі рекурсияның салдары ретінде түсіндірілуі мүмкін деп санайды. Бұл синтаксистік категорияның, мысалы, сөйлемнің рекурсивті анықтамасы тұрғысынан түсіндіріледі. Сөйлемде етістіктен кейін басқа сөйлем келетін құрылым болуы мүмкін: «Дороти сиқыршыларды қауіпті деп ойлайды», онда «сиқыршыларды қауіпті» деген сөйлем үлкен сөйлемнің құрамында кездеседі. Осылайша, сөйлемді рекурсивті түрде (шамамен) есімдік топ, етістік және міндетті түрде басқа сөйлемді қамтитын құрылым ретінде анықтауға болады. Бұл математикалық рекурсияның ерекше жағдайы. Бұл тілдің шығармашылығын – грамматикалық сөйлемдердің шексіз санын түсінуге мүмкіндік береді, себебі ол сөйлемдердің кез келген ұзындықта болуы мүмкін екенін көрсетеді: «Дороти Тотоның Tin Man-ге айтқан сөзін күдіктенеді». Сонымен қатар, сөйлемдерден басқа да көптеген құрылымдарды рекурсивті түрде анықтауға болады, демек, сөйлемнің құрамында бір категорияның мысалдары екінші категорияның ішіне енуінің көптеген жолдары бар. Жылдар бойы тілдер осы сияқты талдауларға бейімделген. Рекурсияның адам тілінің маңызды қасиеті екені туралы қалыптасқан пікірді Дэниел Эверетт Пираха тіліне қатысты мәлімдемелері арқылы сынға алды. Эндрю Невинс, Дэвид Песетский және Силен Родригес оған қарсы пікір білдірген көптеген ғалымдардың қатарында. Әдеби өзіне сілтеу жасау математикалық немесе логикалық рекурсиядан өзгеше болуы мүмкін. Рекурсия тек синтаксисте ғана емес, сонымен қатар табиғи тілдің семантикасында да маңызды рөл атқарады. Мысалы, «және» сөзін жаңа сөйлемдер жасау үшін сөйлемдердің мағыналарына қолданылатын функция ретінде қарастыруға болады, сондай-ақ есімдік сөз тіркестерінің, етістік сөз тіркестерінің және басқаларының мағыналарына да қатысты. Бұл сондай-ақ транзитивті емес, транзитивті және дитранзитивті етістіктерге де қолданылуы мүмкін. Оған бір ғана мағына беру үшін, ол жеткілікті икемді болуы керек және әдетте осы әртүрлі мағыналарды аргумент ретінде қабылдай алады. Мұны сөйлемдерді біріктіретін қарапайым жағдай үшін анықтап, содан кейін басқа жағдайларды қарапайым жағдайға сүйене отырып рекурсивті түрде анықтау арқылы іске асыруға болады. Рекурсивті грамматика – рекурсивті өндіріс ережелерін қамтитын формальді грамматика.

Қайталанулы әзіл

Рекурсия кейде компьютерлік ғылым, бағдарламалау, философия немесе математика оқулықтарында әзіл ретінде қолданылады, әдетте дөңгелек анықтама немесе өзін-өзі сілтеме беру арқылы. Мұнда болжамды рекурсивті қадам базалық жағдайға жақындамайды, керісінше, шексіз регреске алып келеді. Мұндай кітаптардың сөздігінде көбінесе былай жазылады: Рекурсия – Рекурсияны қараңыз. Брайан Керниган мен Деннис Ричидің «С бағдарламалау тілі» кітабының кейбір басылымдарындағы индекс 269-бетте осыған ұқсас жазбаны ұсынады; индекс жазуы рекурсивті түрде өзіне сілтеме жасайды («рекурсия 86, 139, 141, 182, 202, 269»). Бұл әзілдің ерте нұсқаларын Лорен Сиклоссидің «Let's talk Lisp» (1975 жылдың 1 желтоқсанында Prentice Hall PTR баспасынан шыққан, авторлық құқығы 1976 жыл) және Керниган мен Плаугердің «Software Tools» (1976 жылдың 11 қаңтарында Addison Wesley Professional баспасынан шыққан) кітаптарында табуға болады. Бұл әзіл Керниган мен Пайктың «UNIX бағдарламалау ортасы» еңбегінде де кездеседі. Ол «С бағдарламалау тілінің» алғашқы басылымында болған жоқ. Бұл әзіл функционалдық бағдарламалау фольклорының бөлігі және жоғарыда аталған кітаптар жарыққа шықпас бұрын функционалдық бағдарламалау қауымдастығында кең таралған еді. Тағы бір әзіл: «Рекурсияны түсіну үшін рекурсияны түсіну қажет». Эндрю Плоткиннің ұсынған басқаша түрі: «Егер сіз рекурсияның мәнін білсеңіз, жауабын есте сақтаңыз. Әйтпесе, Дуглас Хофстадтерге сізден жақын тұрған адамды табыңыз, содан кейін одан рекурсия деген не екенін сұраңыз». Рекурсивті акронимдер де рекурсивті юмордың мысалы болып табылады. Мысалы, PHP – «PHP Hypertext Preprocessor», WINE – «WINE Is Not an Emulator», GNU – «GNU's Not Unix», ал SPARQL – «SPARQL Protocol and RDF Query Language» дегенді білдіреді.

Түпкілікті бөлініс қағидалары

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

Функционалдық рекурсия

Функция өзін-өзі пайдалана отырып рекурсивті түрде анықталуы мүмкін. Көрінетін мысал – Фибоначчи сандар тізбегі: F(n) = F(n − 1) + F(n − 2). Мұндай анықтаманың қолданыс табуы үшін, оны рекурсивті емес анықталған мәндерге келтіру қажет: осы жағдайда F(0) = 0 және F(1) = 1.

Рекурсивті анықтамалармен дәлелдеу

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

Рекурсивті оңтайландыру

Динамикалық бағдарламалау – көп кезеңді немесе көп қадамды оптимизация мәселесін рекурсивті түрде жаңадан формулирлейтін оптимизациялау әдісі. Динамикалық бағдарламалаудың негізгі нәтижесі – Беллман теңдеуі, ол оптимизация мәселесінің ертерек (немесе ертерек қадамдағы) мәнін кейінгі (немесе кейінгі қадамдағы) мәні арқылы көрсетеді.

Биологияда

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

Әлеуметтік ғылымдар

Авторлар рекурсивтілік тұжырымын әлеуметтік ғалымдар әлем туралы білім жасайтын кезде, олардың өзі де сол әлемнің бір бөлігі екенін ескеретін жағдайды баса көрсету үшін пайдаланады. Одри Алехандроның сөзіне сәйкес, “әлеуметтік ғалымдар ретінде біздің жағдайымыздың рекурсивтілігі біздің екі жақты рөлде болуымызбен байланысты: бір жағынан біз дискурстар арқылы талдау жасайтын субъектіміз, екінші жағынан біз өндіретін академиялық дискурстардың объектісіміз, себебі біз талдайтын әлемге қатысты әлеуметтік агенттерміз”. Осыған сүйене отырып, ол рекурсивтілікті эмансипациялық білімді өндірудегі маңызды қиындық деп санайды, бұл рефлексиялық күш-жігерді қажет етеді:

Бизнесте

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

Өнер саласында

Матреошка қуыршағы – рекурсивті концепцияның физикалық көркем үлгісі. Рекурсия 1320 жылы жасалған Джоттоның Стефанески триптихынан бері суреттерде қолданылып келеді. Оның орталық бөлігінде кардинал Стефанескидің тізе бүгіп, триптихті құрбандық ретінде ұстап тұрған бейнесі бейнеленген. Бұл тәжірибе көбінесе Дросте эффектісі деп аталады, ол Mise en abyme техникасының мысалы. М.С. Эшердің "Баспа галереясы" (1956) гравюрасы – бұрмаланған қаланың суретін бейнелейді, онда галерея суретті рекурсивті түрде қамтиды, және осылай шексіздікке дейін жалғасады.

Мәдениетте

Inception фильмі бір нәрсенің қайталануын әжуалы түрде көрсету үшін зат есімдерге "ception" жұрнағын қосуды қалыпты жағдайға жеткізді.