当递归变得非常深时,理解中的递归调用有什么特别之处？

Question

我注意到当我在列表理解中使用递归时会发生一些奇怪的事情.如果递归过深,解释器似乎空闲(我等了5分钟,什么都没发生).

为了这个问题,假设我想要展平嵌套列表(我没有 - 但它是一个简短的代码示例,说明了我遇到的问题):

def flatten(x):
    if isinstance(x, list):
        return [a for i in x for a in flatten(i)]
    else:
        return [x]

使用辅助函数创建嵌套列表:

def wrap_in_lists(value, depth):
    a = value
    for _ in range(depth):
        a = [a]
    return a

使用时效果很好:

>>> flatten(wrap_in_lists(1, 2**10))
[1]

但是当我使用时它完全停止:

>>> flatten(wrap_in_lists(1, 2**11))
# Nothing happens, no exception, no result, no segfault, ...

我的问题是:这里发生了什么？为什么根本没有回应？

---

奇怪的是,使用生成器的类似方法不会显示此行为:

def flatten(l):
    def inner(x):
        for item in x:
            if isinstance(item, list):
                yield from inner(item)
            else:
                yield item
    return list(inner(l))

>>> flatten(wrap_in_lists(1, 2**11))
[1]

>>> # although increasing the depth leads to an recursion error
>>> flatten(wrap_in_lists(1, 2**12))
RecursionError: maximum recursion depth exceeded

如果重要的是我在一个jupyter实验室的Windows上使用Python 64bit 3.6.6.

Answer 1

这是一个简单的StackOverflow,它在达到递归限制之前发生.

在第二个(生成器)方法中,它达到了递归限制,深度为2**12.这意味着2**11应该在第一种方法中达到递归限制.这是因为list-comprehensions创建了一个额外的堆栈帧,因此它是堆栈帧的两倍而不是生成器解决方案.事实上它没有抛出RecursionError意味着解释器发生了某些"致命"(或者某处存在无限循环).

然而,它不是一个无限循环,因为如果您检查jupyter实验室响应(例如,如果您从命令行启动它jupyter lab),您会注意到在运行该flatten(wrap_in_lists(1, 2**11))行后不久它将打印出来kernel <xyz> restarted.因此,没有响应是不正确的,内核刚刚崩溃,[*]在这种情况下在jupyter lab单元格中显示只是意味着计算没有完成(因为崩溃).

如果您更改Pythons递归限制或使用为您更改它的解释器,那么这就是您真正非常小心的原因之一.