理解尾调用优化

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

尾调用(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(),小和尚听了,找了块豆腐撞死了 // 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境以供处理返回值。}
拿钱去买猫粮和狗粮嗷 ~