共遞迴

共遞迴在計算機科學重視一類操作，與遞迴在範疇論上對偶。因而遞迴是分析地工作，把資料分解為更小的資料直至達到基本情況。共遞迴是合成地工作，從基本情況構造出資料。共遞迴的資料是自己一點一點構造出來的。一個類似但不同的概念是"生成式遞迴"。共遞迴常與惰性求值配合，產生一個潛在無窮結構的有限子集。已隱藏部分未翻譯內容，歡迎參與[ 翻譯]。例子.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 facility in Python. In these examples local variables are used, and assigned values imperatively (destructively), though these are not necessary in corecursion in 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 as formula_1 and formula_2To "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 formula_3, 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:formula_4or in Haskell,(\(n,f) -&gt; (n+1, f*(n+1))) `iterate` (0,1)meaning, "starting from formula_5, on each step the next values are calculated as formula_6". This is mathematically equivalent and almost identical to the recursive definition, but the formula_7 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 formula_8 decrement. Note also that the direct output of the corecursive function does not simply contain the factorial formula_9 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:def factorial(n):if n == 0:return 1else:return n * factorial(n - 1)This could then be called for example as codice_1 to compute "5!".A corresponding corecursive generator can be defined as:def factorials():n, f = 0, 1while True:yield fn, 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, 1while n  (Tree Int Int, [Int])go (Leaf _ ) (n:ns) = (Leaf n , n+1 : ns )go (Branch _ l r) (n:ns) = (Branch n l′ r′ , n+1 : ns′′)where(l′, ns′ ) = go l ns(r′, ns′′) = go r ns′An apomorphism (such as an anamorphism, such as unfold) is a form of corecursion in the same way that a paramorphism (such as a catamorphism, such as fold) is a form of recursion.The Coq proof assistant supports corecursion and coinduction using the CoFixpoint command.歷史.Corecursion, referred to as "circular programming," dates at least to #重定向 , who credits John Hughes and Philip Wadler; more general forms were developed in #重定向 . The original motivations included producing more efficient algorithms (allowing 1 pass over data in some cases, instead of requiring multiple passes) and implementing classical data structures, such as doubly linked lists and queues, in functional languages.