JavaScript的遞歸遍歷會(huì)經(jīng)常遇到，適當(dāng)?shù)倪\(yùn)用遞歸遍歷假抄，可以提高代碼性質(zhì)量朵栖。
1.某些時(shí)候遞歸能替換for循環(huán)
我們先看一下下面2個(gè)例子。
var arrList = [1,2,3,5,100,500,10000,10000,1000,10000002]
//for循環(huán)測(cè)試
function forTest(){
console.time("for循環(huán)")
for(let i in arrList){
console.log(((arrList[i] + arrList[i]) * 5 - arrList[i])/arrList[i])
}
console.timeEnd("for循環(huán)")
}
//遞歸遍歷測(cè)試
function recursive() {
console.time("遞歸遍歷")
const testFun = function (i) {
console.log(((arrList[i] + arrList[i]) * 5 - arrList[i])/arrList[i])
if(i == arrList.length - 1){
return
}
i++
testFun(i)
}
testFun(0)
console.timeEnd("遞歸遍歷")
}
forTest()
recursive()
運(yùn)行結(jié)果：
可以看到剔宪，for循環(huán)去遍歷一個(gè)數(shù)組和用遞歸遍歷去遍歷同一個(gè)數(shù)組得到的結(jié)果一樣拂铡，耗時(shí)也幾乎相同。但是寫(xiě)法上有很大區(qū)別葱绒。
遞歸特點(diǎn)
每個(gè)遞歸都有一個(gè)結(jié)束遞歸的條件感帅，上例中的:if(i == arrList.length - 1){ return }。每一個(gè)遞歸都會(huì)在函數(shù)內(nèi)部把函數(shù)本身調(diào)用一次地淀，但是函數(shù)在每次運(yùn)行的時(shí)候失球，都會(huì)發(fā)生一些變化，用來(lái)觸發(fā)遞歸的結(jié)束帮毁，上例中实苞，testFun函數(shù)在內(nèi)部調(diào)用了自己，并且每次調(diào)用i的值會(huì)+1烈疚，最終觸發(fā)了結(jié)束條件黔牵，讓遞歸結(jié)束。
2.使用遞歸爷肝，可以輕松實(shí)現(xiàn)多級(jí)遍歷
我們先看下面的代碼：
var data = [
{
name: "所有物品",
children: [
{
name: "水果",
children: [{name: "蘋(píng)果", children: [{name: '青蘋(píng)果'}, {name: '紅蘋(píng)果'}]}]
},
{
name: '主食',
children: [
{name: "米飯", children: [{name: '北方米飯'}, {name: '南方米飯'}]}
]
},
{
name: '生活用品',
children: [
{name: "電腦類(lèi)", children: [{name: '聯(lián)想電腦'}, {name: '蘋(píng)果電腦'}]},
{name: "工具類(lèi)", children: [{name: "鋤頭"}, {name: "錘子"}]},
{name: "生活用品", children: [{name: "洗發(fā)水"}, {name: "沐浴露"}]}
]
}
]
}]
某些時(shí)候猾浦，坑逼后臺(tái)讓我們遍歷上面的一個(gè)數(shù)組，最后在頁(yè)面上顯示沒(méi)一級(jí)的最后一個(gè)數(shù)據(jù)阶剑。就是下面的數(shù)據(jù)：
青蘋(píng)果;紅蘋(píng)果;北方米飯;南方米飯;聯(lián)想電腦;蘋(píng)果電腦;鋤頭;錘子;洗發(fā)水;沐浴露;
我們先用遍歷的方式來(lái)實(shí)現(xiàn)：
//普通遍歷實(shí)現(xiàn)
var forFunction = function () {
var str = ""
data.forEach(function(row){
row.children.forEach(function(row){
row.children.forEach(function(row){
row.children.forEach(function(row){
str += (row.name + ";")
})
})
})
})
console.log(str)
}
forFunction()
//輸出：青蘋(píng)果;紅蘋(píng)果;北方米飯;南方米飯;聯(lián)想電腦;蘋(píng)果電腦;鋤頭;錘子;洗發(fā)水;沐浴露;
可以看到跃巡，前端累死累死寫(xiě)了4個(gè)forEach實(shí)現(xiàn)了產(chǎn)品要的效果，這時(shí)候如果再加點(diǎn)別的什么邏輯牧愁，就很難弄了素邪。這時(shí)候我們嘗試用遞歸的思想實(shí)現(xiàn)：
//遞歸遍歷實(shí)現(xiàn)
var recursiveFunction = function(){
var str = ''
const getStr = function(list){
list.forEach(function(row){
if(row.children){
getStr(row.children)
}else {
str += row.name + ";"
}
})
}
getStr(data)
console.log(str)
}
recursiveFunction()
//輸出：青蘋(píng)果;紅蘋(píng)果;北方米飯;南方米飯;聯(lián)想電腦;蘋(píng)果電腦;鋤頭;錘子;洗發(fā)水;沐浴露;
可以看到，遞歸的方式來(lái)實(shí)現(xiàn)的時(shí)候猪半，我們只需要一個(gè)for循環(huán)兔朦，每次遍歷接受到的數(shù)據(jù)，通過(guò)判斷是否還有children磨确，沒(méi)有就代表是最后一級(jí)了沽甥，有就繼續(xù)把children這個(gè)list傳給函數(shù)繼續(xù)遍歷，最后就得到了我們想要的數(shù)據(jù)乏奥。
很明顯摆舟，
forEach的遍歷的方式能實(shí)現(xiàn)多級(jí)的遍歷，并且數(shù)據(jù)格式可以靈活一些，但是遍歷的層級(jí)有限恨诱，而且對(duì)于未知層級(jí)的情況下媳瞪，就無(wú)從下手了。
遞歸遍歷照宝，理論上蛇受，只要內(nèi)存夠用，你能實(shí)現(xiàn)任意層級(jí)的遍歷厕鹃，但缺點(diǎn)也很明顯兢仰，沒(méi)一個(gè)層級(jí)里面需要有固定的數(shù)據(jù)格式，否則無(wú)法遍歷剂碴。
3.遞歸遍歷輕松實(shí)現(xiàn)多個(gè)異步結(jié)果的依次輸出
我們先看一下下面的需求把将，需要依次輸出1,2,3,4,5，每個(gè)輸出中間間隔1s汗茄。
我們先嘗試下面的方式：
//常規(guī)實(shí)現(xiàn)
var forTest = function () {
console.time("for時(shí)間")
for (let i = 0; i < 5; i++) {
setTimeout(function () {
console.log('for循環(huán)輸出：' + (i + 1))
if(i+ 1 === 5){
console.timeEnd("for時(shí)間")
}
}, 1000 * (i + 1))
}
}
forTest()
//每隔一秒輸出了1,2,3,4,5
上面我們用let當(dāng)前作用域的特點(diǎn)實(shí)現(xiàn)了每隔1s輸出秸弛，其實(shí)可以看出，是一起執(zhí)行的洪碳，但是由于間隔時(shí)間不一樣递览，導(dǎo)致結(jié)果是每隔一秒輸出的。
我們?cè)儆眠f歸的方式實(shí)現(xiàn)：
//遞歸遍歷實(shí)現(xiàn)
var recursiveTest = function(){
console.time("遞歸時(shí)間")
const test = function (i) {
setTimeout(function () {
i = i + 1
console.log('遞歸輸出：' + i)
if(i < 5){
test(i)
}else {
console.timeEnd("遞歸時(shí)間")
}
}, 1000)
}
test(0)
}
recursiveTest()
//每隔一秒輸出1,2,3,4,5
這里利用遞歸實(shí)現(xiàn)就很好理解了瞳腌，在setTimeout里面輸出了之后绞铃，再開(kāi)始下一個(gè)1s的輸出。
最后我們看一下運(yùn)行截圖：
通過(guò)截圖上的耗時(shí)來(lái)看：遞歸遍歷需要的時(shí)間更長(zhǎng)嫂侍，但是更好理解一下儿捧，而且不依賴es6的環(huán)境。
4.遞歸遍歷實(shí)現(xiàn)排序
var quickSort = function(arr) {
if (arr.length <= 1) {//如果數(shù)組長(zhǎng)度小于等于1無(wú)需判斷直接返回即可
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);//取基準(zhǔn)點(diǎn)
var pivot = arr.splice(pivotIndex, 1)[0];//取基準(zhǔn)點(diǎn)的值,splice(index,1)函數(shù)可以返回?cái)?shù)組中被刪除的那個(gè)數(shù)
var left = [];//存放比基準(zhǔn)點(diǎn)小的數(shù)組
var right = [];//存放比基準(zhǔn)點(diǎn)大的數(shù)組
for (var i = 0; i < arr.length; i++){ //遍歷數(shù)組挑宠，進(jìn)行判斷分配
if (arr[i] < pivot) {
left.push(arr[i]);//比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組
} else {
right.push(arr[i]);//比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組
}
}
//遞歸執(zhí)行以上操作,對(duì)左右兩個(gè)數(shù)組進(jìn)行操作菲盾，直到數(shù)組長(zhǎng)度為<=1；
return quickSort(left).concat([pivot], quickSort(right));
};
var arr = [14, 50, 80, 7, 2, 2, 11];
console.log(quickSort(arr));
這是利用遞歸實(shí)現(xiàn)的快速排序各淀，效率很高懒鉴，有興趣的同學(xué)可以試試普通的遍歷實(shí)現(xiàn)，再進(jìn)行比較碎浇。
5.總結(jié)
1.很多時(shí)候可以用遞歸代替循環(huán)临谱，可以理解為遞歸是一種特殊的循環(huán)，但通常情況下不推薦這樣做奴璃。
2.遞歸一般是在函數(shù)里面把函數(shù)自己給調(diào)用一遍悉默，通過(guò)每次調(diào)用改變條件，來(lái)結(jié)束循環(huán)苟穆。
3.遞歸在數(shù)據(jù)格式一致抄课，在數(shù)據(jù)層級(jí)未知的情況下唱星，比普通的遍歷更有優(yōu)勢(shì)。
4.遞歸在異步的時(shí)候剖膳，更容易理解魏颓，且更容易實(shí)現(xiàn)，因?yàn)榭梢栽诋惒降幕卣{(diào)里面吱晒，調(diào)用自己來(lái)實(shí)現(xiàn)每次都能拿到異步的結(jié)果再進(jìn)行其他操作。
5.遞歸實(shí)現(xiàn)的快速排序比普通遍歷實(shí)現(xiàn)的排序效率更好沦童。
