В інформатиці, корекурсія — це операція двоїста до рекурсії. Тоді як рекурсія працює аналітично, починаючи з даних далеких від базового випадку, розбиває їх на менші шматки, і повторюється допоки не досягне базового випадку, корекурсія працює синтетично, починаючи з базового випадку і просувається ітеративно продукуючи дані далі віддалені від базового випадку. Просто кажучи, корекурсивні алгоритми використовують дані які самі ж створюють, крок за кроком, по мірі того як вони стають доступними і потрібними для утворення нових даних.
У той час як рекурсія дозволяє програмам діяти на даних довільної складності, допоки їх можна звести до простих даних (базових випадків), корекурсія дозволяє програмам видавати довільно складні і потенціально нескінченні структури даних, такі як потоки, поки це можливо із простих даних (базових випадків). Тоді як рекурсія може не закінчитись, ніколи не досягши базового випадку, корекурсія починає з базового випадку, і отже продукує наступні кроки детерміністично, хоча вона може продовжуватись нескінченно (і також не завершитись за умови ), або вона може споживати більше ніж видавати і таким чином стати непродуктивною. Багато функцій, що традиційно аналізуються як рекурсивні можна представити як корекурсивні, що завершуються на певній стадії, наприклад рекурентні співвідношення такі як факторіали.
Корекурсія може створювати скінченні і нескінченні структури даних, і може задіювати автореферентні структури даних. Корекурсію часто використовують разом із лінивими обчисленнями, для того, щоб утворити лише скінченну підмножину потенційно нескінченної структури (замість спроби отримати повну нескінченну структуру одразу). Корекурсія є дуже важливою концепцією у функціональному програмуванні, де корекурсія і кодані дозволяють цілковито функціональним мовам працювати із нескінченними структурами даних.
Приклади
Факторіал
Класичним прикладом рекурсії є обчислення факторіалу, який рекурсивно визначається як і
Щоб рекурсивно обчислити факторіал певних вхідних даних, рекурсивна функція викликає (копію) себе з іншими (певним чином «меншими») вхідними даними і використовує результат виклику, щоб утворити свій результат. Рекурсивний виклик робить те саме, окрім ситуації коли досягнуто базовий випадок. Таким чином, стек викликів розвивається по ходу. Наприклад, щоб обчислити fac(3), відбуваються рекурсивні виклики fac(2), fac(1), fac(0) ("намотуючи" стек), рекурсія завершується з fac(0) = 1, і тоді стек розмотується у зворотньому порядку і результат обчислюється по дорозі назад уздовж викликів функції, що наразі у стеку аж до початкового фрейму fac(3), де остаточний результат обчислюється як 3*2 =: 6 і повертається. В цьому прикладі функція повертає єдине значення.
Це розмотування стеку можна розгорнути, визначивши факторіал корекурсивно, як ітератор, де стартуємо з випадку , тоді з цього початкового значення будуємо значення факторіалів для чисел 1, 2, 3..., тут "стріла часу" обернута порівняно з рекурсивним випадком, читаючи визначення навпаки . Отже, корекурсивний алгоритм визначений таким чином видає потік всіх факторіалів. Це можна реалізувати за допомогою генератора. Символьно, зауваживши, що обчислення наступного факторіала потребує відслідковування обох n і f (значення попереднього факторіалу), це можна представити як:
або як у Haskell,
(\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)
що означає, "починаючи з , на кожному кроці значення обчислюється як ". Це математично тотожно і майже ідентично до рекурсивного визначення, але наголошує на тому, що значення факторіалів надбудовується на попередніх, рушаючи від стартового випадку, радше ніж обчисленні зворотнім рухом, донизу до базового випадку, використовуючи . Зауважте також, що результат корекурсивної функції містить не тільки значнення, але включає всі допоміжні дані, тому кожен окремий результат можна отримати з них.
Так ми можемо отримати перші десять зі списку значень повернутого функцією
take 10 $ (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)
Послідовність Фібоначчі
Подібним чином, послідовність Фібоначчі можна представити як:
І в Haskell,
map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )
Див. також
Посилання
- Bird, Richard Simpson (1984). Using circular programs to eliminate multiple traversals of data. Acta Informatica. 21 (3): 239—250. doi:10.1007/BF00264249.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici korekursiya ce operaciya dvoyista do rekursiyi Todi yak rekursiya pracyuye analitichno pochinayuchi z danih dalekih vid bazovogo vipadku rozbivaye yih na menshi shmatki i povtoryuyetsya dopoki ne dosyagne bazovogo vipadku korekursiya pracyuye sintetichno pochinayuchi z bazovogo vipadku i prosuvayetsya iterativno produkuyuchi dani dali viddaleni vid bazovogo vipadku Prosto kazhuchi korekursivni algoritmi vikoristovuyut dani yaki sami zh stvoryuyut krok za krokom po miri togo yak voni stayut dostupnimi i potribnimi dlya utvorennya novih danih U toj chas yak rekursiya dozvolyaye programam diyati na danih dovilnoyi skladnosti dopoki yih mozhna zvesti do prostih danih bazovih vipadkiv korekursiya dozvolyaye programam vidavati dovilno skladni i potencialno neskinchenni strukturi danih taki yak potoki poki ce mozhlivo iz prostih danih bazovih vipadkiv Todi yak rekursiya mozhe ne zakinchitis nikoli ne dosyagshi bazovogo vipadku korekursiya pochinaye z bazovogo vipadku i otzhe produkuye nastupni kroki deterministichno hocha vona mozhe prodovzhuvatis neskinchenno i takozh ne zavershitis za umovi abo vona mozhe spozhivati bilshe nizh vidavati i takim chinom stati neproduktivnoyu Bagato funkcij sho tradicijno analizuyutsya yak rekursivni mozhna predstaviti yak korekursivni sho zavershuyutsya na pevnij stadiyi napriklad rekurentni spivvidnoshennya taki yak faktoriali Korekursiya mozhe stvoryuvati skinchenni i neskinchenni strukturi danih i mozhe zadiyuvati avtoreferentni strukturi danih Korekursiyu chasto vikoristovuyut razom iz linivimi obchislennyami dlya togo shob utvoriti lishe skinchennu pidmnozhinu potencijno neskinchennoyi strukturi zamist sprobi otrimati povnu neskinchennu strukturu odrazu Korekursiya ye duzhe vazhlivoyu koncepciyeyu u funkcionalnomu programuvanni de korekursiya i kodani dozvolyayut cilkovito funkcionalnim movam pracyuvati iz neskinchennimi strukturami danih PrikladiFaktorial Klasichnim prikladom rekursiyi ye obchislennya faktorialu yakij rekursivno viznachayetsya yak 0 1 displaystyle 0 1 i n n n 1 displaystyle n n times n 1 Shob rekursivno obchisliti faktorial pevnih vhidnih danih rekursivna funkciya viklikaye kopiyu sebe z inshimi pevnim chinom menshimi vhidnimi danimi i vikoristovuye rezultat vikliku shob utvoriti svij rezultat Rekursivnij viklik robit te same okrim situaciyi koli dosyagnuto bazovij vipadok Takim chinom stek viklikiv rozvivayetsya po hodu Napriklad shob obchisliti fac 3 vidbuvayutsya rekursivni vikliki fac 2 fac 1 fac 0 namotuyuchi stek rekursiya zavershuyetsya z fac 0 1 i todi stek rozmotuyetsya u zvorotnomu poryadku i rezultat obchislyuyetsya po dorozi nazad uzdovzh viklikiv funkciyi sho narazi u steku azh do pochatkovogo frejmu fac 3 de ostatochnij rezultat obchislyuyetsya yak 3 2 6 i povertayetsya V comu prikladi funkciya povertaye yedine znachennya Ce rozmotuvannya steku mozhna rozgornuti viznachivshi faktorial korekursivno yak iterator de startuyemo z vipadku 1 0 displaystyle 1 0 todi z cogo pochatkovogo znachennya buduyemo znachennya faktorialiv dlya chisel 1 2 3 tut strila chasu obernuta porivnyano z rekursivnim vipadkom chitayuchi viznachennya navpaki n n 1 n 1 displaystyle n times n 1 n 1 Otzhe korekursivnij algoritm viznachenij takim chinom vidaye potik vsih faktorialiv Ce mozhna realizuvati za dopomogoyu generatora Simvolno zauvazhivshi sho obchislennya nastupnogo faktoriala potrebuye vidslidkovuvannya oboh n i f znachennya poperednogo faktorialu ce mozhna predstaviti yak n f 0 1 n 1 f n 1 displaystyle n f 0 1 n 1 f times n 1 abo yak u Haskell n f gt n 1 f n 1 iterate 0 1 sho oznachaye pochinayuchi z n f 0 1 displaystyle n f 0 1 na kozhnomu kroci znachennya obchislyuyetsya yak n 1 f n 1 displaystyle n 1 f times n 1 Ce matematichno totozhno i majzhe identichno do rekursivnogo viznachennya ale 1 displaystyle 1 nagoloshuye na tomu sho znachennya faktorialiv nadbudovuyetsya na poperednih rushayuchi vid startovogo vipadku radshe nizh obchislenni zvorotnim ruhom donizu do bazovogo vipadku vikoristovuyuchi 1 displaystyle 1 Zauvazhte takozh sho rezultat korekursivnoyi funkciyi mistit ne tilki n displaystyle n znachnennya ale vklyuchaye vsi dopomizhni dani tomu kozhen okremij rezultat mozhna otrimati z nih Tak mi mozhemo otrimati pershi desyat zi spisku znachen povernutogo funkciyeyu take 10 n f gt n 1 f n 1 iterate 0 1 Poslidovnist Fibonachchi Podibnim chinom poslidovnist Fibonachchi mozhna predstaviti yak a b 0 1 b a b displaystyle a b 0 1 b a b I v Haskell map fst a b gt b a b iterate 0 1 Div takozhKoindukciyaPosilannyaBird Richard Simpson 1984 Using circular programs to eliminate multiple traversals of data Acta Informatica 21 3 239 250 doi 10 1007 BF00264249