1 . 什么是递归:
如果一个函数在内部可以调用其本身,那么这个函数就是递归函数。
简单理解:函数内部自己调用自己, 这个函数就是递归函数
比如:
<script>
function fy(n){
fy();
}
console.log(fy()); // 报错
</script>
但上面代码报错因为递归很容易发生“栈溢出”错误(stack ),所以必须要加退出条件 return。
递归必须由以下两部分组成。
<script>
function fy(n) {
if (n == 1) {
return 1
} else {
return n + fy(n - 1)
}
}
console.log(fy(5));
</script>
执行循序:
f (5) = {5+ f(4)}
= {5 {4 + f(3) }}
= {5 + {4 + {3 + f(2)}}}
= {5 + {4 + {3 + {2 + f(1)}}}}
= {5 + {4 + {3 + {2 +1}}}}
= 15
很容易看出,普通递归很消耗资
利用递归解决问题:
-
主要解决一些数学运算,如阶乘函数、幂函数和斐波那契数列。
利用递归解决斐波那契数列第N项的值
function fy(n){
if (n<0) {
return 'N的值不能小于0'
}else if(n==0||n==1){
return 1;
}
else if (n >1){
return fy(n-1)+fy(n-2)
}
}
console.log(fy(5));
利用递归遍历数据拿对象里面的值:
var data = [{
id: 1,
name: '家电',
goods: [{
id: 11,
gname: '冰箱',
goods: [{
id: 111,
gname: '海尔'
}, {
id: 112,
gname: '美的'
}, ]
}, {
id: 12,
gname: '洗衣机'
}]
}, {
id: 2,
name: '服饰'
}];
function getID(json, id) {
var num= {};
json.forEach(function(item) { // 利用 forEach 去遍历里面的每一个对象
if (item.id == id) {
num = item;
// 拿到里层的数据 11 12 可以利用递归函数
// 里面应该有goods这个数组并且数组的长度不为 0
} else if (item.goods && item.goods.length > 0) {
num = getID(item.goods, id);
}
});
return num;
}
console.log(getID(data, 1));
console.log(getID(data, 11));
console.log(getID(data, 111));
上面的案列中可以看出 普通递归都是很消耗资源的
但可以利用尾递归就不存在这样的问题,因为它的状态完全由变量 n 和 a 保存。
<script>
var n = 5;
var a= 0;
for (var i = 1; i <= 5; i ++) {
a = a + i;
}
console.log(a);
</script>
迭代方式实现递归