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 , 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 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: or in Haskell, (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1) meaning, "starting from , on each step the next values are calculated as ". This is mathematically equivalent and almost identical to the recursive definition, but the 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 decrement. The direct output of the corecursive function does not simply contain the factorial values, but also includes for each value the auxiliary data of its index n in the