"yield" in recursive generator

来源: www.javaeye.com/topic/338111

二叉树的中序遍历，递归的genertor(想当然的解法，和遍历二叉树的算法完全一样)

class tree_t:
    def __init__(self, data, left = None, right = None):
        self.left = left
        self.data = data
        self.right = right

left = tree_t("left")
right = tree_t("right")
root = tree_t("root", left, right)

def infix_iterate(tree):
    if tree.left:
        infix_iterate(tree.left)
    yield tree
    if tree.right:
        infix_iterate(tree.right)

for tree in infix_iterate(root):
    print tree.data

程序输出：
root

二叉树的中序遍历，递归的genertor(正确的解法)

class tree_t:
    def __init__(self, data, left = None, right = None):
        self.left = left
        self.data = data
        self.right = right

left = tree_t("left")
right = tree_t("right")
root = tree_t("root", left, right)

def infix_iterate(tree):
    if tree.left:
        for child in infix_iterate(tree.left):
            yield child
    yield tree
    if tree.right:
        for child in infix_iterate(tree.right):
            yield child

for tree in infix_iterate(root):
    print tree.data

程序输出：
left
root
right

第1个例子没有任何问题，很直观。但在第2个例子时，发现程序只输出一行代码root，仔细看了下参考资料，才注意到正确的递归调用和我想当然的不一样：

    想当然的写法：
    if tree.left:
        infix_iterate(tree.left)

    正确的写法：
    if tree.left:
        for child in infix_iterate(tree.left):
            yield child

不知道为什么python的递归generator没有采用例子2中那样直观的写法？是实现困难的原因吗？

Python里带有yield表达式（*）的函数是generator function，而调用一个generator function总是返回一个iterator；iterator不调用其next()方法是不会执行的；iterator总是通过yield表达式来提供next()方法的返回值，自然，谁调用next()方法谁就会获得返回值。

在 楼主的第二种写法里，那两个if语句里的调用并不是“递归调用”，而只是单纯的获得了两个iterator，并且没有让它们执行；generator function要真的“递归”起来，就得像第三种写法那样，在generator function的函数体里获得了一个iterator之后，遍历这个iterator里的值并逐个yield返回出去。for...in语句所做的正好就是拿到一个iterable然后逐个遍历里面的值，所以正好适合用在这个场景。

要是直接带第二种写法上加点东西就能看到得到的iterator里发生的事：

class tree_t:
    def __init__(self, data, left = None, right = None):
        self.left = left
        self.data = data
        self.right = right

left = tree_t("left")
right = tree_t("right")
root = tree_t("root", left, right)

def infix_iterate(tree):
    if tree.left:
        print (infix_iterate(tree.left).next().data)
    yield tree
    if tree.right:
        print (infix_iterate(tree.right).next().data)

for tree in infix_iterate(root):
    print tree.data

当然这样不能用于遍历就是了，只是用来说明generator function里调用了“自己”得到的是什么。