Editing Corecursion (section)

=== 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.