当我们递归地使用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速度"；。