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

Question

我最近开始学习 Python，我很惊讶地发现深度递归限制为 1000（默认情况下）。 如果你将它设置得足够高，大约 30000，它会像 C 一样因分段错误而崩溃。尽管如此，C 似乎要高得多。

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

我在 Perl 中尝试了相同的实验大约 1000 万次递归它消耗了我所有的 4 GB 内存，我使用 ^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）处理递归以及为什么他们这样处理。 此外，请注意如果函数是“尾递归”，这是否会产生影响（请参阅评论）。

Answer 1

“Python 的人很快就指出，你总是可以将递归函数转换为迭代函数，而且它们总是更快”

这是事实，但如果它真的那么简单，为什么 Python 不为我做呢，以便我的代码看起来尽可能简单？ （我这么说并不是为了抨击 Python 实现者，而是因为答案解释了问题）。

递归优化从 14 世纪起就出现在函数式语言中了。 Haskell、CAML、Lisp 实现通常都至少将尾递归函数转换为迭代：基本上，您可以通过发现这是可能的来做到这一点，即可以重新排列函数，以便在递归调用后不使用除返回值之外的局部变量。 如果在返回之前对递归返回值进行了一些工作，则可以采用一个技巧，即引入一个附加的“累加器”参数。 简单来说，这意味着工作可以有效地以“向下”的方式完成，而不是“向上”的方式：搜索“如何使函数尾递归”以获取详细信息。

将尾递归函数转换为循环的实际细节基本上是调整您的调用约定，这样您只需设置参数并跳回函数的开头即可“执行调用”，而无需费心保存所有内容您知道自己永远不会使用的范围内的东西。 用汇编语言来说，如果数据流分析告诉您它们在调用之外未使用，则不必保留调用者保存寄存器，并且堆栈上的任何内容也是如此：您不必移动堆栈指针如果您不介意下一次递归/迭代会乱写“您的”堆栈位，则可以在调用时进行。

与您对 Python 人员的解释相反，将一般递归函数转换为迭代并不简单：例如，如果它是多重递归的，那么在简单的方法中您仍然需要一个堆栈。

不过，对于任意递归函数来说，记忆化是一种有用的技术，如果您对可能的方法感兴趣，您可能会想查找一下。 这意味着每次计算函数时，都会将结果保存在缓存中。 要使用它来优化递归，基本上，如果您的递归函数“向下”计数，并且您记住了它，那么您可以通过添加一个“向上”计数的循环来迭代地评估它，依次计算函数的每个值，直到达到目标。 如果备忘录缓存足够大以容纳您需要的所有值，则这使用很少的堆栈空间：例如，如果 f(n) 取决于 f(n-1)、f(n-2) 和 f(n -3）你只需要缓存中3个值的空间：当你上升时，你可以把梯子踢开。 如果 f(n) 取决于 f(n-1) 和 f(n/2)，则缓存中需要大量空间，但仍然小于未优化递归中用于堆栈的空间。

Answer 2

这更多的是一个实现问题，而不是一个语言问题。 没有什么可以阻止某些（愚钝的）C 编译器实现者将其调用堆栈限制为 1000。有很多小型处理器甚至没有足够的堆栈空间。

（Python 人员很快指出，您始终可以将递归函数转换为迭代函数，而且它们总是更快。这是 100% 正确的。但这并不是我的问题所在。）

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

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

Answer 3

PHP 在死亡之前的默认限制为 100：

致命错误：已达到最大函数嵌套级别“100”，正在中止！

编辑：您可以使用 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.

Answer 4

C#/.NET 将在特定情况下使用尾递归。 （C# 编译器不会发出 tailcall 操作码，但 递归。

JIT 在某些情况下会实现尾 >还有一篇关于此主题的文章 当然，CLR 正在不断变化，并且在 .NET 3.5 和 3.5SP1 中，它可能在尾部调用方面再次发生变化。

Answer 5

在 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# 编译器具有尾递归优化。 因此，这应该循环直到 i 达到 32 位整数的限制。

Answer 6

根据这个帖子，大约 5,000,000 使用 java， 1Gb 内存。 （并且，使用热点的“客户端”版本）

那是使用 堆栈 (-Xss)< /a> 300Mo。

使用 -server 选项，可以增加。

还可以尝试优化编译器（例如使用 JET）以减少堆栈开销每一层。

Answer 7

在一些非病态的情况下（比如你的），（最新的）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（恒定）来运行它，在几秒钟内完成。

Answer 8

Visual Dataflex 将发生堆栈溢出。

Answer 9

我非常喜欢函数式编程，并且由于大多数语言都实现了尾部调用优化，因此您可以随心所欲地递归 :-P

然而，实际上，我必须使用大量 Java，也大量使用 Python 。 不知道 Java 有什么限制，但对于 Python，我实际上计划（但尚未完成）实现一个装饰器，该装饰器将尾部调用优化装饰函数。
我计划这样做并不是为了优化递归，而是主要作为动态修补 Python 字节码和了解有关 Python 内部结构的更多信息的练习。
这里有一些值得关注的链接： http://lambda-the-ultimate.org/node/1331 和 http://www.rowehl.com/blog/?p=626

Answer 10

有一种方法可以改进 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];
}

Answer 11

clojure 为尾递归“recur”提供了一种特殊形式，它只能用在 ast 的尾部。 否则它的行为就像 java 一样，并且可能会抛出 StackverflowException。