什么是遞歸函數(shù)?
一個(gè)通過函數(shù)名調(diào)用自身的函數(shù)
遞歸函數(shù)的注意點(diǎn)
- 一定要有結(jié)束條件，否則會(huì)導(dǎo)致死循環(huán)
- 能用遞歸函數(shù)實(shí)現(xiàn)的需求，就一定可以用循環(huán)調(diào)用函數(shù)來解決，只是代碼簡潔與性能不同而已
遞歸函數(shù)的應(yīng)用場景
1.求階乘: 求n的階乘
- 循環(huá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.精簡版:三元表達(dá)式
function getMul(n){
return n == 1 ? 1 : n * getMul(n-1);
};
console.log(getMul(4));//24
2.求1-n的累加和
- 循環(huá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.精簡版:三元表達(dá)式
function getSum(n){
return n==1 ? 1:n + getSum(n-1);
};
console.log(getSum(4));//10
3.求斐波拉契數(shù)列
- 斐波拉契數(shù)列: 前面兩個(gè)數(shù)字是固定的1,從第三個(gè)數(shù)字開始，每一個(gè)數(shù)字都是前面兩個(gè)數(shù)字的和
循環(huán)數(shù)組寫法(性能好)
思路:1.每次計(jì)算都是前兩個(gè)數(shù)字之和,其他的數(shù)據(jù)沒有什么用,所以每次只計(jì)算兩個(gè)
arr[n]=arr[n-1]+arr[n-2]
image
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.精簡版:三元表達(dá)式
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的子代元素凫佛。 繼續(xù)檢查該元素是否有子代元素，
如果有則繼續(xù)循環(huán)獲取子代孕惜，依次類推愧薛，形成遞歸調(diào)用
<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 = []; //聲明空數(shù)組存儲(chǔ)所有的后代元素
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>
經(jīng)典面試題以及推薦用法
a.寫出該題打印的值
var res = (function(n){ return n==1?1:n*arguments.callee(n-1)})(6);
console.log('res' + res);//res720
考察的知識(shí)點(diǎn):argument.callee
- argument.callee是一個(gè)指向正在執(zhí)行的函數(shù)的指針,使用它來代替函數(shù)名,可以確保無論怎樣調(diào)用函數(shù)都不會(huì)出問題
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變量設(shè)置為Null,結(jié)果指向原始函數(shù)的引用只剩下一個(gè),res已經(jīng)不是函數(shù),而調(diào)用data()會(huì)執(zhí)行res,所以會(huì)報(bào)錯(cuò);而使用arguments.callee可以解決這個(gè)問題
function res(n) {
return n ==1 ? 1 : n * arguments.callee(n - 1);
};
var data = res;
res = null;
console.log(data(4));//24
推薦用法
-
嚴(yán)格模式:使用arguments.callee會(huì)報(bào)錯(cuò),不過我們可以通過命名函數(shù)表達(dá)式來達(dá)到相同的效果
以下代碼創(chuàng)建了一個(gè)f()的命名函數(shù)表達(dá)式,賦值給res變量,即使把函數(shù)賦值給另一個(gè)變量,函數(shù)的名字依然有效,遞歸能正常完成,這種方式在嚴(yán)格模式和非嚴(yán)格模式都能運(yùn)行
var res=(function f(n) {
return n ==1 ? 1 : n * f(n - 1);
});
console.log(res(4));//24
