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

本篇文章帶給大家的內容是關於遞迴是什麼？ 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

上面程式碼第一行沒有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中文網其他相關文章！