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

最近我尝试用GCC编译这样的程序:

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

它运行得很好.当我检查堆栈帧时,编译器优化程序只使用一个帧,只需跳回函数的开头,只将参数替换为f.而且 - 编译器甚至没有以优化模式运行.

现在,当我在Python中尝试相同的事情时 - 我点击了最大递归墙(或者如果我将递归深度设置得太高,则可能是堆栈溢出).

像python这样的动态语言是否可以利用这些优秀的优化？也许可以使用编译器而不是解释器来完成这项工作？

只是好奇!

您正在谈论的优化称为尾调用消除 - 递归调用展开到迭代循环中.

已经对此进行了一些讨论,但目前的情况是,这不会被添加,至少对cpython是正确的.有关讨论,请参阅Guido的博客文章.

但是,确实存在一些 操纵函数来执行此优化的装饰器.它们通常只获得节省空间,而不是时间(事实上,它们通常较慢)

当我检查堆栈帧时,编译器优化程序只使用一个帧,只需跳回函数的开头,只将参数替换为f.

你所描述的被称为"尾递归".有些编译器/口译员支持它,有些则不支持.事实上,大多数人都没有.正如你所注意到的,gcc确实如此.实际上,尾递归是Scheme编程语言规范的一部分,因此所有Scheme编译器/解释器都必须支持尾递归.另一方面,Java和Python等语言的编译器(以及大多数其他语言,我都打赌)不进行尾递归.

像python这样的动态语言是否可以利用这些优秀的优化？

你的意思是,现在,还是你用更抽象的术语提问？抽象地说,是的!动态语言绝对有可能利用尾递归(例如,Scheme).但具体来说,不,CPython(规范的Python解释器)没有标志或其他参数来启用尾递归.