MATLAB是否执行尾递归优化？

Question

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

- Shea Levy

---

避免只是因为一时兴起而进行循环迭代不是一个好主意。针对给定的问题使用更合适并且可行的方法（当然，对于纯粹的函数式语言来说，迭代并不实用）。 - user395760

通过适当的尾调用优化，"避免迭代"变成了你思考问题的方式，而不是你的解决方案的性能。如果MATLAB没有提供TCO，那么显然我需要使用迭代，但如果它提供了，我将能够在所有代码中使用一致的范例。 - Shea Levy

我不特别了解MATLAB，我是泛指地说。如果你在编写Python，并且Python具有TCO，你仍然不应该使用递归而非循环，因为这不是惯用方式，该语言和标准库专注于充分利用迭代器等。关于“一致的范式”：每种范式都有其弱点，因此使用最适合解决给定问题的任何方法（当然，“最佳”的定义也涉及与其余部分的良好协作程度）。 - user395760

Y-Combinator在MATLAB中的实现：http://mathforum.org/kb/message.jspa?messageID=6636833&tstart=0 - Mikhail Poda

Answer 1

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

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 进行任何尾调用优化是不一致的；当一个函数仅在一个地方进行自我尾调用时，没有除一个参数外的局部变量，这种情况就足够简单了。

所以：不，似乎 MATLAB 默认情况下根本不会进行尾调用优化。我还没有寻找可能启用它的选项。如果有的话，我会感到惊讶。

在我们不会爆栈的情况下，递归成本如何？请参见我对 Bill Cheatham 的回答：看起来时间开销是相当大的，但不是疯狂的。

... 但是 Bill Cheatham 在我留下评论后删除了他的回答。好吧。因此，我对斐波那契函数进行了简单的迭代实现和简单的尾递归实现，在两者中都执行基本相同的计算，并在 fib(60) 上对它们进行了计时。递归实现的运行时间约为迭代实现的 2.5 倍。当然，对于执行比每次迭代一个加法和一个减法更多工作的函数，相对开销将更小。

（我也同意 delnan 的观点：在 Haskell 中感觉自然的高度递归代码通常不太符合 MATLAB 的惯用法。）

- Gareth McCaughan

---

在Matlab中，TCO可能会很困难，因为从堆栈帧的工作区中清除本地变量可能会对onCleanup()功能产生副作用。Matlab不像GCed Java一样具有垃圾回收机制；它是确定性的，使用引用计数或类似方法。支持RAII。要确定堆栈帧省略是否安全，需要深入搜索所有未在尾调用中传递的本地变量，以查看它们是否包含任何onCleanup。这是一个昂贵的测试。此外，至少需要保留一个父堆栈帧，以防调用assignin(...,'caller')或evalin(...,'caller')。同意，不符合惯例。 - Andrew Janke

Answer 2

有一种简单的方法来检查这个。创建这个函数 tail_recursion_check：

function r = tail_recursion_check(n)
    if n > 1
        r = tail_recursion_check(n - 1);
    else
        error('error');
    end
end

运行tail_recursion_check(10)，例如。你会看到一个非常长的堆栈跟踪，其中有10个项目，显示错误在第3行。如果有尾调用优化，你只会看到一个。

- Zhe