我最近学习了Haskell,并在可能的情况下尝试将纯函数风格应用到其他代码中。这样做的一个重要方面是将所有变量都视为不可变的,即常量。为此,许多使用命令式循环实现的计算必须使用递归执行,这通常会由于为每个函数调用分配一个新的堆栈框架而导致内存损失。然而,在尾部调用的特殊情况下(被调用函数的返回值立即返回到被调用者的调用方),称为尾部调用优化的过程可以绕过这种损失(在一种方法中,这可以通过在正确设置堆栈之后基本上用JMP替换调用来实现)。MatLab是否默认执行TCO,或者有什么方法可以告诉它这样做?
2条答案
按热度按时间ki0zmccv1#
如果我定义一个简单的尾递归函数:
把它叫来,这样它就会非常深入地循环:
这样看起来堆栈帧就不会占用太多内存。然而,如果我让它递归得更深:
然后(在我的机器上,今天),matlab简单地崩溃了:这个进程随意地死了。
我不认为这与MatLab做任何TCO是一致的;函数只在一个地方尾部调用自身,除了一个参数之外没有其他局部变量的情况,就像任何人所希望的那样简单。
所以:不,至少在默认情况下,MatLab似乎根本不做TCO。我(到目前为止)还没有寻找可能实现这一点的选择。如果有的话,我会很惊讶的。
在我们不清除堆栈的情况下,递归的成本是多少?请看我对Bill Cheatham回答的评论:看起来时间开销不是微不足道的,但并不疯狂。
..。除了比尔·切瑟姆在我留下那条评论后删除了他的回答。好的。因此,我采用了Fibonacci函数和简单的尾递归函数的简单迭代实现,在两者中进行了基本上相同的计算,并在
fib(60)
上对它们进行了计时。递归实现的运行时间大约是迭代实现的2.5倍。当然,对于每次迭代执行的工作多于一次加法和一次减法的函数,相对开销会更小。(我也同意Delnan的观点:在Haskell中感觉很自然的那种高度递归代码在matlab中通常很可能是单一化的。)
falq053o2#
有一种简单的方法可以检查这一点。创建此函数
tail_recursion_check
:例如,运行
tail_recursion_check(10)
。您将看到一个非常长的堆栈跟踪,其中有10个项在第3行显示错误。如果有尾部调用优化,您将只会看到一个。