This articleis written like apersonal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Pleasehelp improve it by rewriting it in anencyclopedic style.(February 2020) (Learn how and when to remove this message)

Incomputer science,corecursion is a type of operation that isdual torecursion. Whereas recursion worksanalytically, 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 isgenerative 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 asstreams, so long as it can be produced from simple data (base cases) in a sequence offinite 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 examplerecurrence relations such as the factorial.

Corecursion can produce bothfinite andinfinitedata structures as results, and may employself-referential data structures. Corecursion is often used in conjunction withlazy 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 infunctional programming, where corecursion andcodata allowtotal languages to work with infinite data structures.

Corecursion can be understood by contrast with recursion, which is more familiar. While corecursion is primarily of interest in functional programming, it can be illustrated usingimperative programming, which is done below using thegenerator facility inPython. In these exampleslocal variables are used, andassigned values imperatively (destructively), though these are not necessary in corecursion inpure functional programming. In pure functional programming, rather than assigning to local variables, these computed values form an invariable sequence, and prior values are accessed by self-reference (later values in the sequence reference earlier values in the sequence to be computed). The assignments simply express this in the imperative paradigm and explicitly specify where the computations happen, which serves to clarify the exposition.

A classic example of recursion is computing thefactorial, which is defined recursively by0! := 1 andn! := n × (n - 1)!.

Torecursively compute its result on a given input, a recursive function calls (a copy of)itself with a different ("smaller" in some way) input and uses the result of this call to construct its result. The recursive call does the same, unless thebase case has been reached. Thus acall stack develops in the process. For example, to computefac(3), this recursively calls in turnfac(2),fac(1),fac(0) ("winding up" the stack), at which point recursion terminates withfac(0) = 1, and then the stack unwinds in reverse order and the results are calculated on the way back along the call stack to the initial call framefac(3) that uses the result offac(2) = 2 to calculate the final result as3 × 2 = 3 × fac(2) =: fac(3) and finally returnfac(3) = 6. In this example a function returns a single value.

This stack unwinding can be explicated, defining the factorialcorecursively, as aniterator, where onestarts with the case of${\displaystyle 1=:0!}$, then from this starting value constructs factorial values for increasing numbers1, 2, 3... as in the above recursive definition with "time arrow" reversed, as it were, by reading itbackwards as${\displaystyle n!\times (n+1)=:(n+1)!}$. The corecursive algorithm thus defined produces astream ofall factorials. This may be concretely implemented as agenerator. Symbolically, noting that computing next factorial value requires keeping track of bothn andf (a previous factorial value), this can be represented as:

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

or inHaskell,

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

meaning, "starting from${\displaystyle n,f=0,1}$, on each step the next values are calculated as${\displaystyle n+1,f\times (n+1)}$". This is mathematically equivalent and almost identical to the recursive definition, but the${\displaystyle +1}$ emphasizes that the factorial values are being builtup, going forwards from the starting case, rather than being computed after first going backwards,down to the base case, with a${\displaystyle -1}$ decrement. The direct output of the corecursive function does not simply contain the factorial${\displaystyle n!}$ values, but also includes for each value the auxiliary data of its indexn in the sequence, so that any one specific result can be selected among them all, as and when needed.

There is a connection withdenotational semantics, where thedenotations of recursive programs is built up corecursively in this way.

In Python, a recursive factorial function can be defined as:^[a]

deffactorial(n:int)->int:"""Recursive factorial function."""ifn==0:return1else:returnn*factorial(n-1)

This could then be called for example asfactorial(5) to compute5!.

A corresponding corecursive generator can be defined as:

fromtypingimportGeneratordeffactorials()->Generator[int,None,None]:"""Corecursive generator."""n:int=0f:int=1whileTrue:yieldfn,f=n+1,f*(n+1)

This generates an infinite stream of factorials in order; a finite portion of it can be produced by:

fromtypingimportGeneratordefn_factorials(n:int)->Generator[int,None,None]:k:int=0f:int=1whilek<=n:yieldfk,f=k+1,f*(k+1)

This could then be called to produce the factorials up to5! via:

forfinn_factorials(5):print(f)

If we're only interested in a certain factorial, just the last value can be taken, or we can fuse the production and the access into one function,

defnth_factorial(n:int)->int:k:int=0f:int=1whilek<n:k,f=k+1,f*(k+1)returnf

As can be readily seen here, this is practically equivalent (just by substitutingreturn for the onlyyield there) to the accumulator argument technique fortail recursion, unwound into an explicit loop. Thus it can be said that the concept of corecursion is an explication of the embodiment of iterative computation processes by recursive definitions, where applicable.

In the same way, theFibonacci sequence can be represented as:

${\displaystyle a,b=(0,1):(b,a+b)}$

Because the Fibonacci sequence is arecurrence relation of order 2, the corecursive relation must track two successive terms, with the${\displaystyle (b,-)}$ corresponding to shift forward by one step, and the${\displaystyle (-,a+b)}$ corresponding to computing the next term. This can then be implemented as follows (usingparallel assignment):

fromtypingimportGeneratordeffibonacci_sequence()->Generator[int,None,None]:a:int=0b:int=1whileTrue:yieldaa,b=b,a+b

In Haskell,

mapfst((\(a,b)->(b,a+b))`iterate`(0,1))

Tree traversal via adepth-first approach is a classic example of recursion. Dually,breadth-first traversal can very naturally be implemented via corecursion.

Iteratively, one may traverse a tree by placing its root node in a data structure, then iterating with that data structure while it is non-empty, on each step removing the first node from it and placing the removed node'schild nodes back into that data structure. If the data structure is astack (LIFO), this yields depth-first traversal, and if the data structure is aqueue (FIFO), this yields breadth-first traversal:

${\displaystyle {\text{trav}}_{\text{nn}}(t)={\text{aux}}_{\text{nn}}([t])}$

${\displaystyle {\text{aux}}_{\text{df}}([t,...ts])=\text{val}(t);{\text{aux}}_{\text{df}}([...\text{children}(t),...ts])}$

${\displaystyle {\text{aux}}_{\text{bf}}([t,...ts])=\text{val}(t);{\text{aux}}_{\text{bf}}([...ts,...\text{children}(t)])}$

Using recursion, a depth-first traversal of a tree is implemented simply as recursively traversing each of the root node's child nodes in turn. Thus the second child subtree is not processed until the first child subtree is finished. The root node's value is handled separately, whether before the first child is traversed (resulting in pre-order traversal), after the first is finished and before the second (in-order), or after the second child node is finished (post-order) — assuming the tree is binary, for simplicity of exposition. The call stack (of the recursive traversal function invocations) corresponds to the stack that would be iterated over with the explicit LIFO structure manipulation mentioned above. Symbolically,

${\displaystyle {\text{df}}_{\text{in}}(t)=[...{\text{df}}_{\text{in}}(\text{left}(t)),\text{val}(t),...{\text{df}}_{\text{in}}(\text{right}(t))]}$

${\displaystyle {\text{df}}_{\text{pre}}(t)=[\text{val}(t),...{\text{df}}_{\text{pre}}(\text{left}(t)),...{\text{df}}_{\text{pre}}(\text{right}(t))]}$

${\displaystyle {\text{df}}_{\text{post}}(t)=[...{\text{df}}_{\text{post}}(\text{left}(t)),...{\text{df}}_{\text{post}}(\text{right}(t)),\text{val}(t)]}$

"Recursion" has two meanings here. First, the recursive invocations of the tree traversal functions${\displaystyle {\text{df}}_{xyz}}$. More pertinently, we need to contend with how the resultinglist of values is built here. Recursive, bottom-up output creation will result in the right-to-left tree traversal. To have it actually performed in the intended left-to-right order the sequencing would need to be enforced by some extraneous means, or it would be automatically achieved if the output were to be built in the top-down fashion, i.e.corecursively.

A breadth-first traversal creating its output in the top-down order, corecursively, can be also implemented by starting at the root node, outputting its value,^[b] then breadth-first traversing the subtrees – i.e., passing on thewhole list of subtrees to the next step (not a single subtree, as in the recursive approach) – at the next step outputting the values of all of their root nodes, then passing ontheir child subtrees, etc.^[c] In this case the generator function, indeed the output sequence itself, acts as the queue. As in the factorial example above, where the auxiliary information of the index (which step one was at,n) was pushed forward, in addition to the actual output ofn!, in this case the auxiliary information of the remaining subtrees is pushed forward, in addition to the actual output. Symbolically,

${\displaystyle vs,ts=([],[\text{FullTree}]):(\text{RootValues}(ts),\text{ChildTrees}(ts))}$

meaning that at each step, one outputs the list of values in this level's nodes, then proceeds to the next level's nodes. Generating just the node values from this sequence simply requires discarding the auxiliary child tree data, then flattening the list of lists (values are initially grouped by level (depth); flattening (ungrouping) yields a flat linear list). This is extensionally equivalent to the${\displaystyle {\text{aux}}_{\text{bf}}}$ specification above. In Haskell,

concatMapfst((\(vs,ts)->(rootValuests,childTreests))`iterate`([],[fullTree]))

Notably, given an infinite tree,^[d] the corecursive breadth-first traversal will traverse all nodes, just as for a finite tree, while the recursive depth-first traversal will go down one branch and not traverse all nodes, and indeed if traversing post-order, as in this example (or in-order), it will visit no nodes at all, because it never reaches a leaf. This shows the usefulness of corecursion rather than recursion for dealing with infinite data structures. One caveat still remains for trees with the infinite branching factor, which need a more attentive interlacing to explore the space better, as indovetailing.

In Python, this can be implemented as follows.^[e]The usual post-order depth-first traversal can be defined as:^[f]

defdf(node:Tree)->None:"""Post-order depth-first traversal."""ifnodeisnotNone:df(node.left)df(node.right)print(node.value)

This can then be called bydf(t) to print the values of the nodes of the tree in post-order depth-first order.

The breadth-first corecursive generator can be defined as:^[g]

fromtypingimportGeneratordefbf(tree:Tree)->Generator[int,None,None]:"""Breadth-first corecursive generator."""tree_list:list[Tree]=[tree]whiletree_list:new_tree_list:list[Tree]=[]fortreeintree_list:iftreeisnotNone:yieldtree.valuenew_tree_list.append(tree.left)new_tree_list.append(tree.right)tree_list=new_tree_list

This can then be called to print the values of the nodes of the tree in breadth-first order:

foriinbf(t):print(i)

This sectionmay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(November 2010) (Learn how and when to remove this message)

Initial data types can be defined as being theleast fixpoint (up to isomorphism) of some type equation; theisomorphism is then given by aninitial algebra. Dually, final (or terminal) data types can be defined as being thegreatest fixpoint of a type equation; the isomorphism is then given by a finalcoalgebra.

If the domain of discourse is thecategory of sets andtotal functions, then final data types may contain infinite,non-wellfounded values, whereas initial types do not.^[1][2] On the other hand, if the domain of discourse is the category ofcomplete partial orders andcontinuous functions, which corresponds roughly to theHaskell programming language, then final types coincide with initial types, and the corresponding final coalgebra and initial algebra form an isomorphism.^[3]

Corecursion is then a technique for recursively defining functions whose range (codomain) is a final data type, dual to the way that ordinaryrecursion recursively defines functions whose domain is an initial data type.^[4]

The discussion below provides several examples in Haskell that distinguish corecursion. Roughly speaking, if one were to port these definitions to the category of sets, they would still be corecursive. This informal usage is consistent with existing textbooks about Haskell.^[5] The examples used in this article predate the attempts to define corecursion and explain what it is.

This section mayrequirecleanup to meet Wikipedia'squality standards. The specific problem is:mix of discussion, examples, and related concepts. Please helpimprove this section if you can.(July 2012) (Learn how and when to remove this message)

The rule forprimitive corecursion oncodata is the dual to that forprimitive recursion on data. Instead of descending on the argument bypattern-matching on its constructors (thatwere called up before, somewhere, so we receive a ready-made datum and get at its constituent sub-parts, i.e. "fields"), we ascend on the result by filling-in its "destructors" (or "observers", thatwill be called afterwards, somewhere - so we're actually calling a constructor, creating another bit of the result to be observed later on). Thus corecursioncreates (potentially infinite) codata, whereas ordinary recursionanalyses (necessarily finite) data. Ordinary recursion might not be applicable to the codata because it might not terminate. Conversely, corecursion is not strictly necessary if the result type is data, because data must be finite.

In "Programming with streams in Coq: a case study: the Sieve of Eratosthenes"^[6] we find

hd(concas)=atl(concas)=s(sieveps)=ifdivp(hds)thensievep(tls)elseconc(hds)(sievep(tls))hd(primess)=(hds)tl(primess)=primes(sieve(hds)(tls))

where primes "are obtained by applying the primes operation to the stream (Enu 2)". Following the above notation, the sequence of primes (with a throwaway 0 prefixed to it) and numbers streams being progressively sieved, can be represented as

${\displaystyle p,s=(0,[\mathrm{2..}]):(hd(s),sieve(hd(s),tl(s)))}$

or in Haskell,

(\(p,s@(h:t))->(h,sieveht))`iterate`(0,[2..])

The authors discuss how the definition ofsieve is not guaranteed always to beproductive, and could become stuck e.g. if called with[5,10..] as the initial stream.

Here is another example in Haskell. The following definition produces the list ofFibonacci numbers in linear time:

fibs=0:1:zipWith(+)fibs(tailfibs)

This infinite list depends on lazy evaluation; elements are computed on an as-needed basis, and only finite prefixes are ever explicitly represented in memory. This feature allows algorithms on parts of codata to terminate; such techniques are an important part of Haskell programming.

This can be done in Python as well:^[7]

importitertoolsfromtypingimportGeneratordeffibonacci()->Generator[int,None,None]:defdeferred_output()->Generator[int,None,None]:yield fromoutputresult,c1,c2=itertools.tee(deferred_output(),3)paired:Generator[int,None,None]=(x+yforx,yinzip(c1,itertools.islice(c2,1,None)))output:Generator[int,None,None]=itertools.chain([0,1],paired)returnresultprint(*islice(fibonacci(),20),sep=', ')# prints:# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

The definition ofzipWith can be inlined, leading to this:

fibs=0:1:nextfibswherenext(a:t@(b:_))=(a+b):nextt

This example employs a self-referentialdata structure. Ordinary recursion makes use of self-referentialfunctions, but does not accommodate self-referential data. However, this is not essential to the Fibonacci example. It can be rewritten as follows:

fibs=fibgen(0,1)fibgen(x,y)=x:fibgen(y,x+y)

This employs only self-referentialfunction to construct the result. If it were used with strict list constructor it would be an example of runaway recursion, but withnon-strict list constructor this guarded recursion gradually produces an indefinitely defined list.

Corecursion need not produce an infinite object; a corecursive queue^[8] is a particularly good example of this phenomenon. The following definition produces abreadth-first traversal of a binary tree in thetop-down manner, in linear time (already incorporating the flattening mentionedabove):

dataTreeab=Leafa|Branchb(Treeab)(Treeab)bftrav::Treeab->[Treeab]bftravtree=tree:tswherets=gen1(tree:ts)gen0p=[]genlen(Leaf_:p)=gen(len-1)pgenlen(Branch_lr:p)=l:r:gen(len+1)p--       ----read----        ----write-ahead----- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]

This definition takes a tree and produces a list of its sub-trees (nodes and leaves). This list serves dual purpose as both the input queue and the result (gen len p produces its outputlen notches ahead of its input back-pointer,p, along the list). It is finite if and only if the initial tree is finite. The length of the queue must be explicitly tracked in order to ensure termination; this can safely be elided if this definition is applied only to infinite trees.

This Haskell code uses self-referential data structure, but does notessentially depend on lazy evaluation. It can be straightforwardly translated into e.g. Prolog which is not a lazy language. Whatis essential is the ability to build a list (used as the queue) in thetop-down manner. For that, Prolog hastail recursion modulo cons (i.e. open ended lists). Which is also emulatable in Scheme, C, etc. using linked lists with mutable tail sentinel pointer:

bftrav(Tree,[Tree|TS]):-bfgen(1,[Tree|TS],TS).bfgen(0,_,[]):-!.% 0 entries in the queue -- stop and close the listbfgen(N,[leaf(_)|P],TS):-N2isN-1,bfgen(N2,P,TS).bfgen(N,[branch(_,L,R)|P],[L,R|TS]):-N2isN+1,bfgen(N2,P,TS).%%         ----read-----      --write-ahead--

Another particular example gives a solution to the problem of breadth-first labeling.^[9] The functionlabel visits every node in a binary tree in the breadth first fashion, replacing each label with an integer, each subsequent integer bigger than the last by 1. This solution employs a self-referential data structure, and the binary tree can be finite or infinite.

label::Treeab->TreeIntIntlabelt=tnwhere(tn,ns)=got(1:ns)go::Treeab->[Int]->(TreeIntInt,[Int])go(Leaf_)(i:a)=(Leafi,i+1:a)go(Branch_lr)(i:a)=(Branchilnrn,i+1:c)where(ln,b)=gola(rn,c)=gorb

Or in Prolog, for comparison,

label(Tree,Tn):-label(Tree,[1|Ns],Tn,Ns).label(leaf(_),[I|A],leaf(I),[I+1|A]).label(branch(_,L,R),[I|A],branch(I,Ln,Rn),[I+1|C]):-label(L,A,Ln,B),label(R,B,Rn,C).

Anapomorphism (such as ananamorphism, such asunfold) is a form of corecursion in the same way that aparamorphism (such as acatamorphism, such asfold) is a form of recursion.

TheRocq proof assistant supports corecursion andcoinduction using the CoFixpoint command.

Corecursion, referred to ascircular programming, dates at least to (Bird 1984), who creditsJohn Hughes andPhilip Wadler; more general forms were developed in (Allison 1989). The original motivations included producing more efficient algorithms (allowing a single pass over data in some cases, instead of requiring multiple passes) and implementing classical data structures, such asdoubly linked lists and queues, in functional languages.

• Bisimulation
• Coinduction
• Recursion
• Anamorphism

• Theoretical computer science
• Self-reference
• Functional programming
• Category theory
• Recursion

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles with style issues from February 2020
• All articles with style issues
• Wikipedia articles that are too technical from November 2010
• All articles that are too technical
• Articles needing cleanup from July 2012
• All pages needing cleanup
• Cleanup tagged articles with a reason field from July 2012
• Wikipedia pages needing cleanup from July 2012
• Articles with example Haskell code
• Articles with example Python (programming language) code