Editing Corecursion (section)

{{Short description|Type of algorithm in computer science}}
{{distinguish|Mutual recursion}}
{{essay|date=February 2020}}
In [[computer science]], '''corecursion''' is a type of operation that is [[Dual (category theory)|dual]] to [[recursion (computer science)|recursion]]. Whereas recursion works [[analysis|analytically]], starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is ''[[Generative recursion#Structural versus generative recursion|generative recursion]]'', which may lack a definite "direction" inherent in corecursion and recursion.

Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as [[stream (computing)|stream]]s, so long as it can be produced from simple data (base cases) in a sequence of ''finite'' steps. Where recursion may not terminate, never reaching a base state, corecursion starts from a base state, and thus produces subsequent steps deterministically, though it may proceed indefinitely (and thus not terminate under strict evaluation), or it may consume more than it produces and thus become non-''productive''. Many functions that are traditionally analyzed as recursive can alternatively, and arguably more naturally, be interpreted as corecursive functions that are terminated at a given stage, for example [[recurrence relation]]s such as the factorial.

Corecursion can produce both [[Finite set|finite]] and [[Infinite set|infinite]] [[data structure]]s as results, and may employ [[self-reference|self-referential]] data structures. Corecursion is often used in conjunction with [[lazy evaluation]], to produce only 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 (computer science)|codata]] allow [[total language]]s to work with infinite data structures.