当我们递归地使用yield时，是否创建了n个迭代器？

Question

考虑：

def iterInOrder(node):
    if node.left:
        for n in iterInOrder(node.left):
            yield n
    yield node
    if node.right:
        for n in iterInOrder(node.right):
            yield n

假设n是输入二叉树中的节点数，我们是否创建一个生成n个节点的生成器？或者我们创建n迭代器，每个迭代器生成一个节点？与简单的递归旅行相比，该代码的空间/时间复杂性如何

def visitInOrder(node):
    if node.left:
        visitInOrder(node.left)
    visit(node)
    if node.right:
        visitInOrder(node.right)
                

我更关心Python2，但如果Python3的答案不同，我可能会很高兴知道

Answer 1

在CPython中，对iterInOrder()的每次调用都会创建一个新的生成器迭代器，而不管Python版本如何，也不管它是顶级调用还是递归调用

类似地，对visitInOrder()的每次调用都会创建一个新的堆栈框架，同样与Python版本或上下文无关

因此，无论哪种方式，空间复杂度都是O(depth(tree))（通常，这与节点数没有有用的关系-树可能是n层深，或2层深）

时间是一种不同的计算，但很微妙，因为它几乎不值得注意：递归版本具有O(n)时间复杂性，但这是生成器版本的下限。每次yield，生成的值都会在递归生成器调用链中向上传递，每次传递一个级别，直到最终被顶级调用使用为止。然后，当链恢复时，生成器迭代器帧的堆栈一次重新激活一个，直到返回到原始yield

因此，在生成器版本中，在depth(tree)中有一个二次时间分量。但是，除非树很深，否则您可能永远不会注意到这一点，因为在CPython中，所有堆栈的展开和回放都是“以C速度”进行的