首頁 > web前端 > js教程 > 主體

遞迴是什麼? javascript中遞歸的詳解

不言
發布: 2018-10-26 16:03:44
轉載
4411 人瀏覽過

本篇文章帶給大家的內容是關於遞迴是什麼? 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、現在堆疊中又為空了。

上面步驟容易把人繞暈,下面是流程圖:

遞迴是什麼? javascript中遞歸的詳解

#再看下在chrome 瀏覽器環境下執行:

遞迴是什麼? javascript中遞歸的詳解



##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

#看流程圖

遞迴是什麼? javascript中遞歸的詳解

所以,遞迴也是個壓棧出堆疊的過程。

遞迴可以用非遞歸表示,下面是上面遞歸例子等價執行

// 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 關鍵字句子,因為遞迴沒有終止條件,所以會一直壓棧,造成記憶體洩漏。

遞迴容易出錯點

  1. 沒有設定終止點

  2. 除了遞迴,其他部分的程式碼

  3. 什麼時候遞迴合適

#好了,以上就是JavaScript 方式遞歸的概念。

下面是練習題。

6. 練習題目

1、寫一個函數,接受一串字串,回傳一個字串,這個字串就是將原來字串倒過來。

2、寫一個函數,接受一串字串,同時從前後開始拿一位字元對比,如果兩個相等,則回傳 true,如果不等,則回傳 false。

3、寫一個函數,接受一個數組,並回傳扁平化新數組。

4、寫一個函數,接受一個對象,這個對象值是偶數,則讓它們相加,回傳這個總值。

5、寫一個函數,接受一個對象,回傳一個數組,這個數組包含對象裡所有的值是字串

7.參考答案

參考1

function 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)
登入後複製
參考3

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}})
登入後複製
參考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

以上是遞迴是什麼? javascript中遞歸的詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:segmentfault.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板