理解尾调用优化

Posted on | In , | |

上篇讲了递归的理解，里面涉及到了对尾递归优化的阐述，不过不够详尽。这篇将详细阐述从尾调用到尾递归。

尾调用（Tail Call）

概念：某个函数的最后一步是调用另一个函数。 

function f(x){
    return g(x) 123
}

上面函数的最后一步是调用函数g，此即尾调用。
若调用之后还有其他操作，则不属于尾调用。譬如： 

//condition 1
fucntion f(x){
    let y = g(x);
    return y;
    }    
//condition 2
function f(x){
    return g(x) + 1;
}

尾调用不一定出现在函数尾部，只要是最后一步即可。如下面代码中函数m、n都是尾调用。 

function f(x){
if (x > 0){
    return m(x)
}
return n(x)}

尾调用优化

调用栈：函数调用会在内存形成一个“调用记录（调用帧／call frame）”，用以保存调用位置和内部变量等信息。在函数A内部调用函数B，则会在A的调用记录上方形成一个B的调用记录。等到B运行结束， 将结果返回A，B的调用记录才会消失。若函数B内部还调用C，则还有一个C的调用记录栈，依此类推。所有的调用记录形成一个调用栈（call stack）。

调用栈

上图表示一个调用栈及递归调用的过程。矩形块表示一个个调用帧／调用记录／call frame，箭头表示状态，从左至右是流程。

尾调用优化：只保留内层函数的调用记录（实际上是以内层函数直接取代外层函数的调用记录）。尾调用可大大节省内存，因为调用记录只有一项。 

function f(){
    let m = 1;
    let n =2;
    return g(m + n);
}
f();

//is equal to 
function f(){
    return g(3)
}

//is equal to 
g(3)

如上例，若函数不是尾调用，f函数就需保存m和n的值以及g的调用位置等信息。但由于调用了g后，函数f就结束了，故最后完全可删除法f()的记录，只保留g(3)的调用信息。

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

为什么用尾递归：递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生”栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。 

//递归求阶乘的算法，最多需要保存n个调用记录，复杂度O(n)
function fact(n){
    if (n == 1) return 1;
    return n * fact(n -1);
}
fact(5) 

//改成尾递归,只保留一个调用记录，复杂度O(1)            

function fact(n, total){
    if (n == 1) return total;
    return fact(n -1, n * total)
}
fact(5, 1)

递归函数的改写

柯里化（currying）：将多参数的函数转化为单参数形式。 

//由于参数total有默认值1，故调用时不用提供此值。
function fact(n, total = 1){
    if (n == 1) return total;
    return fact(n - 1, n * total)
}
fact(5)

递归本质是循环操作，所有的循环都用递归实现。一旦使用递归，最好使用尾递归。

趣味例子

摘自某乎上的一个形象解释尾递归与递归的区别的例子： 

function story() {    从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story() // 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。}   

function story() {    从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story()，小和尚听了，找了块豆腐撞死了 // 非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。}
Thanks!