Корекурсія

В інформатиці, корекурсія — це операція двоїста до рекурсії. Тоді як рекурсія працює аналітично, починаючи з даних далеких від базового випадку, розбиває їх на менші шматки, і повторюється допоки не досягне базового випадку, корекурсія працює синтетично, починаючи з базового випадку і просувається ітеративно продукуючи дані далі віддалені від базового випадку. Просто кажучи, корекурсивні алгоритми використовують дані які самі ж створюють, крок за кроком, по мірі того як вони стають доступними і потрібними для утворення нових даних.

У той час як рекурсія дозволяє програмам діяти на даних довільної складності, допоки їх можна звести до простих даних (базових випадків), корекурсія дозволяє програмам видавати довільно складні і потенціально нескінченні структури даних, такі як потоки, поки це можливо із простих даних (базових випадків). Тоді як рекурсія може не закінчитись, ніколи не досягши базового випадку, корекурсія починає з базового випадку, і отже продукує наступні кроки детерміністично, хоча вона може продовжуватись нескінченно (і також не завершитись за умови строгих обчислень), або вона може споживати більше ніж видавати і таким чином стати непродуктивною. Багато функцій, що традиційно аналізуються як рекурсивні можна представити як корекурсивні, що завершуються на певній стадії, наприклад рекурентні співвідношення такі як факторіали.

Корекурсія може створювати скінченні і нескінченні структури даних, і може задіювати автореферентні структури даних. Корекурсію часто використовують разом із лінивими обчисленнями, для того, щоб утворити лише скінченну підмножину потенційно нескінченної структури (замість спроби отримати повну нескінченну структуру одразу). Корекурсія є дуже важливою концепцією у функціональному програмуванні, де корекурсія і кодані дозволяють цілковито функціональним мовам працювати із нескінченними структурами даних.

Приклади

Факторіал

Класичним прикладом рекурсії є обчислення факторіалу, який рекурсивно визначається як $0!:=1$ і $n!:=n\times (n-1)!$

Щоб рекурсивно обчислити факторіал певних вхідних даних, рекурсивна функція викликає (копію) себе з іншими (певним чином «меншими») вхідними даними і використовує результат виклику, щоб утворити свій результат. Рекурсивний виклик робить те саме, окрім ситуації коли досягнуто базовий випадок. Таким чином, стек викликів розвивається по ходу. Наприклад, щоб обчислити fac(3), відбуваються рекурсивні виклики fac(2), fac(1), fac(0) ("намотуючи" стек), рекурсія завершується з fac(0) = 1, і тоді стек розмотується у зворотньому порядку і результат обчислюється по дорозі назад уздовж викликів функції, що наразі у стеку аж до початкового фрейму fac(3), де остаточний результат обчислюється як 3*2 =: 6 і повертається. В цьому прикладі функція повертає єдине значення.

Це розмотування стеку можна розгорнути, визначивши факторіал корекурсивно, як ітератор, де стартуємо з випадку $1=:0!$, тоді з цього початкового значення будуємо значення факторіалів для чисел 1, 2, 3..., тут "стріла часу" обернута порівняно з рекурсивним випадком, читаючи визначення навпаки  $n!\times (n+1)=:(n+1)!$. Отже, корекурсивний алгоритм визначений таким чином видає потік всіх факторіалів. Це можна реалізувати за допомогою генератора. Символьно, зауваживши, що обчислення наступного факторіала потребує відслідковування обох n і f (значення попереднього факторіалу), це можна представити як:

$n,f=(0,1):(n+1,f\times (n+1))$

або як у Haskell,

  (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)

що означає, "починаючи з $n,f=0,1$, на кожному кроці значення обчислюється як $n+1,f\times (n+1)$". Це математично тотожно і майже ідентично до рекурсивного визначення, але $+1$ наголошує на тому, що значення факторіалів надбудовується на попередніх, рушаючи від стартового випадку, радше ніж обчисленні зворотнім рухом, донизу до базового випадку, використовуючи $-1$. Зауважте також, що результат корекурсивної функції містить не тільки $n!$ значнення, але включає всі допоміжні дані, тому кожен окремий результат можна отримати з них.

Так ми можемо отримати перші десять зі списку значень повернутого функцією

  take 10 $ (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)

Послідовність Фібоначчі

Подібним чином, послідовність Фібоначчі можна представити як:

$a,b=(0,1):(b,a+b)$

І в 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.