共递归

Factorial

A classic example of recursion is computing the factorial, which is defined recursively as ${\displaystyle 0!:=1}$ and ${\displaystyle n!:=n\times (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), where the final result is calculated as 3*2 =: 6 and finally returned. 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 ${\displaystyle 1=:0!}$, 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 ${\displaystyle n!\times (n+1)=:(n+1)!}$. The corecursive algorithm thus defined produces a stream of all factorials. This may be concretely implemented as a 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:

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

or in Haskell,

  (\(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 built up, going forwards from the starting case, rather than being computed after first going backwards, down to the base case, with a ${\displaystyle -1}$ decrement. Note also that 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 index n in the sequence, so that any one specific result can be selected among them all, as and when needed.

Note the connection with denotational semantics, where the denotations of recursive programs is built up corecursively in this way.

In Python, a recursive factorial function can be defined as:[lower-alpha 1]

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

This could then be called for example as factorial(5) to compute 5!.

A corresponding corecursive generator can be defined as:

def factorials():
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)

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

def n_factorials(k):
    n, f = 0, 1
    while n <= k:
        yield f
        n, f = n + 1, f * (n + 1)

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

for f in n_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,

def nth_factorial(k):
    n, f = 0, 1
    while n < k:
        n, f = n + 1, f * (n + 1)
    yield f

As can be readily seen here, this is practically equivalent (just by substituting return for the only yield there) to the accumulator argument technique for 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:

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

Note that because the Fibonacci sequence is a recurrence 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 (using parallel assignment):

def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

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

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.

Without using recursion or corecursion, one may traverse a tree by starting at the root node, placing the child nodes in a data structure, then removing the nodes in the data structure in turn and iterating over its children.[lower-alpha 2] If the data structure is a stack (LIFO), this yields depth-first traversal, while if the data structure is a queue (FIFO), this yields breadth-first traversal.

Using recursion, a (post-order)[lower-alpha 3] depth-first traversal can be implemented by starting at the root node and recursively traversing each child subtree in turn (the subtree based at each child node) – the second child subtree does not start processing until the first child subtree is finished. Once a leaf node is reached or the children of a branch node have been exhausted, the node itself is visited (e.g., the value of the node itself is outputted). In this case, the call stack (of the recursive functions) acts as the stack that is iterated over.

Using corecursion, a breadth-first traversal can be implemented by starting at the root node, outputting its value,[lower-alpha 4] 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 value of all of their root nodes, then passing on their child subtrees, etc.[lower-alpha 5] 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:

v,t = ([], FullTree) : (RootValues, ChildTrees)

meaning that at each step, one outputs the list of values of root nodes, then proceeds to the child subtrees. 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).

These can be compared as follows. The recursive traversal handles a leaf node (at the bottom) as the base case (when there are no children, just output the value), and analyzes a tree into subtrees, traversing each in turn, eventually resulting in just leaf nodes – actual leaf nodes, and branch nodes whose children have already been dealt with (cut off below). By contrast, the corecursive traversal handles a root node (at the top) as the base case (given a node, first output the value), treats a tree as being synthesized of a root node and its children, then produces as auxiliary output a list of subtrees at each step, which are then the input for the next step – the child nodes of the original root are the root nodes at the next step, as their parents have already been dealt with (cut off above). Note also that in the recursive traversal there is a distinction between leaf nodes and branch nodes, while in the corecursive traversal there is no distinction, as each node is treated as the root node of the subtree it defines.

Notably, given an infinite tree,[lower-alpha 6] 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.

In Python, this can be implemented as follows.[lower-alpha 7] The usual post-order depth-first traversal can be defined as:[lower-alpha 8]

def df(node):
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)

This can then be called by df(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:[lower-alpha 9]

def bf(tree):
    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

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

for i in bf(t):
    print(i)