尾调用及其消除

问题来源:《Lua程序设计》第四版 第六章 第四节

尾调用 tail call

概念:一个函数里的最后一个动作是一个函数调用的情形

Lua例:

function func1(x) do return func2(x) end

也就是说,是这个调用的返回值直接被当前函数返回的情形。

为什么这种情况要单独拿出来定义,首先要明确函数 调用栈 的概念。

调用栈

在程序的内存空间中,有一块专门的区域被用来记录正在调用的函数的情况,这块区域就是函数调用栈。
每次调用一个新的函数时,就会在调用栈顶进行一个压栈操作;函数执行完毕时,会执行弹栈操作,清除被调用函数的资源。

尾递归

尾调用的函数是当前函数自身,这种情况被成为尾递归。

如果在函数内调用函数的话,就会导致不断压栈而没有弹栈的情况,其结果是消耗大量内存并且有撑爆函数调用栈空间的风险,尤其是递归的情况下。
但尾调用有所不同,普通函数内调用函数,因为后续还有要执行的语句,所以无法优化。而尾调用由于是函数的最后一条语句,优化是可以实现的,尤其是尾递归的情况下,优化可以提高不少效率。

尾调用消除 Tail Call Elimination

主要目的:使程序员可以使用递归代替循环且不损失性能。

调用栈执行机制:调用栈在将一个函数压栈时,会记住他的返回位置,当一个函数调用结束时,他的返回值会被放到栈中所记录的返回位置上。举例来说,函数a在第三条语句时调用函数b,那么函数b被压栈,它的返回位置就是函数a调用它的地方,当函数b运行结束,它的返回值就会被放到a调用函数b的位置,之后再执行下面的语句。

消除实现:对于尾调用而言,被调函数的位置可以不用记录在调用栈中。用上述例子类比,如果a在return语句调用函数b,那么b的调用和返回位置就是a的返回位置。所以尾调用消除就是在不改变当前调用栈的调用情况下,直接跳转进入另一个函数的调用,并且该函数的返回位置就是调用该函数函数的返回位置。这样一来,就省下了一次压栈和一次弹栈的消耗。