Python中实例方法中的递归

Question

我正在尝试定义一个递归方法，来遍历树的所有节点。我把树定义成了下面这样：

class Tree(object):

    def __init__(self, value, lson=None, sibling=None):
        self.value = value
        if lson:
            self.lson = Tree(lson)
        else: 
            self.lson = None

        if sibling:
            self.sibling = Tree(sibling)
        else:
            self.sibling = None

    def __str__(self):
        return str(self.value) 

我有一个可以正常工作的函数：

def walk_tree(t):
    # walk in order
    print t
    if t.lson:
        walk_tree(t.lson)
    if t.sibling:
        walk_tree(t.sibling)
    return t

我该如何把它变成一个实例方法呢？

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.walk_tree(self.lson)
    if self.sibling:
        self.walk_tree(self.sibling)
    return self

这样做会导致 最大递归深度错误...

a. 这就是实现递归方法的方式吗？
b. 在这里使用 yield 有什么理由吗？
c. 在这里使用 @staticmethod，并接收一个 Tree 实例，有什么理由吗？

Answer 1

你的递归方法其实并不是递归。它调用了一个全局的 walk_tree() 方法，而这个方法可能本身也不是递归的。

要让一个方法真正变成递归的，你需要在子节点上调用这个方法：

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.lson.walk_tree()
    if self.sibling:
        self.sibling.walk_tree()
    return self

这个方法只是在 打印 值，并没有返回任何东西，除了最上层的节点给最初的调用者。

yield 可以帮助你高效地获取值，但你需要记得在递归调用时也要使用 yield：

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        for res in self.lson.walk_tree():
            yield res
    if self.sibling:
        for res in self.sibling.walk_tree():
            yield res

或者，如果你使用的是 Python 3.3 或更高版本，可以用 yield from 来进行生成器委托：

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        yield from self.lson.walk_tree()
    if self.sibling:
        yield from self.sibling.walk_tree()

静态方法其实就是一个带命名空间的函数；你的原始 walk_tree() 全局方法可以变成一个静态方法，当然可以，但如果你觉得命名空间能让你的 API 更清晰，那这样做才有意义。