Рекурсія (лат.recursio) — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.
Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі.
Термін «рекурсія» використовується в різних спеціальних галузях знань — від лінгвістики до логіки, але найширше застосування знаходить у математиці та інформатиці. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення.
для всіх наступних чисел цього ряду кожне наступне є сумою двох попередніх, тобто для n>2, n-і число Фібоначчі дорівнює сумі (n-1)-го і (n-2)-го чисел Фібоначчі.
Трикутник Серпінського Практично всі геометричні фрактали задаються у формі нескінченної рекурсії (наприклад, трикутник Серпінського).
В одному з буддійських монастирів ченці вже тисячу років займаються перекладанням кілець. Вони розташовані трьома пірамідами, на яких нанизані кільця різних розмірів. У початковому стані 64 кільця були нанизані на першу піраміду й упорядковані по розміру. Ченці повинні перекласти всі кільця з першої піраміди на другу, виконуючи єдину умову — кільце не можна покласти на кільце меншого розміру. При перекладанні можна використовувати всі три піраміди. Ченці перекладають одне кільце за одну секунду. Як тільки вони закінчать свою роботу, наступить кінець світу.
Рекурсивний варіант розв'язку задачі:
Потрібно застосувати рекурсивно алгоритм, переклавши n-1 кільце з першої піраміди на третю піраміду. Потім зробити очевидний хід, переклавши останнє найбільше кільце з першої піраміди на другу. Потім знову застосувати рекурсію, переклавши n-1 кільце з третьої піраміди на другу піраміду.
У програмуванні рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного та/або такого, що виконується), реалізують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.
Варто уникати надлишкової глибини рекурсії, бо це може викликати переповнення стека викликів.
Рекурсія у фізиці
Два дзеркала відбиваються одне в одному створюючи нескінченний коридор
Класичним прикладом нескінченної рекурсії є два поставлені одне проти одного дзеркала: у них утворяться два коридори згасальних відображень дзеркал.
Іншим прикладом нескінченної рекурсії є ефект самозбудження (позитивного зворотного зв'язку) в електронних схемах посилення, коли сигнал з виходу попадає на вхід, підсилюється, знову попадає на вхід схеми і знову підсилюється. Підсилювачі, для яких такий режим роботи є штатним, називаються автогенератори.
Побутовий приклад (небажаного) самозбудження — свист у акустичних системах при завеликому підсиленні та/або невдалому розміщенні мікрофона відносно акустичних систем.
Яскравим прикладом явища рекурсії у природі є зовнішній вигляд капусти Романеско, яка має вигляд округлої піраміди, що формується з маленьких круглих пірамідок.
Кілька розповідей Станіслава Лема присвячені можливим казусам при нескінченній рекурсії:
Оповідання про Йона Тихого та сепульки («Зоряні щоденники Йона Тихого»), у якій герой послідовно переходить від статті про сепульки до статті про сепуляції, звідти до статті про сепулькарії, у якій знову міститься посилання на статтю «сепульки».
Оповідання про розумну машину, що мала достатній розум і лінь, щоб для розв'язання поставленої задачі побудувати собі подібну, і доручити розв'язування їй (підсумком стала нескінченна рекурсія, коли кожна нова машина будувала собі подібну і передавала задачу їй).
Російська народна казка-пісня «У попа була собака…» є прикладом рекурсії:
У попа була собака, він її любив
Вона з'їла шматок м'яса, він її убив
Убив і закопав,
А на могилі написав:
«У попа була собака, він її любив
Вона з'їла шматок м'яса, він її убив
Убив і закопав,
А на могилі написав:
«У попа була собака, він її любив
Вона з'їла шматок м'яса, він її убив
Убив і закопав,
А на могилі написав:
…
(лапки цитат ніколи не закриються)
Якщо в пошуковій системі Google ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі: рекурсія».
Література
Елементи математичної логіки та теорії рекурсії : навч. посіб. / М. Комарницький, В.Андрійчук , І.Мельник. – Львів : ЛНУ імені Івана Франка, 2013. – 282 с.
Примітки
Hunter, David (2011). . Jones and Bartlett. с. 494. Архів оригіналу за 1 квітня 2017. Процитовано 16 лютого 2016.
Ця стаття не містить . Ви можете допомогти поліпшити цю статтю, додавши посилання на . Матеріал без джерел може бути піддано сумніву та вилучено.(лютий 2013)
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її.
Rekursiya lat recursio metod viznachennya klasu chi ob yektu cherez poperednye zadannya odnogo chi dekilkoh zazvichaj prostih jogo bazovih vipadkiv chi metodiv a potim zadannyam na yihnij osnovi pravila pobudovi klasu yakij viznachayetsya Vizualna forma rekursiyi vidoma yak Efekt Droste Inshimi slovami rekursiya chastkove viznachennya ob yekta cherez sebe viznachennya ob yekta z vikoristannyam ranishe viznachenih Rekursiya vikoristovuyetsya koli mozhna vidiliti samopodibnist zadachi Termin rekursiya vikoristovuyetsya v riznih specialnih galuzyah znan vid lingvistiki do logiki ale najshirshe zastosuvannya znahodit u matematici ta informatici U matematici ta informatici rekursiya pov yazana z metodom viznachennya funkcij rekursivno zadana funkciya u svoyemu viznachenni mistit sebe zokrema rekursivnoyu ye funkciya zadana rekurentnoyu formuloyu Takim chinom mozhna odnim virazom dati neskinchennij nabir sposobiv obchislennya funkciyi viznachiti bezlich ob yektiv cherez samu sebe z vikoristannyam ranishe zadanih okremih viznachen Z rekursiyeyu tisno pov yazana matematichna indukciya vona ye prirodnim sposobom dovedennya vlastivostej funkcij na naturalnih chislah rekursivno zadanih cherez svoyi menshi znachennya Viznachennya u logici sho vikoristovuye rekursiyu nazivayetsya induktivnim div napriklad Naturalni chisla PrikladiMotrijka yak priklad rekursiyi Faktorial cilogo nevid yemnogo chisla n poznachayetsya n i viznachayetsya yak n n n 1 pri n gt 0 i n 1 pri n 0 Chisla Fibonachchi viznachayutsya za dopomogoyu rekursiyi pershe i druge chisla Fibonachchi rivni 1 dlya vsih nastupnih chisel cogo ryadu kozhne nastupne ye sumoyu dvoh poperednih tobto dlya n gt 2 n i chislo Fibonachchi dorivnyuye sumi n 1 go i n 2 go chisel Fibonachchi Trikutnik Serpinskogo Praktichno vsi geometrichni fraktali zadayutsya u formi neskinchennoyi rekursiyi napriklad trikutnik Serpinskogo Zadacha Hanojska vezha Yiyi zmistovna postanovka taka V odnomu z buddijskih monastiriv chenci vzhe tisyachu rokiv zajmayutsya perekladannyam kilec Voni roztashovani troma piramidami na yakih nanizani kilcya riznih rozmiriv U pochatkovomu stani 64 kilcya buli nanizani na pershu piramidu j uporyadkovani po rozmiru Chenci povinni pereklasti vsi kilcya z pershoyi piramidi na drugu vikonuyuchi yedinu umovu kilce ne mozhna poklasti na kilce menshogo rozmiru Pri perekladanni mozhna vikoristovuvati vsi tri piramidi Chenci perekladayut odne kilce za odnu sekundu Yak tilki voni zakinchat svoyu robotu nastupit kinec svitu Rekursivnij variant rozv yazku zadachi Potribno zastosuvati rekursivno algoritm pereklavshi n 1 kilce z pershoyi piramidi na tretyu piramidu Potim zrobiti ochevidnij hid pereklavshi ostannye najbilshe kilce z pershoyi piramidi na drugu Potim znovu zastosuvati rekursiyu pereklavshi n 1 kilce z tretoyi piramidi na drugu piramidu Rekursiya v programuvanniDokladnishe Rekursiya programuvannya U programuvanni rekursiya viklik pidprogrami funkciyi chi proceduri z neyi samoyi zvichajno z inshimi znachennyami vhidnih parametriv bezposeredno chi cherez inshi funkciyi napriklad funkciya A viklikaye funkciyu B a funkciya B funkciyu A Kilkist vkladenih viklikiv funkciyi chi proceduri nazivayetsya glibinoyu rekursiyi Mic rekursivnogo viznachennya ob yekta v tim sho take kinceve viznachennya zdatne opisuvati neskinchenno velike chislo ob yektiv Za dopomogoyu zh rekursivnoyi programi mozhlivo opisati neskinchenne obchislennya prichomu bez yavnih povtoren chastin programi Isnuye specialnij tip rekursiyi nazivanij hvostovoyu rekursiyeyu Interpretatori i kompilyatori funkcionalnih mov programuvannya sho pidtrimuyut optimizaciyu kodu vihidnogo ta abo takogo sho vikonuyetsya realizuyut hvostovu rekursiyu v obmezhenomu obsyazi pam yati za dopomogoyu iteracij Varto unikati nadlishkovoyi glibini rekursiyi bo ce mozhe viklikati perepovnennya steka viklikiv Rekursiya u fiziciDva dzerkala vidbivayutsya odne v odnomu stvoryuyuchi neskinchennij koridor Klasichnim prikladom neskinchennoyi rekursiyi ye dva postavleni odne proti odnogo dzerkala u nih utvoryatsya dva koridori zgasalnih vidobrazhen dzerkal Inshim prikladom neskinchennoyi rekursiyi ye efekt samozbudzhennya pozitivnogo zvorotnogo zv yazku v elektronnih shemah posilennya koli signal z vihodu popadaye na vhid pidsilyuyetsya znovu popadaye na vhid shemi i znovu pidsilyuyetsya Pidsilyuvachi dlya yakih takij rezhim roboti ye shtatnim nazivayutsya avtogeneratori Pobutovij priklad nebazhanogo samozbudzhennya svist u akustichnih sistemah pri zavelikomu pidsilenni ta abo nevdalomu rozmishenni mikrofona vidnosno akustichnih sistem Rekursiya u prirodiPriklad rekursiyi u prirodi kapusta Romanesko Yaskravim prikladom yavisha rekursiyi u prirodi ye zovnishnij viglyad kapusti Romanesko yaka maye viglyad okrugloyi piramidi sho formuyetsya z malenkih kruglih piramidok CitatiIteraciya vid lyudini Rekursiya vid Boga L Donald Knut Mistectvo programuvannya GumorBilshist vsih zhartiv pro rekursiyu stosuyetsya neskinchennoyi rekursiyi u yakij nemaye umovi vihodu Vidome vislovlennya Shob zrozumiti rekursiyu potribno spochatku zrozumiti rekursiyu Duzhe populyarnij zhart pro rekursiyu sho nagaduye slovnikovu stattyu rekursiya div rekursiya Kilka rozpovidej Stanislava Lema prisvyacheni mozhlivim kazusam pri neskinchennij rekursiyi Opovidannya pro Jona Tihogo ta sepulki Zoryani shodenniki Jona Tihogo u yakij geroj poslidovno perehodit vid statti pro sepulki do statti pro sepulyaciyi zvidti do statti pro sepulkariyi u yakij znovu mistitsya posilannya na stattyu sepulki Opovidannya pro rozumnu mashinu sho mala dostatnij rozum i lin shob dlya rozv yazannya postavlenoyi zadachi pobuduvati sobi podibnu i doruchiti rozv yazuvannya yij pidsumkom stala neskinchenna rekursiya koli kozhna nova mashina buduvala sobi podibnu i peredavala zadachu yij Rosijska narodna kazka pisnya U popa bula sobaka ye prikladom rekursiyi U popa bula sobaka vin yiyi lyubiv Vona z yila shmatok m yasa vin yiyi ubiv Ubiv i zakopav A na mogili napisav U popa bula sobaka vin yiyi lyubiv Vona z yila shmatok m yasa vin yiyi ubiv Ubiv i zakopav A na mogili napisav U popa bula sobaka vin yiyi lyubiv Vona z yila shmatok m yasa vin yiyi ubiv Ubiv i zakopav A na mogili napisav dd dd dd lapki citat nikoli ne zakriyutsya Yaksho v poshukovij sistemi Google vvesti zapit rekursiya to v poshukovij vidachi pobachite slova Mozhlivo vi mali na uvazi rekursiya LiteraturaElementi matematichnoyi logiki ta teoriyi rekursiyi navch posib M Komarnickij V Andrijchuk I Melnik Lviv LNU imeni Ivana Franka 2013 282 s PrimitkiHunter David 2011 Jones and Bartlett s 494 Arhiv originalu za 1 kvitnya 2017 Procitovano 16 lyutogo 2016 Div takozhPortal Matematika Korekursiya Miz an abim Fraktal Avtoreferenciya Nepredikativnist matematika Rekursivna procedura Rekursivni funkciyi vikoristovuyutsya v matematici zokrema v teoriyi algoritmiv dlya viznachennya klasu obchislyuvanih funkcij Universalni rekursivni funkciyi Iteraciya Teoriya obchislyuvanosti Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lyutij 2013 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi
Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
