为什么返回自身的函数在Python 3中会导致递归达到上限

Question

为什么这段代码会出现错误：RuntimeError: maximum recursion depth exceeded during compilation？print_test 并没有调用自己，所以我觉得它不是一个递归函数。

def print_test():
    print("test")
    return print_test

print_test() #prints 'test'
print()

#a quick way of writing "print_test()()()()()()()()()()()()()..."
eval("print_test"+"()"*10000) #should print 'test' 10000 times

我测试的时候发现，它在 Python 2.7.7rc1 里能正常运行，但在 Python 3.3.5 里却报错。使用调试工具 Pdb 时，看到的调用栈很短，不像通常超过最大递归深度时那样很长。

Traceback (most recent call last):
  File "/usr/lib/python3.3/pdb.py", line 1662, in main
    pdb._runscript(mainpyfile)
  File "/usr/lib/python3.3/pdb.py", line 1543, in _runscript
    self.run(statement)
  File "/usr/lib/python3.3/bdb.py", line 405, in run
    exec(cmd, globals, locals)
  File "<string>", line 1, in <module>
  File "/home/beet/overflow.py", line 1, in <module>
    def print_test():

我出于好奇在想这个问题，并意识到这并不是最佳的编程实践。

Answer 1

eval 是用来编译代码的。它可以发现你想要进行更深层次的嵌套调用，这个深度可能超过了 sys.getrecursionlimit() 设置的限制。

递归可以是直接的（函数直接调用自己）或者间接的（一个函数被另一个函数调用，而这个函数又曾经被第一个函数调用过）。但是当调用的深度超过预期（在写这段内容时，Python 的默认深度是 1000），这个调用可能是间接递归的一部分，需要更深的调用才能表现出它是“递归”的。换句话说，如果达到了最大调用深度（并且这个深度是合理的），可以称之为“无法进行的递归”。

确切的答案可以在其他资料中找到……但我只是出于好奇，做了一个实验。我尝试写代码定义足够多的不同函数（用编号标识），这些函数依次调用下一个函数——除了最后一个，它实际上并没有递归地调用第一个函数。

def fn1():
    print('fn1() is going to call fn2()')
    fn2()

def fn2():
    print('fn2() is going to call fn3()')
    fn3()

def fn3():
    print('fn3() does not call anything.')

fn1()

最后一行开始了嵌套调用，并且它会打印输出。

fn1() is going to call fn2()
fn2() is going to call fn3()
fn3() does not call anything.

我们可以将源代码生成一个字符串，然后使用 compile 内置函数，再用 exec 执行它：

#!python3
import textwrap

n = 1000
print('n =', n)

lst = []
for i in range(1, n+1):
    if i == n:
        fndef = textwrap.dedent('''\
            def fn{}():
                print('fn{}() does not call anything.')

            fn1()
            '''.format(i, i))
    else:
        fndef = textwrap.dedent('''\
            def fn{}():
                print('fn{}() is going to call fn{}()')
                fn{}()
            '''.format(i, i, i+1, i+1))

    if n <= 10:
        print(fndef)
    lst.append(fndef)

ast = compile('\n'.join(lst), '<string>', 'exec')
exec(ast)

注意源代码开头的 n = 1000。当执行时，并将标准输出和错误输出重定向到文件中，我观察到了：

n = 1000
fn1() is going to call fn2()
fn2() is going to call fn3()
fn3() is going to call fn4()
...
fn992() is going to call fn993()
fn993() is going to call fn994()
fn994() is going to call fn995()

Traceback (most recent call last):
  File "a.py", line 28, in <module>
    exec(ast)
  File "<string>", line 4000, in <module>
  File "<string>", line 3, in fn1
  File "<string>", line 7, in fn2
  File "<string>", line 11, in fn3
  ...
  File "<string>", line 3967, in fn992
  File "<string>", line 3971, in fn993
  File "<string>", line 3975, in fn994
  File "<string>", line 3978, in fn995
RuntimeError: maximum recursion depth exceeded

结论： Python 在 eval 中称之为 递归，不仅在递归时，而且在还没有执行的时候（正如问题所示）。即使实际上没有递归，Python 也可能称之为 递归。

更好的结论： 谁在乎呢？当代码显然可能是递归或不是递归时，无论是在编译时还是运行时，反正代码都不会工作 :)

Answer 2

我觉得这跟问题 #5765有关。

在编译器中设置了一个严格的递归限制 [从3.3版本开始]

我不是百分之百确定，但这段代码在3.2.3版本上可以运行：

def f():
    return f

eval("f" + "()" * 10000)

但是在我的3.4.1版本上就失败了，这让我怀疑是这个改动导致的。如果有人能确认或否定这一点，那就太好了。