共递归

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是互递归

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

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

参见[编辑]

注释[编辑]

  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.