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