代码之家 › 专栏 › 技术社区 › MSeifert

当递归非常深入时,递归调用在理解中有什么特别之处?

jupyter list-comprehension recursion python

MSeifert · 技术社区 · 6 年前

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

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

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

使用helper函数创建嵌套列表:

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上使用python64位3.6.6。

2 回复 | 直到 6 年前

MSeifert 6 年前

发生的是一个简单的stackoverflow 之前已达到递归限制。

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

但是它不是无限循环,因为如果检查jupyter lab响应(例如,如果从命令行启动 jupyter lab )在运行 flatten(wrap_in_lists(1, 2**11)) 行它将打印 kernel <xyz> restarted .所以没有响应是不正确的,内核崩溃了,并且 [*] 在本例中显示在jupyter实验室的单元格中只是表示计算没有完成(因为崩溃)。

这就是为什么你 真的很小心 如果您更改pythons递归限制或使用更改它的解释器为你是的。

-1

nosklo 6 年前

我不知道为什么在你的案子里这个错误会被掩盖。我不能在这里复制。我尝试了很多值,它要么给出错误,要么起作用。

>>> 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。