Corecursion

In computer science, corecursion is a type of operation that is dual to recursion. Where recursion works backwards (analytically, deductively), working on large data (more properly, data further from a base case) by breaking it into smaller data and repeating until one reaches a base case, corecursion works forward (synthetically, inductively), starting from a base case and iteratively producing larger data (more properly, later data, further removed from a base case). Put simply, it is about algorithms using the data which they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data.

Where recursion allows programs to operate on arbitrarily complex data, so long as it can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams, so long as it can be produced from simple data (base cases). Where recursion may not terminate, never reaching a base state, corecursion starts from a base state, and thus produces subsequent steps deterministically, but the result may be infinite (and thus not terminate).

Corecursion can produce both finite and infinite data structures as result, and may employ self-referential data structures. Corecursion is often used in conjunction with lazy evaluation, to only produce a finite subset of a potentially infinite structure (rather than trying to produce an entire infinite structure at once). Corecursion is a particularly important concept in functional programming, where corecursion and codata allow total languages to work with infinite data structures.