为什么这个错误抛出的递归Python函数在最后几次调用中来回跳转？

Question

考虑一下这个递归函数,由我的一位同事挖掘出来:

def a():
    try:
        a()
    except:
        a()

如果你运行它,(Python 2.7)解释器挂起.这让我感到惊讶,因为我预计一旦递归深度(比如N)被击中它就会抛出一个RuntimeError,跳到第(N-1)个except区块,得到另一个RuntimeError,跳到第(N-2)个except等等.

所以我充实了调试功能:

y = 10000

def a(x=0):
  global y
  if y:
    y -= 1
    try:
      print "T: %d" % x
      a(x+1)
    except RuntimeError:
      print "E: %d" % x
      a(x+1)

该y仅仅是有给力的功能在某些时候结束,我不认为它,否则转换功能的行为.在我的解释器中(递归限制为1000),调用a()产生如下序列:

T: 998
E: 998
E: 997
T: 998
E: 998
E: 990
T: 991
T: 992
T: 993
T: 994
T: 995
T: 996
T: 997
T: 998
E: 998
E: 997
T: 998
E: 998
E: 996

看着较长的序列,我无法从中看出任何真实的模式(虽然我承认我没有尝试绘制它).我认为可能堆栈在N和NM调用之间来回反弹,其中M在每次递归深度被触发时递增.但是看起来并不重要y,堆栈永远不会超过大约八次调用.

那么Python内部真正发生了什么？这种行为有一种模式吗？

Answer 1

这是一个有趣的问题.您的预期行为不是现实的原因似乎是当引发RuntimeError时,关闭了违规的"太递归"堆栈帧.这意味着当异常被捕获在下一个较低的堆栈帧中时,该帧可以再次向上递归直到达到限制.

也就是说,你预计一旦递归深度(比如N)被击中它就会:

1. 抛出一个RuntimeError
2. 跳到第(N-1)个除了块
3. 得到另一个RuntimeError
4. 跳到第(N-2)个除外
5. 等等

实际上会发生什么:

1. 抛出一个RuntimeError
2. 跳到第(N-1)个除了块
3. 再一次递归到N.
4. 得到另一个RuntimeError
5. 跳到第(N-2)个除外
6. 再一次递归到N.
7. 等等

此外,必须使用异常 - recurse-exception的相同增量过程解开每个"再次递归到N".因此,递归比你预期的多得多.

在您的输出中很难看到的原因是您的原始代码不区分具有相同x值的多个调用.进行第1001次调用时,第1000次调用中的异常将控制权返回给第999次调用.然后,此调用再次调用x=1000,创建具有特定x值的调用的并行"谱系" .

通过修改原始代码可以看到行为,如下所示:

y = 2000

def a(x=0, t=''):
    print(t + "In a({0})".format(x))
    global y
    if y:
        y -= 1
        try:
            a(x+1, t)
        except RuntimeError:
            print(t + "*** E: %d" % x)
            a(x+1, t+'\t')

这会添加缩进,以便您可以查看哪些调用进入了哪些其他调用.结果输出的示例是:

In a(986)
In a(987)
*** E: 987
*** E: 986
    In a(987)
    *** E: 987
*** E: 985
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
*** E: 984
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
*** E: 983
    In a(984)
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
    *** E: 984
        In a(985)
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
        *** E: 985
            In a(986)
            In a(987)
            *** E: 987
            *** E: 986
                In a(987)
                *** E: 987

(由于某种原因,我的解释器首先在第988次调用而不是第1000次调用时生成错误,但这并没有太大变化.)您可以看到每个错误只会在层次结构中向后移动一步,允许整个森林发生"嵌套递归".

这导致呼叫数量呈指数增长.事实上,我通过将递归限制设置为一个较小的值(我试过20和25)来测试这一点,并确认递归最终会终止.在我的系统上,它在2**(R-12)总调用后终止,其中R是递归限制.(12是递归限制与实际引发第一个异常的数量之间的差异,如我的例子中所示,当第一个异常在N = 988处被提出时;可能这些12个帧在某种程度上被内部"使用"了我的翻译.)

你的翻译似乎挂起并不足为奇,因为限制为1000,这将比宇宙的年龄要长得多.