SOURCE

/**
 * 总结:尾递归性能比普通递归强(前提是编译器或者解释器对其有做了优化)
 * 以下说法基于上述前提下
 * 
 * 普通递归是在“归”的过程中处理逻辑,因此需要将上一个调用函数的上下文做存储,形成调用栈,递归的层级深了,容易造成栈溢出
 * 尾递归则是在“递”的过程中处理逻辑,上下文的数据就不重要了,因此经编译器或者解释器优化后,其空间效率上与迭代一样
 * 
 * 类比:下楼捡金币
 * 普通递归是在下楼的时候空手,只看不捡,但是会有精神消耗,
 * 心想:哇这么多,我待会要捡完了要买什么什么...,走的一楼的时候,脑子里已经把这些金币用在什么地方都想了个遍,上楼的时候再捡金币
 * 尾递归是在下楼的时候就捡金币,边捡边想,捡到最后一层,心里已经想好了金币的用处,直接抱着金币上楼,开开心心回家,不必在做什么了
 */

/*** 案例1:给定一个斐波那契数列0,1,1,2,3,5,8,13,... ,求该数列的第n个数字 ***/

/**
 * 普通递归
 * n: 第n个数字
 */
function fib(n){
    //终止条件 f(1) = 0 f(2) = 1
    if(n == 1 || n == 2) {
        return n - 1
    }
    //递归调用 f(n) = f(n-1) + f(n-2)
    return fib(n - 1) + fib(n - 2)
}

/**
 * 尾递归
 * n: 第n个数字
 * res1: 存放f(n-2)
 * res2: 存放f(n-1)
 */
function tailFib(n, res1 = 0, res2 = 1) {
    //尾递归的特点,在递的过程中处理逻辑
    if(n === 1) return res1
    if(n === 2) return res2

    return tailFib(n - 1, res2, res1 + res2)
}

console.log("斐波那契-普通递归:", fib(5))
console.log("斐波那契-尾递归:", tailFib(80))

/*** 案例2:细胞分裂,初始状态为1个细胞,1分2,2分4,4分8,n分2的n方,求第n次分裂后的总分裂次数 ***/
//f(1)=1, f(2)=f(1)+2的1方, f(3)=f(1)+f(2)+2的2方..., f(n)=2的n方-1
// n=1:初始状态(1个细胞,尚未分裂)
// n=2:完成第1次分裂后的状态
// n=3:完成第2次分裂后的状态
//关键点是:每次都是复制出新个体,但是原个体保留

/**
 * 循环
 * n: 表示分裂轮数
 */
function loopCellSplit(n) {
    let count = 0,base = 1
    for(let i = 0; i < n; i++){
        for(let j = 0; j < base; j++){
            count++
        }
        base *= 2
    }
    return count
}

/**
 * 普通递归
 * n: 表示分裂轮数
 */
function cellSplit(n) {
    //终止条件 f(1) = 1
    if(n == 1) return 1
    //cellSplit(n - 1)为前一次分裂的总数
    //2 * cellSplit(n - 1)为每次分裂都产生2倍的数量
    //+ 1是加的初始状态下的那个细胞
    return 2 * cellSplit(n - 1) + 1
}

/**
 * 尾递归
 * n: 表示分裂轮数
 * res: 表示分裂后的总数
 */
function tailCellSplit(n, res = 1) {
    if(n == 1) return res
    return tailCellSplit(n - 1, 2 * res + 1)
}

console.log("细胞分裂-循环:", loopCellSplit(10))
console.log("细胞分裂-普通递归:", cellSplit(5))
console.log("细胞分裂-尾递归:", tailCellSplit(10))
console 命令行工具 X clear

                    
>
console