原文地址
1. 遞歸是啥?
遞歸概念很簡單，“自己調用自己”（下面以函數為例）。
在分析遞歸之前，需要了解下 JavaScript 中“壓棧”（call stack） 概念。
2. 壓棧與出棧
棧是什么？可以理解是在內存中某一塊區域，這個區域比喻成一個箱子，你往箱子里放些東西，這動作就是壓棧。所以最先放下去的東西在箱子最底下，最后放下去的在箱子最上面。把東西從箱子中拿出來可以理解為出棧。
所以得出結論，我們有個習慣，拿東西是從上面往下拿，最先放下去的東西在箱子的最底下，最后才能拿到。
在 JavaScript 中，調用函數時，都會發生壓棧行為，遇到含 return 關鍵字的句子或執行結束后，才會發生出棧（pop）。
來看個例子，這個段代碼執行順序是怎樣的？
function fn1() {return 'this is fn1'
}function fn2() {fn3()return 'this is fn2'
}function fn3() {let arr = ['apple', 'banana', 'orange']return arr.length
}function fn() {fn1()fn2()console.log('All fn are done')
}fn()
復制代碼上面發生了一系列壓棧出棧的行為：
- 首先，一開始棧（箱子）是空的
- 函數
fn執行，fn先壓棧，放在棧（箱子）最底下 - 在函數 fn 內部，先執行函數
fn1，fn1壓棧在fn上面 - 函數
fn1執行，遇到return關鍵字，返回this is fn1，fn1出棧，箱子里現在只剩下fn - 回到
fn內部，fn1執行完后，函數fn2開始執行，fn2壓棧，但是在fn2內部，遇到fn3，開始執行fn3，所以fn3壓棧 - 此時棧中從下往上順序為：
fn3<=fn2<=fn，fn在最底下 - 以此類推，函數
fn3內部遇到return關鍵字的句子，fn3執行完結束后出棧，回到函數fn2中 ，fn2也是遇到return關鍵字，繼續出棧。 - 現在棧中只有
fn了，回到函數fn中，執行console.log('All fn are done') 語句后，fn出棧。 - 現在棧中又為空了。
上面步驟容易把人繞暈，下面是流程圖：
再看下在 chrome 瀏覽器環境下執行：
3. 遞歸
先看下簡單的 JavaScript 遞歸
function sumRange(num) {if (num === 1) return 1;return num + sumRange(num - 1)
}sumRange(3) // 6
復制代碼上面代碼執行順序：
- 函數
sumRange(3)執行，sumRange(3)壓棧，遇到return關鍵字，但這里還馬上不能出棧，因為調用了sumRange(num - 1)即sumRange(2) - 所以，
sumRange(2)壓棧,以此類推，sumRange(1)壓棧， - 最后，
sumRange(1)出棧返回 1，sumRange(2)出棧，返回 2，sumRange(3)出棧 - 所以
3 + 2 + 1結果為 6
看流程圖
所以，遞歸也是個壓棧出棧的過程。
遞歸可以用非遞歸表示，下面是上面遞歸例子等價執行
// for 循環
function multiple(num) {let total = 1;for (let i = num; i > 1; i--) {total *= i}return total
}
multiple(3)
復制代碼4. 遞歸注意點
如果上面例子修改一下，如下：
function multiple(num) {if (num === 1) console.log(1)return num * multiple(num - 1)
}multiple(3) // Error: Maximum call stack size exceeded
復制代碼上面代碼第一行沒有 return 關鍵字句子，因為遞歸沒有終止條件，所以會一直壓棧，造成內存泄漏。
遞歸容易出錯點
- 沒有設置終止點
- 除了遞歸，其他部分的代碼
- 什么時候遞歸合適
好了，以上就是 JavaScript 方式遞歸的概念。
下面是練習題。
6. 練習題目
- 寫一個函數，接受一串字符串，返回一個字符串，這個字符串是將原來字符串倒過來。
- 寫一個函數，接受一串字符串，同時從前后開始拿一位字符對比，如果兩個相等，返回
true，如果不等，返回false。 - 編寫一個函數，接受一個數組，返回扁平化新數組。
- 編寫一個函數，接受一個對象，這個對象值是偶數，則讓它們相加，返回這個總值。
- 編寫一個函數，接受一個對象，返回一個數組，這個數組包括對象里所有的值是字符串
7. 參考答案
參考1
function reverse(str) {if(str.length <= 1) return str; return reverse(str.slice(1)) + str[0];
}reverse('abc')
復制代碼參考2
function isPalindrome(str){ if(str.length === 1) return true;if(str.length === 2) return str[0] === str[1]; if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) return false;
}var str = 'abba'
isPalindrome(str)
復制代碼參考3
function flatten (oldArr) {var newArr = [] for(var i = 0; i < oldArr.length; i++){ if(Array.isArray(oldArr[i])){ newArr = newArr.concat(flatten(oldArr[i])) } else { newArr.push(oldArr[i])}}return newArr;
}flatten([1,[2,[3,4]],5])
復制代碼參考4
function nestedEvenSum(obj, sum=0) {for (var key in obj) { if (typeof obj[key] === 'object'){ sum += nestedEvenSum(obj[key]); } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ sum += obj[key]; }} return sum;
}nestedEvenSum({c: 4,d: {a: 2, b:3}})
復制代碼參考5
function collectStrings(obj) {let newArr = []for (let key in obj) {if (typeof obj[key] === 'string') {newArr.push(obj[key])} else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {newArr = newArr.concat(collectStrings(obj[key]))}}return newArr
}var obj = {a: '1',b: {c: 2,d: 'dd'}}collectStrings(obj)
復制代碼5. 總結
遞歸精髓是，往往要先想好常規部分是怎樣的，在考慮遞歸部分，下面是 JavaScript 遞歸常用到的方法
- 數組：
slice,concat - 字符串:
slice,substr,substring - 對象：
Object.assign
