什么是递归函数?
一个通过函数名调用自身的函数
递归函数的注意点
- 一定要有结束条件，否则会导致死循环
- 能用递归函数实现的需求，就一定可以用循环调用函数来解决，只是代码简洁与性能不同而已
递归函数的应用场景
1.求阶乘: 求n的阶乘
- 循环写法
function getMul(n){
var data = 1;
for(var i = 1;i<=n;i++){
data *= i
}
return data;
}
console.log(getMul(4));//24
-
递归写法
a.推理版:中间省略
function getMul(n){
if(n == 1){
return 1;
}else if(n == 2){
return 2 * getMul(1);
}else if(n == 3){
return 3 * getMul(2)
}
//*****
else if(n == n){
return n * getMul(n-1);
};
};
console.log(getMul(4));//24
b.精简版:三元表达式
function getMul(n){
return n == 1 ? 1 : n * getMul(n-1);
};
console.log(getMul(4));//24
2.求1-n的累加和
- 循环写法
function getSum(n){
var data = 0;
for(var i = 1;i<=n;i++){
data += i;
}
return data;
};
console.log(getSum(4));//10
-
递归写法
a.推理版:中间省略
function getSum(n){
if(n == 1){
return 1;
}else if(n == 2){
return n + getSum(1);
}else if(n == 3){
return n + getSum(2);
}else if(n == 4){
return n + getSum(3);
}
// ………………
else if(n == n){
return n + getSum(n-1)
}
};
console.log(getSum(4));//10
b.精简版:三元表达式
function getSum(n){
return n==1 ? 1:n + getSum(n-1);
};
console.log(getSum(4));//10
3.求斐波拉契数列
- 斐波拉契数列: 前面两个数字是固定的1,从第三个数字开始，每一个数字都是前面两个数字的和
循环数组写法(性能好)
思路:1.每次计算都是前两个数字之和,其他的数据没有什么用,所以每次只计算两个
arr[n]=arr[n-1]+arr[n-2]
灵魂画手
function getData(n) {
var arr = [1, 1];
for (var i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
};
console.log(arr);//[1,1,2,3,5,8,13,21,34,55]
return arr[arr.length - 1];
};
console.log(getData(10)); //10
递归写法
a.推理版:中间省略
function getData(n) {
if(n == 1 || n == 2){
return 1;
}else if(n == 3){
return getData(2) + getData(1);
}else if(n == 4){
return getData(3)+getData(2);
}else if(n == 5){
return getData(4) + getData(3)
}
// …………
else if(n == n){
return getData(n-1) + getData(n-2)
};
};
console.log(getData(10)); //10
b.精简版:三元表达式
function getData(n) {
return (n == 1 || n == 2)?1 : getData(n-1) + getData(n-2);
};
console.log(getData(10)); //10
4.遍历DOM树:获取所有的后代元素
a.需求:获得div中所有的后代元素
b.思路:获取father的子代元素。 继续检查该元素是否有子代元素，
如果有则继续循环获取子代，依次类推，形成递归调用
<div id="father">
<div>
<span>1</span>>
</div>
<p>
<span>11</span>
<span>22</span>
</p>
<a href="#">boJack</a>
<div>
<div>
<b>Todd</b>
</div>
</div>
</div>
<script>
var father = document.getElementById('father');
var list = []; //声明空数组存储所有的后代元素
function getHouDai(ele) {
for (var i = 0; i < ele.children.length; i++) {
list.push(ele.children[i]);
getHouDai(ele.children[i]);
};
};
getHouDai(father);
console.log(list);//[span,p,span,span,a,div,div,b]
// 遍历整颗DOM树
getHouDai(document);
console.log(list);
</script>
经典面试题以及推荐用法
a.写出该题打印的值
var res = (function(n){ return n==1?1:n*arguments.callee(n-1)})(6);
console.log('res' + res);//res720
考察的知识点:argument.callee
- argument.callee是一个指向正在执行的函数的指针,使用它来代替函数名,可以确保无论怎样调用函数都不会出问题
function res(n) {
return n ==1 ? 1 : n * res(n - 1);
};
var data = res;
res = null;
console.log(data(4));
//res is not a function
由于res变量设置为Null,结果指向原始函数的引用只剩下一个,res已经不是函数,而调用data()会执行res,所以会报错;而使用arguments.callee可以解决这个问题
function res(n) {
return n ==1 ? 1 : n * arguments.callee(n - 1);
};
var data = res;
res = null;
console.log(data(4));//24
推荐用法
-
严格模式:使用arguments.callee会报错,不过我们可以通过命名函数表达式来达到相同的效果
以下代码创建了一个f()的命名函数表达式,赋值给res变量,即使把函数赋值给另一个变量,函数的名字依然有效,递归能正常完成,这种方式在严格模式和非严格模式都能运行
var res=(function f(n) {
return n ==1 ? 1 : n * f(n - 1);
});
console.log(res(4));//24
