python - 当我们递归使用 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)
                

我更关心 Python 2，但可能很高兴知道 Python 3 的答案是否不同。

Answer 1

在 CPython 中，每次调用 iterInOrder()创建一个新的生成器迭代器，无论 Python 版本如何，无论它是顶级调用还是递归调用。
同样，每次调用 visitInOrder()无论 Python 版本或上下文如何，都会创建一个新的堆栈帧。
所以空间复杂度是O(depth(tree))无论哪种方式(通常，它与节点数没有有用的关系 - 树可能是 n 层深，或 2 层深)。
时间是一个不同的计算，但很微妙，因为它几乎不会被注意到:递归版本有 O(n)时间复杂度，但这是生成器版本的下限。每次您yield ，产生的值被传递到递归生成器调用链上，一次一层，直到最终被顶层调用消耗。然后，当链恢复时，生成器-迭代器帧堆栈一次重新激活一个，直到回到原始 yield .
所以在生成器版本中，depth(tree) 中有一个时间分量二次方。 .但是除非树很深，否则您可能永远不会注意到这一点，因为在 CPython 中，所有堆栈展开和重绕都是“以 C 速度”发生的。