language-agnostic - 你最喜欢的语言如何处理深度递归？

Question

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

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

我在 Perl 中尝试了相同的实验，大约 1000 万次递归消耗了我所有的 4 gig 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）是如何处理递归的，以及为什么它们以这种方式处理递归。此外，请注意如果函数是“尾递归”（见评论），它是否会有所不同。

score 23 · Accepted Answer

“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)，

score 7 · Accepted Answer

这更像是一个实现问题而不是语言问题。没有什么能阻止一些（愚蠢的）C 编译器实现者也将他们的调用堆栈限制为 1000。那里有很多小型处理器，即使有那么多也没有堆栈空间。

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

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

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

score 4 · Accepted Answer

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.

score 3 · Accepted Answer

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

Shri Borde也有关于这个主题的帖子。当然，CLR 不断变化，在 .NET 3.5 和 3.5SP1 中，它可能在尾调用方面再次发生变化。

score 3 · Accepted Answer

在 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 位整数的限制。

score 2 · Accepted Answer

根据这个线程，大约 5,000,000使用 java，1Gb RAM。（而且，使用热点的“客户端”版本）

那是300Mo的堆栈（-Xss）。

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

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

score 2 · Accepted Answer

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

score 1 · Accepted Answer

1

Visual Dataflex 将堆栈溢出。

于 2008-10-24T10:46:52.367 回答

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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

language-agnostic - 你最喜欢的语言如何处理深度递归？

11 回答 11

Related

Reference