计算机科学

首页 > 计算机科学

共递归

2018-08-28 09:58:32     所属分类:递归论
Confusion grey.svg
提示:本条目的主题不是互递归

共递归在计算机科学重视一类操作,与递归在范畴论上对偶。因而递归是分析地工作,把数据分解为更小的数据直至达到基本情况。共递归是合成地工作,从基本情况构造出数据。共递归的数据是自己一点一点构造出来的。一个类似但不同的概念是生成式递归(generative recursion)。

共递归常与惰性求值配合,产生一个潜在无穷结构的有限子集。

参见

  • 双拟英语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. 

相关推荐