问题来源:《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的返回位置。所以尾调用消除就是在不改变当前调用栈的调用情况下,直接跳转进入另一个函数的调用,并且该函数的返回位置就是调用该函数函数的返回位置。这样一来,就省下了一次压栈和一次弹栈的消耗。