问Python生成器表达式递归

EN

显然，在每一层传递时都需要保存变量的上下文，例如，每一层都“看到”不同的n。

是的，这不是特定于生成器，而是任何函数调用:如果该函数调用一个函数(可能是它本身)，那么它的局部变量将保留在堆栈框架中，而新的函数执行上下文将得到它自己的一组局部变量。

它是否为每个嵌套的生成器调用添加了堆栈框架？

是。因此，在sieve的情况下，sieve的每个执行上下文都有自己的n和s变量。

在sieve传递给递归调用的表达式中，它是从它作为参数获得的现有迭代器中创建一个新的、限制性更强的迭代器。我们可以反向工作，看看完整的迭代器是什么样子的。

第一个递归调用可以展开为：

yield from sieve(i for i in 
                   (i for i in nat(3))   # this is roughly `s`
                 if i % 2 != 0)

我编写nat(3)而不是nat(2)，因为值2已经从那个迭代器中使用了。

然后，该递归调用将产生3，并进行下一次递归调用：

yield from sieve(i for i in 
                   i for i in                 # }
                     (i for i in nat(3))      # } this is roughly `s` 
                   if i % 2 != 0 and i != 3)  # }
                 if i % 3 != 0)

我再次添加and i != 3，因为3已经被单独的next(s)调用占用了。

...and，所以它继续。

实际局限性

正如你所能想象的，这是非常消耗内存的。在每次递归调用时，调用堆栈的使用都会增加，迭代器嵌套结构中的每个迭代器都是sieve执行上下文中的变量sieve，必须完成其工作。

虽然从理论角度看，这看起来很优雅，但在实际实现中却不实用:在遇到“超过最大递归深度”之前，您可以生成的素数很少，这让人失望。在repl.it上运行它时，在错误发生之前生成的最后一个素数是3559。

FWIW，您可以通过删除递归并在生成器内使用一个循环来避免堆栈溢出。这会让你产生更大的素数，但这不是免费的午餐。您仍然通过捕获所有生成器对象来消耗内存，而不是通过递归来完成。它将逐渐变慢，最终耗尽资源：

def nats(n): 
    while True:
        yield n
        n += 1


def sieve(s):
    while True:
        n = next(s)
        yield n
        s = filter(lambda i, n=n: i % n != 0, s)


s = sieve(nats(2))

# generate the 3000th prime
for x in range(3000):
    n = next(s)

print(n)
# 27449

如你所见，在这段代码的可视化演示中，

每个yield from都会创建一个新的堆栈框架和一个新的生成器对象。

我认为nats可以很容易地重写为使用循环而不是recurse。然而，sieve很可能更难重写，以保持这一想法。