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

Question

考虑这个递归函数，由我的一位同事开发:

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

如果您运行它，(Python 2.7) 解释器会挂起。这让我感到惊讶，因为我预计一旦达到递归深度(比如 N)，它就会抛出一个 RuntimeError，跳转到第 (N-1) 个 except block ，得到另一个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 和 N-M 调用之间来回跳动，其中每次递归深度达到时 M 都会递增。但是 y 有多大似乎并不重要，堆栈展开的调用不会超过大约八次。

那么 Python 内部到底发生了什么？这种行为有规律吗？

Answer 1

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

也就是说，您预计一旦达到递归深度(比如 N)，它就会:

1. 抛出运行时错误
2. 跳转到第(N-1)个 block
3. 得到另一个RuntimeError
4. 跳转到第(N-2)个除了
5. 等等

实际情况是:

1. 抛出运行时错误
2. 跳转到第(N-1)个 block
3. 再次递归直到 N
4. 得到另一个RuntimeError
5. 跳转到第(N-2)个除了
6. 再次递归直到 N
7. 等等

此外，每个“再次递归一直到 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，这将需要比宇宙年龄更长的时间才能完成。