时间戳

首页 > 解决方案 > 当递归非常深入时，理解中的递归调用有什么特别之处？

python - 当递归非常深入时，理解中的递归调用有什么特别之处？

问题描述

我注意到当我在列表推导中使用递归时会发生一些奇怪的事情。如果递归太深，解释器似乎会空闲（我等了 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。

标签： pythonrecursionlist-comprehensionjupyter

解决方案

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

在第二种（生成器）方法中，它达到了深度为2**12. 这意味着2**11应该在第一种方法中达到递归限制。这是因为 list-comprehensions 创建了一个额外的堆栈帧，所以它是生成器解决方案的两倍。它没有抛出 RecursionError 的事实意味着解释器发生了“致命”的事情（或者某处存在无限循环）。

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

如果您更改 Python 递归限制或使用为您更改它的解释器，这就是您非常小心的原因之一。

推荐阅读