Описание тега corecursion

В информатике corecursion - это тип операции, который двойственен рекурсии. В то время как рекурсия работает аналитически, начиная с данных дальше от базового случая и разбивая их на более мелкие данные и повторяя до тех пор, пока не будет достигнут базовый вариант, corecursion работает синтетически, начиная с базового случая и наращивая его, итеративно производя данные, удаленные от базовый случай. Проще говоря, коркурсивные алгоритмы используют данные, которые они сами производят, бит за битом, по мере того, как они становятся доступными и необходимыми, для получения дополнительных битов данных. Некоторые авторы называют это генеративной рекурсией.

Если рекурсия позволяет программам работать с произвольно сложными данными, если их можно свести к простым данным (базовые случаи), corecursion позволяет программам создавать произвольно сложные и потенциально бесконечные структуры данных, такие как потоки, при условии, что они могут быть созданы из простых данных (базовые случаи). Там, где рекурсия не может завершиться, никогда не достигнув базового состояния, corecursion начинается с базового состояния и, таким образом, детерминированно производит последующие шаги, но результат может быть бесконечным (и, таким образом, не завершаться в целом, но каждый шаг будет конечным - что есть известное как "продуктивное" поведение). Многие функции, которые традиционно анализируются как рекурсивные, могут альтернативно и, возможно, более естественно, интерпретироваться как коркурсивные функции, которые завершаются на данном этапе, например рекуррентные отношения, такие как факториал. Таким образом, corecursion - это повторная итерация.

В результате corecursion может создавать как конечные, так и бесконечные структуры данных, а также может использовать самодостаточные структуры данных. corecursion часто используется в сочетании с ленивым вычислением, чтобы создать только конечное подмножество потенциально бесконечной структуры (вместо того, чтобы пытаться создать всю бесконечную структуру сразу). corecursion - это особенно важная концепция в функциональном программировании, где corecursion и codata позволяют всем языкам работать с бесконечными структурами данных.

Страница Википедии: http://en.wikipedia.org/wiki/Corecursion