# 共递归

2018-08-28 09:58:32     所属分类：递归论

## 参见

• 双拟英语Bisimulation
• 共诱导英语Coinduction
• 递归
• 合成变质英语Anamorphism

## 注释

1. ^ Not validating input data.
2. ^ More elegantly, one can start by placing the root node itself in the structure and then iterating.
3. ^ Post-order is to make "leaf node is base case" explicit for exposition, but the same analysis works for pre-order or in-order.
4. ^ Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.
5. ^ 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.
6. ^ Assume fixed branching factor (e.g., binary), or at least bounded, and balanced (infinite in every direction).
7. ^ First defining a tree class, say via:
```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)
```

and initializing a tree, say via:

```t = Tree(1, Tree(2, Tree(4), Tree(5)), Tree(3, Tree(6), Tree(7)))
```

In this example nodes are labeled in breadth-first order:

```    1
2     3
4 5   6 7
```
8. ^ 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.
9. ^ 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.

## 参考文献

1. ^ Barwise and Moss 1996.
2. ^ Moss and Danner 1997.
3. ^ Smyth and Plotkin 1982.
4. ^ Gibbons and Hutton 2005.
5. ^ Doets and van Eijck 2004.
6. ^ Leclerc and Paulin-Mohring, 1994
7. ^ Hettinger 2009.
8. ^ Allison 1989; Smith 2009.
9. ^ Jones and Gibbons 1992.
• Bird, Richard Simpson. Using circular programs to eliminate multiple traversals of data. Acta Informatica. 1984, 21 (3): 239–250. doi:10.1007/BF00264249.
• Lloyd Allison. Circular Programs and Self-Referential Structures. Software Practice and Experience. April 1989, 19 (2): 99–109. doi:10.1002/spe.4380190202.
• Geraint Jones and Jeremy Gibbons. Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips (Technical report). Dept of Computer Science, University of Auckland. 1992.
• Jon Barwise; Lawrence S Moss. Vicious Circles. Center for the Study of Language and Information. June 1996. ISBN 978-1-57586-009-1. （原始内容存档于2010年6月21日）.
• Lawrence S Moss; Norman Danner. On the Foundations of Corecursion. Logic Journal of the IGPL. 1997, 5 (2): 231–257. doi:10.1093/jigpal/5.2.231.
• Kees Doets; Jan van Eijck. The Haskell Road to Logic, Maths, and Programming. King's College Publications. May 2004. ISBN 978-0-9543006-9-2.
• David Turner. Total Functional Programming. Journal of Universal Computer Science. 2004-07-28, 10 (7): 751–768. doi:10.3217/jucs-010-07-0751.
• Jeremy Gibbons; Graham Hutton. Proof methods for corecursive programs. Fundamenta Informaticae Special Issue on Program Transformation. April 2005, 66 (4): 353–366.
• Leon P Smith, Lloyd Allison's Corecursive Queues: Why Continuations Matter, The Monad Reader, 2009-07-29, (14): 37–68
• Raymond Hettinger. Recipe 576961: Technique for cyclical iteration. 2009-11-19.
• M. B. Smyth and G. D. Plotkin. The Category-Theoretic Solution of Recursive Domain Equations. SIAM Journal on Computing. 1982, 11 (4): 761–783. doi:10.1137/0211062.
• Leclerc, Francois; Paulin-Mohring, Christine. Programming with Streams in Coq: A Case Study: the Sieve of Eratosthenes. Types for Proofs and Programs: International Workshop TYPES '93. Springer-Verlag New York, Inc. 1993: 191–212. ISBN 3-540-58085-9.

1分，2分不嫌少，钱不钱的无所谓，重要的是你的话语激励我前行！