尾递归

知乎优秀答案

尾递归，比线性递归多一个参数，这个参数是上一次调用函数得到的结果。

尾递归与普通递归的比较

普通递归

fac(3)

普通递归：
3 * fac(2)
3 * 2 * fac(1)
3 * 2 * 1 * fac(0)
3 * 2 * 1 * 1
3 * 2 * 1
3 * 2
6

// 普通递归实现的阶乘函数
function factorial1(n){
    if(n === 0){
        return 1;
    }
    return n * factorial1(n-1);
}

尾递归

fac(3)

尾递归
fac(3, 1)
fac(2, 3 * 1)
fac(1, 2 * 3 * 1)
fac(0, 1 * 2 * 3 * 1)
1 * 1 * 2 * 3 * 1
6

// 尾递归
function  factorial2(n, already=1){
    if(n === 0){
        return 1 * already;
    } else {  
        return factorial2(n-1, already * n);
    }
}

两种递归算法速度比较

function _main(){
    console.time('普通递归');
    console.log(factorial1(44));
    console.timeEnd('普通递归');
    console.time('尾递归');
    console.log(factorial2(44));
    console.timeEnd('尾递归');
}    

_main();

结果展示

寄语

希望每一个看到这篇博客的人 44 如意，身体健康！