聪明的基于streams的python程序不会遇到无限递归

Question

我一直在研究如何为序列A003602创建一个python生成器

这似乎有用，但我不明白为什么。在我看来，它应该达到无限递归。python在我不认识的地方做了一些懒惰的评估吗？在

def N():
    i=1
    while True:
        yield i
        i+=1

def interleave(a,b):
    def result():
        x=a()
        y=b()
        while True:
            yield next(x)
            yield next(y)
    return result

def RZ():
    return interleave(N,RZ)()

gen=RZ()

在我看来，由于RZ立即调用interleave返回的方法，而interleave又调用b，即RZ（在第一次调用yield之前），这应该是无限递归。但实际上这似乎是有效的。有人能解释一下为什么吗？在

Answer 1

其他答案解释了为什么不存在立即无限递归问题（因为生成器的解释是惰性的）。但是，我认为考虑一下何时可能达到Python解释器中存在的递归的有限限制也是很有趣的。在

首先，我注意到您的代码可以简化一点（您的函数比实际需要的还要多，而且您的N生成器与itertools.count(1)完全相同）。下面是一个更简单的生成器版本：

from itertools import count

def RZ():
    x=count(1)
    y=RZ()
    while True:
        yield next(x)
        yield next(y)

样本输出：

^{pr2}$

接下来，我编写了一个函数，该函数可以对嵌套生成器进行反省，并计算它们被计算的深度。我不确定这段代码是否可以在python版本之间移植（我使用的是2.7）：

def getDepth(gen):
    depth = 0
    while gen:
        depth += 1
        gen = gen.gi_frame.f_locals.get("y")
    return depth

输出（索引、深度、值）：

>>> for i in range(1, 21):
    print i, getDepth(gen), next(gen)

1 1 1
2 2 1
3 3 2
4 3 1
5 4 3
6 4 2
7 4 4
8 4 1
9 5 5
10 5 3
11 5 6
12 5 2
13 5 7
14 5 4
15 5 8
16 5 1
17 6 9
18 6 5
19 6 10
20 6 3

这些深度值呈对数增长。具体地说，生成序列的第n个值所需的嵌套生成器的深度是ceil(log(N, 2)) + 1。在

在我的Python副本中，递归允许（默认情况下）达到100级深度。只有在生产了2^99+1（=63382530014114700748351602689）个项目后，生成器才会达到该限制。我不会屏住呼吸等着的。在

Answer 2

To me it seems like since RZ instantly calls the method returned by interleave which in turn calls b which is RZ (before the first call to yield),调用包含yield的函数将返回一个迭代器对象，直到开始迭代时才会对其求值，因为这样的RZ也返回迭代器，因为它调用的result具有yield，因此它最初返回一个迭代器，即RZ返回迭代器。在

yield next(x)将调用yield i并停止，再次调用迭代器yield next(y)将调用x = a(); y = b(); while True: yield next(x)并停止，依此类推，它似乎在不断地创建生成器，虽然不是很快，但这可能是好的，也可能不是很好。。。在

count = 0
def N():
    i=1
    global count
    count += 1
    while True:
        yield i
        i+=1

def interleave(a,b):
    def result():
        global count
        count += 1
        x=a()
        y=b()
        while True:
            yield next(x)
            yield next(y)
    return result

def RZ():
    return interleave(N,RZ)()

gen = RZ() # 1) call RZ

gen = RZ()
r = [next(gen) for index in xrange(100)]
print count

它生成了14个迭代器对象，经过100次迭代，1000次后20次，10000次后28次，100000次后34次，速度相当慢。。。在

Answer 3

生成器（任何带有yield语句的函数）都是惰性的。这意味着result()在您从中请求第一个值之前不会开始处理，而您不会这样做。在

这里的根本原因是您首先从x请求一个值。这意味着生成器在至少请求第二个值之前永远不会询问它的子生成器。考虑一个更简单的例子：

def test():
    yield 1
    a = test()
    while True:
        yield next(a)

a = test()
for i in range(10):
    print(next(a))

这和你的一样有效。它有无限递归的潜力，但只有当你要求这么多的值时，它才会走得那么远。您所要做的就是删除yield 1以获得预期的行为。在您的代码中，只需切换N和RZ并请求下一个值-您将得到预期的递归。在