检测Python或动态语言中的无限递归

Question

最近我尝试用GCC编译一个类似这样的程序：

int f(int i){
    if(i<0){ return 0;}
    return f(i-1);
f(100000);

结果运行得很好。当我查看堆栈帧时，发现编译器优化了这个程序，只用了一个堆栈帧，它通过跳回函数的开头来实现，只是替换了传给函数f的参数。而且——编译器甚至没有在优化模式下运行。

但是，当我在Python中尝试同样的事情时，我遇到了最大递归限制（如果我把递归深度设置得太高，可能会导致堆栈溢出）。

有没有办法让像Python这样的动态语言也能利用这些不错的优化呢？也许可以用编译器而不是解释器来实现这个效果？

我只是好奇！

Answer 1

这和它是一种动态语言或者是解释型语言没有关系。CPython就是没有实现尾递归优化。而你可能会发现像JPython之类的其他语言是有这个优化的。

Answer 2

当我检查程序的调用栈时，发现编译器优化了程序，只用了一个调用栈帧，它通过直接跳回函数的开头，并只替换参数来实现。

你说的这个情况叫做“尾递归”。有些编译器或解释器支持尾递归，有些则不支持。实际上，大多数是不支持的。正如你注意到的，gcc是支持的。而且，尾递归是Scheme编程语言规范的一部分，所以所有的Scheme编译器和解释器都必须支持尾递归。另一方面，像Java和Python这样的语言的编译器（我敢打赌大多数其他语言也是如此）并不支持尾递归。

像Python这样的动态语言有没有办法利用这些不错的优化呢？

你是问“现在”是否可以，还是在更抽象的层面上问？从抽象的角度来看，是的！动态语言完全可以利用尾递归的优化（比如Scheme就做到了）。但从具体的角度来看，不行，CPython（标准的Python解释器）没有任何标志或参数可以启用尾递归。

Answer 3

你提到的优化叫做尾调用消除，这是一种把递归调用转换成循环的技术。

关于这个话题有过一些讨论，但目前的情况是，这个功能不会被加入到cpython的正式版本中。你可以看看Guido的博客，里面有一些相关的讨论。

不过，确实存在一些装饰器，可以对函数进行处理，从而实现这种优化。一般来说，这些装饰器主要是节省内存，而不是提高速度（实际上，它们通常会更慢）。