用 JavaScript 的方式理解遞歸

snowLu 發布于2019-08-23 12:33 / 1302人閱讀

摘要：在分析遞歸之前，需要了解下中壓棧概念。在中，調用函數時，都會發生壓棧行為，遇到含關鍵字的句子或執行結束后，才會發生出棧。

原文地址

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

GPU云服務器云服務器 javascript理解如何理解javascript 深入理解javascript 用深度學習理解

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98715.html

LeetCode 之 JavaScript 解答第21題 —— 合并兩個有序鏈表（Merge Two

摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數的參數和返回值是什么參數是兩個合并的鏈表結點頭結點。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿題目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 評論0 收藏0
JavaScript 數據結構與算法之美 - 遞歸

摘要：遞歸常見問題及解決方案警惕堆棧溢出可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出。文章輸出計劃數據結構與算法之美的系列文章，堅持天左右更新一篇，暫定計劃如下表。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 前言算法為王。排序算法博大精深，前輩們用了數年甚至一輩子的心血研究出來的算法，更值得我們學習與...

Rocko 2019-08-23 18:29 評論0 收藏0
JS函數表達式的特征和遞歸

摘要：函數表達式是中的一個既強大又容易令人困惑的特性。函數表達式有幾種不同的語法形式。匿名函數的屬性是空字符竄。在把函數當成值使用的情況下，都可以使用匿名函數。不過，這并不是匿名函數唯一的用途。不過我們可以使用命名函數表達式來達成相同的成果。前言：最近在細讀Javascript高級程序設計，對于我而言，中文版，書中很多地方翻譯的差強人意，所以用自己所理解的，嘗試解讀下。如有紕漏或錯誤，會...

mudiyouyou 2019-08-23 12:32 評論0 收藏0
[翻譯] JS的遞歸與TCO尾調用優化

這兩天搜了下JS遞歸的相關文章，覺得這篇文章很不錯，就順手翻譯了下，也算給自己做個筆記，題目是我自己加的。原文很長，寫得也很詳盡，這里并非逐字翻譯，而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實際意義并不是特別大，但算法的邏輯挺有意思，不過也略抽象，理解需要花點時間（囧，估計我太閑了）文中的用例?全部來自原文：原文鏈接：（原題為：理解JS函數式編程中的遞歸）Underst...

pekonchan 2019-08-21 10:49 評論0 收藏0
JavasScript重難點知識

摘要：忍者級別的函數操作對于什么是匿名函數，這里就不做過多介紹了。我們需要知道的是，對于而言，匿名函數是一個很重要且具有邏輯性的特性。通常，匿名函數的使用情況是創建一個供以后使用的函數。 JS 中的遞歸遞歸, 遞歸基礎, 斐波那契數列, 使用遞歸方式深拷貝, 自定義事件添加這一次，徹底弄懂 JavaScript 執行機制本文的目的就是要保證你徹底弄懂javascript的執行機制，如果...

forsigner 2019-08-21 18:36 評論0 收藏0