本篇文章帶給大家的內容是關於遞迴是什麼? javascript中遞歸的詳解,有一定的參考價值,有需要的朋友可以參考一下,希望對你有幫助。
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()
上面發生了一系列壓棧出棧的行為:
1、首先,一開始堆疊(箱子)是空的
2、函數fn 執行, fn 先壓棧,放在堆疊(箱子)最底下
3、在函數fn 內部,先執行函數fn1,fn1 壓棧在fn 上面
4、函數fn1 執行,遇到return 關鍵字,返回this is fn1,fn1 出棧,箱子裡現在只剩下fn
5、回到fn 內部,fn1 執行完後,函數fn2 開始執行,fn2 壓棧,但是在fn2 內部,遇到fn3,開始執行fn3,所以fn3 壓棧
6、此時棧中從下往上順序為:fn3
7、以此類推,函數fn3 內部遇到return 關鍵字的句子,fn3 執行完結束後出棧,回到函數fn2 中,fn2 也是遇到return 關鍵字,繼續出棧。
8、現在堆疊中只有 fn 了,回到函數 fn 中,執行 console.log('All fn are done') 語句後,fn 出棧。
9、現在堆疊中又為空了。
上面步驟容易把人繞暈,下面是流程圖:
#再看下在chrome 瀏覽器環境下執行:
##3. 遞迴
先看簡單的JavaScript 遞歸
function sumRange(num) { if (num === 1) return 1; return num + sumRange(num - 1) } sumRange(3) // 6
上面程式碼執行順序:
1、函數sumRange(3) 執行,sumRange(3) 壓棧,遇到return 關鍵字,但這裡還馬上不能出棧,因為調用了sumRange(num - 1) 即sumRange(2)
2、所以,sumRange(2) 壓棧,以此類推,sumRange(1) 壓棧,
3、最後, sumRange(1) 出棧回傳1,sumRange(2) 出棧,回傳2,sumRange(3) 出棧
4、所以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
遞迴容易出錯點
6. 練習題目
1、寫一個函數,接受一串字串,回傳一個字串,這個字串就是將原來字串倒過來。 2、寫一個函數,接受一串字串,同時從前後開始拿一位字元對比,如果兩個相等,則回傳 true,如果不等,則回傳 false。 3、寫一個函數,接受一個數組,並回傳扁平化新數組。 4、寫一個函數,接受一個對象,這個對象值是偶數,則讓它們相加,回傳這個總值。 5、寫一個函數,接受一個對象,回傳一個數組,這個數組包含對象裡所有的值是字串7.參考答案
參考1function reverse(str) { if(str.length 參考2<p></p><pre class="brush:php;toolbar:false">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)
function flatten (oldArr) { var newArr = [] for(var i = 0; i 參考4<p></p><pre class="brush:php;toolbar:false">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}})
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
以上是遞迴是什麼? javascript中遞歸的詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!