MATLAB是否执行尾部调用优化？

[poster]

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



回答：

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

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根本不执行TCO。到目前为止，我还没有寻找可能启用它的选项。如果有的话我会感到惊讶。

在我们不花钱的情况下，递归要花多少钱？请看我对Bill Cheatham的回答的评论：看起来时间开销是不平凡的，但并非疯狂。

...除了我发表评论后，比尔·希瑟姆（Bill Cheatham）删除了他的答案。好。因此，我采用了Fibonacci函数的简单迭代实现和简单的尾递归函数，在这两个函数中进行了基本上相同的计算，并将它们都定时在fib(60) 。递归实现的运行时间比迭代实现的时间长约2.5倍。当然，对于执行更多工作而不是每次迭代进行一次加法和一次减法的函数，相对开销将较小。

（我也同意delnan的观点：在Haskell中感觉很自然的那种高度递归的代码在MATLAB中通常很容易理解。）



更多&回答...