Editing Corecursion (section)

== Examples ==
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 using [[imperative programming]], which is done below using the [[Generator (computer programming)|generator]] facility in [[Python (programming language)|Python]]. In these examples [[local variable]]s are used, and [[Assignment (computer science)|assigned values]] imperatively (destructively), though these are not necessary in corecursion in [[Purely functional programming|pure 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.

=== Factorial ===
A classic example of recursion is computing the [[factorial]], which is defined recursively by ''0! := 1'' and ''n! := n × (n - 1)!''.

To ''recursively'' 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 the ''base case'' has been reached. Thus a [[call stack]] develops in the process. For example, to compute ''fac(3)'', this recursively calls in turn ''fac(2)'', ''fac(1)'', ''fac(0)'' ("winding up" the stack), at which point recursion terminates with ''fac(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 frame ''fac(3)'' that uses the result of ''fac(2) = 2'' to calculate the final result as ''3 × 2 = 3 × fac(2) =: fac(3)'' and finally return ''fac(3) = 6''. In this example a function returns a single value.

This stack unwinding can be explicated, defining the factorial ''corecursively'', as an [[iterator]], where one ''starts'' with the case of <math>1 =: 0!</math>, then from this starting value constructs factorial values for increasing numbers ''1, 2, 3...'' as in the above recursive definition with "time arrow" reversed, as it were, by reading it ''backwards'' as {{nobreak|<math>n! \times (n+1) =: (n+1)!</math>.}} The corecursive algorithm thus defined produces a ''stream'' of ''all'' factorials. This may be concretely implemented as a [[Generator (computer programming)|generator]]. Symbolically, noting that computing next factorial value requires keeping track of both ''n'' and ''f'' (a previous factorial value), this can be represented as:
:<math>n, f = (0, 1) : (n + 1, f \times (n+1))</math>
or in [[Haskell (programming language)|Haskell]], 
<syntaxhighlight lang=haskell>
  (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)
</syntaxhighlight>
meaning, "starting from <math>n, f = 0, 1</math>, on each step the next values are calculated as <math>n+1, f \times (n+1)</math>". This is mathematically equivalent and almost identical to the recursive definition, but the <math>+1</math> emphasizes that the factorial values are being built ''up'', going forwards from the starting case, rather than being computed after first going backwards, ''down'' to the base case, with a <math>-1</math> decrement. The direct output of the corecursive function does not simply contain the factorial <math>n!</math> values, but also includes for each value the auxiliary data of its index ''n'' in the sequence, so that any one specific result can be selected among them all, as and when needed.

There is a connection with [[denotational semantics]], where the [[Denotational semantics#Meanings of recursive programs|denotations of recursive programs]] is built up corecursively in this way.

In Python, a recursive factorial function can be defined as:{{efn|Not validating input data.}}
<syntaxhighlight lang="python">
def factorial(n: int) -> int:
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
</syntaxhighlight>
This could then be called for example as <code>factorial(5)</code> to compute ''5!''.

A corresponding corecursive generator can be defined as:
<syntaxhighlight lang="python">
def factorials():
    """Corecursive generator."""
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)
</syntaxhighlight>
This generates an infinite stream of factorials in order; a finite portion of it can be produced by:
<syntaxhighlight lang="python">
def n_factorials(n: int):
    k, f = 0, 1
    while k <= n:
        yield f
        k, f = k + 1, f * (k + 1)
</syntaxhighlight>
This could then be called to produce the factorials up to ''5!'' via:
<syntaxhighlight lang="python">
for f in n_factorials(5):
    print(f)
</syntaxhighlight>
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,
<syntaxhighlight lang="python">
def nth_factorial(n: int):
    k, f = 0, 1
    while k < n:
        k, f = k + 1, f * (k + 1)
    return f
</syntaxhighlight>
As can be readily seen here, this is practically equivalent (just by substituting <code>return</code> for the only <code>yield</code> there) to the accumulator argument technique for [[tail call|tail 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.

=== Fibonacci sequence ===
In the same way, the [[Fibonacci sequence]] can be represented as:
:<math>a, b = (0, 1) : (b, a+b)</math>
Because the Fibonacci sequence is a [[recurrence relation]] of order 2, the corecursive relation must track two successive terms, with the <math>(b, -)</math> corresponding to shift forward by one step, and the <math>(-, a+b)</math> corresponding to computing the next term. This can then be implemented as follows (using [[parallel assignment]]):
<syntaxhighlight lang="python">
def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
</syntaxhighlight>
In Haskell, <syntaxhighlight lang=haskell> map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )</syntaxhighlight>

=== Tree traversal ===
[[Tree traversal]] via a [[depth-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's ''child nodes'' back into that data structure. If the data structure is a [[Stack (abstract data type)|stack]] (LIFO), this yields depth-first traversal, and if the data structure is a [[Queue (abstract data type)|queue]] (FIFO), this yields breadth-first traversal:
:<math>\text{trav}_\text{nn}(t) = \text{aux}_\text{nn}([t])</math>

:<math>\text{aux}_\text{df}([t,\ ...ts]) = \text{val}(t) ;\ \text{aux}_\text{df}([\ ...\text{children}(t),\ ...ts\ ])</math>

:<math>\text{aux}_\text{bf}([t,\ ...ts]) = \text{val}(t) ;\ \text{aux}_\text{bf}([\ ...ts,\ ...\text{children}(t)\ ])</math>

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,
:<math>\text{df}_\text{in}(t) = [\ ...\text{df}_\text{in}(\text{left}(t)),\ \text{val}(t),\ ...\text{df}_\text{in}(\text{right}(t))\ ]</math>
<!--
:<math>\text{df}_\text{pre}(t) = [\ \text{val}(t),\ ...flatMap(\text{df}_\text{pre})(\text{children}(t))\ ]</math>
-->

:<math>\text{df}_\text{pre}(t) = [\ \text{val}(t),\ ...\text{df}_\text{pre}(\text{left}(t)),\ ...\text{df}_\text{pre}(\text{right}(t))\ ]</math>

:<math>\text{df}_\text{post}(t) = [\ ...\text{df}_\text{post}(\text{left}(t)),\ ...\text{df}_\text{post}(\text{right}(t)),\ \text{val}(t)\ ]</math>

"Recursion" has two meanings here. First, the recursive invocations of the tree traversal functions <math>\text{df}_{xyz}</math>. More pertinently, we need to contend with how the resulting ''list 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,{{efn|Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.}} then breadth-first traversing the subtrees – i.e., passing on the ''whole 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 on ''their'' child subtrees, etc.{{efn|Technically, one may define a breadth-first traversal on an ordered, disconnected set of trees – first the root node of each tree, then the children of each tree in turn, then the grandchildren in turn, etc.}} 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 of ''n''!, in this case the auxiliary information of the remaining subtrees is pushed forward, in addition to the actual output. Symbolically,
:<math>v, ts = ([], [\text{FullTree}]) : (\text{RootValues}(ts), \text{ChildTrees}(ts))</math>
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 <math>\text{aux}_\text{bf}</math> specification above. In Haskell, 
<syntaxhighlight lang=haskell> concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )</syntaxhighlight>

Notably, given an infinite tree,{{efn|Assume fixed [[branching factor]] (e.g., binary), or at least bounded, and balanced (infinite in every direction).}} 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. See [[Dovetailing (computer science)|dovetailing]].

In Python, this can be implemented as follows.{{efn|First defining a tree class, say via:
<syntaxhighlight lang="python">
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left  = left
        self.right = right

    def __str__(self):
        return str(self.value)
</syntaxhighlight>
and initializing a tree, say via:
<syntaxhighlight lang="python">
t = Tree(1, Tree(2, Tree(4), Tree(5)), Tree(3, Tree(6), Tree(7)))
</syntaxhighlight>
In this example nodes are labeled in breadth-first order:
     1
  2     3
 4 5   6 7
}}
The usual post-order depth-first traversal can be defined as:{{efn|Intuitively, the function iterates over subtrees (possibly empty), then once these are finished, all that is left is the node itself, whose value is then returned; this corresponds to treating a leaf node as basic.}}
<syntaxhighlight lang="python">
def df(node):
    """Post-order depth-first traversal."""
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)
</syntaxhighlight>
This can then be called by <code>df(t)</code> 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:{{efn|1=Here the argument (and loop variable) is considered as a whole, possible infinite tree, represented by (identified with) its root node (tree = root node), rather than as a potential leaf node, hence the choice of variable name.}}
<syntaxhighlight lang="python">
def bf(tree):
    """Breadth-first corecursive generator."""
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list
</syntaxhighlight>
This can then be called to print the values of the nodes of the tree in breadth-first order:
<syntaxhighlight lang="python">
for i in bf(t):
    print(i)
</syntaxhighlight>