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

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 64位3.6.6。

Answer 1

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

在第二种(生成器(方法中，它达到了深度为2**12的递归极限。这意味着2**11应该已经达到了第一种方法中的递归极限。这是因为列表理解创建了一个额外的堆栈框架，所以它是生成器解决方案的两倍。事实上，它没有抛出RecursionError意味着解释器发生了"致命"的事情(或者某个地方有一个无限循环(。

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

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

Answer 2

我不知道为什么在您的情况下错误会被消除。我不能在这里复制它。我尝试了许多值，但它要么出错，要么有效。

>>> sys.setrecursionlimit(3000)
>>> flatten(wrap_in_lists(1, 2**10)) #works
[1]
>>> flatten(wrap_in_lists(1, 2**11)) #fails with exception
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
...
RecursionError: maximum recursion depth exceeded

我还在jupyter笔记本中使用python3。