一個函數(shù)在內(nèi)部調(diào)用自己就叫遞歸横堡，遞歸必須加退出條件
//遞歸實現(xiàn)階乘
function fn(n){
if(n == 1){
return 1
}
return n * fn(n-1)
}
console.log(fn(7));
//斐波那契數(shù)列，1黔姜、1粗悯、2、3如捅、5棍现、8、13镜遣、21己肮、34，第三項開始等于前兩項之和
function fb(n){
if(n <= 2){
return 1
}
return fb(n-1) + fb(n-2)
}
console.log(fb(8));
//利用遞歸獲取數(shù)據(jù)
var data = [{
id: 1,
name: '家電',
goods: [{
id: 11,
gname: '冰箱',
goods: [{
id: 111,
gname: '海爾'
}, {
id: 112,
gname: '美的'
}, ]
}, {
id: 12,
gname: '洗衣機'
}]
}, {
id: 2,
name: '服飾'
}];
function getGoods(array,id){
var o = {}
array.forEach(item => {
if(item.id == id){
o = item
}else if(item.goods && item.goods.length > 0){
o = getGoods(item.goods, id);
}
});
return o
}
console.log(getGoods(data,1));
console.log(getGoods(data,11));
console.log(getGoods(data,111));
可以使用arguments.callee代替函數(shù)名
//遞歸實現(xiàn)階乘
function fn(n){
if(n <= 2){
return n
}
return n * arguments.callee(n-1)
}
console.log(fn(7));
寫遞歸分三步：
1悲关、先去確定功能：
實現(xiàn)階乘
2谎僻、找出結(jié)束條件，結(jié)束條件一般在很小的數(shù)去找
if(n <= 2){
return n
}
3寓辱、找出函數(shù)的等價關(guān)系式：
f(n) = n * fn(n-1)
例子：
一只青蛙一次可以跳上1級臺階艘绍，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法秫筏。
1诱鞠、確立功能：
跳上一個n級的臺階總共有多少種跳法
2挎挖、找出結(jié)束條件，往小了找
1級：(1)
2級：(1,1) (2)
3級：(1,1,1) (1,2) (2,1)
4級：(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)
第四級開始不一樣了航夺，前面三級都是返回n種肋乍，第四級5種
所以結(jié)束條件為：
if(n <= 3){
return n
}
3、找出函數(shù)的等價關(guān)系式：
第一次跳1級敷存，所以接下來還有n-1級階梯墓造，n-1級階梯有f(n-1)種跳法
第一次跳2級，所以接下來還有n-2級階梯锚烦，n-2級階梯有f(n-2)種跳法
所以
f(n) = f(n-1) + f(n-2)
function fn(n){
if(n <= 3){
return n
}
return fn(n-1) + fn(n-2)
}
優(yōu)化：
function fn(n){
var arr=[]
if(n <= 3){
return n;
}
//先判斷有沒計算過
if(arr[n]!=null){
//計算過觅闽，直接返回
return arr[n];
}else{
// 沒有計算過，遞歸計算,并且把結(jié)果保存到 arr數(shù)組里
arr[n] = fn(n-1) + fn(n-2)
return arr[n];
}
}
