您最喜欢的语言如何处理深度递归？ [关闭]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我最近开始学习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<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
我很好奇其他语言（例如，PHP，Ruby，Java，Lua，Ocaml，Haskell）如何处理递归以及它们为何如此处理它。另外，请注意，如果函数是<！>“tail-recursive <！>”，它是否会有所不同; （见评论）。
解决方案
<！>“Python人员很快指出，您总是可以将递归函数转换为迭代函数，并且它们总是更快<！>;
这是真的，但是如果它真的那么简单，为什么Python不能为我做这些，所以我的代码看起来尽可能简单？ （我说这不是为了抨击Python实现者，但因为答案解释了这个问题）。
递归优化已经存在于函数式语言中，就像14世纪一样。 Haskell，CAML，Lisp实现通常都将至少尾递归函数转换为迭代：你基本上通过发现它是可能的来做到这一点，即函数可以重新排列，使得在递归调用之后不使用除返回值之外的局部变量。如果在返回之前对递归返回值进行了一些工作，那么可以使用一个技巧：引入一个额外的<！> quot; accumulator <！>;参数。简单来说，这意味着工作可以在<！> quot; down <！>的方式上有效地完成。而不是在路上<！>“; up <！>”;：搜索“如何使函数尾递归”以获取详细信息。
将尾递归函数转换为循环的实际细节基本上是用你的调用约定跳转，这样你就可以<！>执行调用<！>只需设置参数并跳回函数的开头，无需在您知道不会使用的范围内保存所有内容。在汇编语言中，如果数据流分析告诉您它们在调用之外未被使用，则不必保留调用者保存寄存器，并且堆栈上的任何内容都是如此：您不必移动堆栈指针在你打电话的时候如果你不介意<！>你的<！>堆栈的位被下一个递归/迭代潦草地写下来。
与你对Python人员的解释相反，将一般递归函数转换为迭代并非易事：例如，如果它是多次递归的，那么在一个简单的方法中你仍然需要一个堆栈。
对于任意递归函数，记忆是一种有用的技术，如果您对可能的方法感兴趣，可能希望查找。这意味着每次评估函数时，都会将结果粘贴到缓存中。为了使用它来优化递归，基本上，如果你的递归函数计算<！> quot; down <！>，并且你记住它，那么你可以通过添加一个计数<！> quot; up <的循环来迭代地评估它。 ！> QUOT;依次计算函数的每个值，直到达到目标。这使用非常少的堆栈空间，前提是备忘录缓存足以容纳您需要的所有值：例如，如果f（n）取决于f（n-1），f（n-2）和f（n） -3）你只需要在缓存中有3个值的空间：当你上去时你可以踢掉梯子。如果f（n）依赖于f（n-1）和f（n / 2），则缓存中需要大量空间，但仍然比未经优化的递归中的堆栈空间少。
其他提示
这更像是一个实现问题，而不是一个语言问题。没有什么能阻止一些（stoopid）C编译器实现者将他们的调用堆栈限制为1000.那里有很多小型处理器，即使有很多也没有堆栈空间。
（Python人员很快指出，你总是可以将递归函数转换为迭代函数，并且它们总是更快。这是100％正确。虽然我的问题不是真的。）
也许他们这么说，但这不太正确。递归总是可以转换为迭代，但有时它也需要手动使用堆栈。在这种情况下，我可以看到递归版本更快（假设你足够聪明，可以进行简单的优化，比如在递归例程之外删除不需要的声明）。毕竟，堆栈推送周围的过程调用是一个很好的问题，你的编译器应该知道如何优化。另一方面，手动堆栈操作不会在编译器中具有专门的优化代码，并且可能会进行各种用户界面健全性检查，这将需要额外的周期。
迭代/堆栈解决方案可能总是在Python 中更快。如果是这样，那就是Python的失败，而不是递归。
PHP在死亡之前的默认限制为100：
Fatal error: Maximum function nesting level of '100' reached, aborting!
编辑：您可以使用ini_set('xdebug.max_nesting_level', 100000);更改限制，但如果超过大约1150次迭代，PHP崩溃：
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C＃/ .NET将在特定情况下使用尾递归。 （C＃编译器不会发出尾调操作码，但 JIT将在某些情况下实现尾递归。
Shri Borde 也有关于此主题的帖子。当然，CLR会不断变化，而对于.NET 3.5和3.5SP1，它可能会在尾部调用方面再次发生变化。
在F＃交互式控制台中使用以下内容，它在不到一秒的时间内运行：
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
结果相同但编译不同。
这是 f 在转换为C＃时的样子：
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g 被翻译成：
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
有趣的是，F＃编译器对两个基本相同的函数进行了不同的渲染。它还表明F＃编译器具有尾递归优化。因此，这应该循环，直到我达到32位整数的限制。
在一些非病理情况下（如你的），（最新）Lua将使用尾调用递归，即。它只会跳转而不会在堆栈中推送数据。因此，递归循环的数量几乎是无限的。
经过测试：
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
还有：
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
甚至尝试了交叉递归（f调用g和g调用f ...）。
在Windows上，Lua 5.1使用大约1.1MB（常量）来运行它，在几秒钟内完成。
在较旧的白色macbook上运行ruby 1.9.2dev（2010-07-11修订版28618）[x86_64-darwin10.0.0]：
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
为我输出9353，这意味着Ruby会在堆栈上少于10,000次调用时出现问题。
使用交叉递归，例如：
def f
@i += 1
g
end
def g
f
end
我可以通过在proc：
中包装递归调用来挤出几次迭代def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
在错误输出之前达到4850。
Visual Dataflex将堆栈溢出。
我非常喜欢函数式编程，并且由于大多数语言实现了尾部调用优化，因此您可以尽可能多地递归:-P
然而，实际上，我必须使用大量的Java并且也使用Python。不知道Java有什么限制，但是对于Python我实际上已经计划（但还没有完成）实现一个装饰器，它会调用优化装饰函数。 我计划不优化递归，但主要是作为动态修补Python字节码和学习更多关于Pythons内部的练习。 下面是一些非常有用的链接： http://lambda-the-ultimate.org/node/1331和 http://www.rowehl.com/blog/?p=626
有一种方法可以改进Perl代码，使其使用常量大小的堆栈。您可以使用goto的特殊形式执行此操作。
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
首次调用时，它将在堆栈上分配空间。然后它将更改其参数，并重新启动子例程，而不向堆栈添加任何其他内容。因此，它会假装它从不称呼它自己，将它改变为一个迭代过程。
你也可以使用 Sub :: Call :: Recur 模块。这使得代码更容易理解，也更短。
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure 为尾递归提供了一种特殊形式<！> quot; recur <！> quot;这只能用于ast的尾部。否则它的行为就像java一样，可能会引发StackverflowException。
