您最喜欢的语言如何处理深度递归？

我最近开始学习Python,我很惊讶地发现1000深度递归限制(默认情况下).如果你把它设置得足够高,大约30000,就会像C一样崩溃.但是,C似乎要高得多.

(Python人员很快指出,你总是可以将递归函数转换为迭代函数,并且它们总是更快.这是100%正确.但这不是我的问题所在.)

我在Perl中尝试了相同的实验,并且在大约1000万次递归中它消耗了我所有的4个ram并且我使用了^ C来停止尝试.显然,Perl不使用C堆栈,但它在执行时会使用大量的内存 - 考虑到调用函数需要做多少工作,这并不是非常令人震惊.

我在Pike尝试过,并且在大约2秒钟内完成100,000,000次递归完全感到惊讶.我不知道它是如何做到的,但我怀疑它将递归转换为迭代过程 - 它似乎没有消耗任何额外的内存.[注意:Pike确实会使琐碎的案件变得扁平化,但是对于更复杂的案件会发生段错误,或者我被告知.]

我使用了这些无用的功能:

int f(int i, int l) { if(i

我很好奇其他语言(例如,PHP,Ruby,Java,Lua,Ocaml,Haskell)如何处理递归以及它们为何如此处理它.另外,请注意,如果函数是"尾递归"(请参阅​​注释),它是否会有所不同.


1> Steve Jessop..：
"Python人员很快指出,您总是可以将递归函数转换为迭代函数,并且它们总是更快"

这是真的,但是如果它真的那么简单,为什么Python不能为我做,所以我的代码看起来尽可能简单？(我说这不是为了抨击Python实施者,而是因为答案解释了这个问题).

递归优化已经存在于函数式语言中,就像14世纪一样.Haskell,CAML,Lisp实现通常都将至少尾递归函数转换为迭代:你基本上通过发现它是可能的来做到这一点,即函数可以重新排列,使得在递归调用之后不使用除返回值之外的局部变量.如果在返回之前对递归返回值进行了一些工作,那么可以使用一个技巧是引入一个额外的"累加器"参数.简单来说,这意味着可以在"向下"而不是"向上"的方式上有效地完成工作:搜索"如何使函数尾递归"以获取详细信息.

将尾递归函数转换为循环的实际细节基本上是用你的调用约定跳转,这样你就可以通过设置参数并跳回函数的开头来"执行调用",而无需保存所有这些在你知道你永远不会使用的范围内的东西.在汇编语言中,如果数据流分析告诉您它们在调用之外未被使用,则不必保留调用者保存寄存器,并且堆栈上的任何内容都是如此:您不必移动堆栈指针如果你不介意在下一次递归/迭代中乱写"你的"堆栈,那么在一个电话上.

与你对Python人员的解释相反,将一般递归函数转换为迭代并非易事:例如,如果它是多次递归的,那么在一个简单的方法中你仍然需要一个堆栈.

但是,对于任意递归函数,Memoization是一种有用的技术,如果您对可能的方法感兴趣,可能需要查找.这意味着每次评估函数时,都会将结果粘贴到缓存中.要使用它来优化递归,基本上,如果你的递归函数计数"向下",并且你记住它,那么你可以通过添加一个循环计算"向上"依次计算函数的每个值来迭代地评估它,直到你到达目标.这使用非常少的堆栈空间,前提是备忘录缓存足以容纳您需要的所有值:例如,如果f(n)取决于f(n-1),f(n-2)和f(n) -3)你只需要在缓存中有3个值的空间:当你上去时你可以踢掉梯子.如果f(n)取决于f(n-1)和f(n/2),

        
+1为"为什么Python不为我做"...许多人不会遗漏和这里涉及的甜蜜讽刺. 

2> T.E.D...：
这更像是一个实现问题,而不是一个语言问题.没有什么能阻止某些(stoopid)C编译器实现者将他们的调用堆栈限制为1000.那里有许多小型处理器,即使有很多也没有堆栈空间.


  
(Python人员很快指出,你总是可以将递归函数转换为迭代函数,并且它们总是更快.这是100%正确.但这不是我的问题所在.)


也许他们确实这么说,但这不太正确.递归总是可以转换为迭代,但有时它也需要手动使用堆栈.在这种情况下,我可以看到递归版本更快(假设你足够聪明,可以进行简单的优化,比如在递归例程之外删除不需要的声明).毕竟,堆栈推送周围的过程调用是一个很好的问题,你的编译器应该知道如何优化.另一方面,手动堆栈操作不会在编译器中具有专门的优化代码,并且可能会进行各种用户界面健全性检查,这将需要额外的周期.

情况可能是Python中的迭代/堆栈解决方案总是更快.如果是这样,那是Python的失败,而不是递归.