聪明的基于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）个项目后，生成器才会达到该限制。我不会屏住呼吸等着的。在