14

我最近学习了 Haskell，并尽可能将纯函数式风格带到我的其他代码中。这方面的一个重要方面是将所有变量视为不可变的，即常量。为了做到这一点，许多将使用命令式循环实现的计算必须使用递归来执行，这通常会由于为每个函数调用分配新的堆栈帧而导致内存损失。然而，在尾调用的特殊情况下（被调用函数的返回值立即返回给被调用者的调用者），这种惩罚可以被称为尾调用优化的过程绕过（在一种方法中，这可以通过基本上在正确设置堆栈后用 jmp 替换调用）。MATLAB 是否默认执行 TCO，或者有没有办法告诉它？

4

1 回答 1

11

如果我定义一个简单的尾递归函数：

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

并调用它，以便它会非常深入地递归：

set(0,'RecursionLimit',10000);
tailtest(1000);

那么看起来堆栈帧并没有占用大量内存。但是，如果我让它递归得更深：

set(0,'RecursionLimit',10000);
tailtest(5000);

然后（今天在我的机器上）MATLAB 简单地崩溃了：进程毫不客气地死了。

我不认为这与 MATLAB 做任何 TCO 是一致的。函数尾部调用自身的情况，只在一个地方，除了一个参数之外没有局部变量，这几乎是任何人都希望的那样简单。

所以：不，MATLAB 似乎根本不做 TCO，至少在默认情况下是这样。我（到目前为止）还没有寻找可能启用它的选项。如果有的话，我会感到惊讶。

在我们不爆栈的情况下，递归的成本是多少？请参阅我对 Bill Cheatham 的回答的评论：看起来时间开销并非微不足道，但并非疯狂。

...除了比尔·奇塔姆（Bill Cheatham）在我发表评论后删除了他的答案。好的。因此，我采用了斐波那契函数的简单迭代实现和简单的尾递归函数，在两者中进行基本相同的计算，并将它们都计时fib(60)。递归实现的运行时间大约是迭代实现的 2.5 倍。当然，对于比每次迭代一次加法和一次减法做更多工作的函数，相对开销会更小。

（我也同意 delnan 的观点：在 Haskell 中感觉很自然的那种高度递归的代码在 MATLAB 中通常可能是单调的。）

于 2011-03-16T16:25:34.060 回答