3

考虑这个由我的同事开发的递归函数：

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

如果你运行它，（Python 2.7）解释器就会挂起。这让我感到惊讶，因为我预计一旦递归深度（比如 N）被击中，它就会抛出 a 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，堆栈的展开次数永远不会超过 8 次。

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

4

1 回答 1

5

这是一个有趣的问题。您的预期行为不是现实的原因似乎是当引发 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. 等等

此外，必须使用相同的异常-递归-异常增量过程来展开每个“再次递归直到 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，这将需要比宇宙年龄更长的时间才能完成。

于 2013-09-04T04:07:20.967 回答