MATLAB是否执行尾调用优化？

Question

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

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做任何TCO一致; 函数尾部调用自身的情况,只在一个地方,除了单个参数之外没有局部变量,就像任何人都希望的那样简单.

所以:不,看起来MATLAB根本不做TCO,至少在默认情况下是这样.我(到目前为止)还没有找到可能启用它的选项.如果有的话,我会感到惊讶.

如果我们没有炸掉堆栈,递归费用是多少？请参阅我对Bill Cheatham的回答的评论:看起来时间开销是非常重要但不是疯狂.

......除非Bill Cheatham在我发表评论后删除了答案.好.因此,我采用了Fibonacci函数的简单迭代实现和一个简单的尾递归函数,在两者中进行了基本相同的计算,并将它们计时fib(60).递归实现比迭代实现的运行时间长约2.5倍.当然,对于执行比一次加法更多工作的函数和每次迭代一次减法的函数,相对开销会更小.

(我也同意delnan的观点:在Haskell中感觉很自然的那种高递归代码在MATLAB中通常可能是单一的.)