深入瞭解JavaScript中遞歸的理解與實現

Posted on 2022-06-27 by WalkonNet

前言

我們在寫業務代碼的時候，或多或少都會遇到需要使用遞歸的場景，比如在遍歷樹形結構時。

本文將通過遞歸的經典案例：求斐波那契數來講解遞歸，通過畫遞歸樹的方式來講解其時間復雜度和空間復雜度以及遞歸的執行順序，歡迎各位感興趣的開發者閱讀本文。

遞歸的基本理解

表象理解

函數會自己調用自己
每一次調用，函數的參數都會收斂變小

實質理解

把一個大問題變成1個或n個小問題
用同樣的邏輯來解決這些問題
最後把他拼湊起來，拼成全局問題

具體實現

先寫Base case，定義基線條件，判斷其是否為最小號問題，避免死循環
Recursive rule：遞歸規則

實例解析

接下來我們通過一個實例來講解遞歸的應用。

求斐波那契數

求特定位置的斐波那契數，用遞歸實現代碼很簡單，接下來我們先看下斐波那契數的概念。

0號位置的斐波那契數是0
1號位置的斐波那契數是1
n(n>1)號位置的斐波那契數等於 n-1位置的斐波那契數 + n-2位置的斐波那契數

我們知道怎麼計算斐波那契數後，就可以用遞歸來將其實現瞭。

我們可以將上述遞歸的理解中應用到求斐波那契數裡，實現思路和實現代碼如下：

Base case: 0號位置的斐波那契數是0，1號位置的斐波那契數是1。即:n === 0 return 0, n === 1 return 1;
Recursive rule: n號位置的值 = n – 1位置的值 + n – 2位置的值，即:fibonacciNumbers(n – 1) + fibonacciNumbers(n – 2);

const fibonacciNumbers = function(n){
    // base case
    if(n === 0){
        return 0;
    }else if(n === 1){
        return 1;
    }
    
    // Recursive rule
    return fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2);
}

時間復雜度分析

我們將上述代碼執行過程轉換成如下圖所示的遞歸樹，觀察二叉樹中的節點後我們發現如下規律：

第0層有1個節點，第1層有2個節點，第2層有4個節點，第3層…第n層，每一層的節點數都是上一層的2倍。
即：1 + 2 + 4 + 8 + 2^(n-1)，等比數列求和後：2^n，時間復雜度為：O(2^n)。
最後一層結點的總數，遠遠超過其他所有層的總數。
時間復雜度取決於遞歸樹中一共有多少節點。
所有遞歸的時間復雜度都可以通過遞歸樹來分析。

空間復雜度分析

分析空間復雜度我們可以通過遞歸的執行順序來分析，我們將上述代碼的執行順序整理成遞歸圖標示其執行順序，我們發現如下規律：

由於馮諾伊曼體系的影響，遞歸樹執行時采用深度優先的方式執行。即：順著一條線執行到底（蜜橙色線條）。
圖中每一層執行時的bp全稱為：break point，每一層執行到bp時，會將當前層的變量(n)記錄一下，放進Call stack中。
由於執行遞歸樹中的每一層時，都會有一個Call stack操作，將當前層的變量(n)放進去，因此遞歸樹中有多少個調用棧取決於遞歸樹的層數，因此空間復雜度為O(n)。
空間復雜度與節點總數關系不大，與其在Call stack裡總共存瞭多少層直接相關。
所有遞歸的空間復雜度都可以通過遞歸樹來分析。

執行順序分析

上述遞歸圖的執行順序如下圖所示，接下來帶著代價來分析下每一步都做瞭哪些事情：

當函數執行到return fibonacciNumbers(n – 1) + fibonacciNumbers( n – 2) 的時候，由於馮諾伊曼體系的影響，它不會並行執行，他會先執行fibonacciNumbers(n – 1)函數，觸發基線條件時，return到上一層，取出其在上一層在call Stack中存儲的n的值，然後再去執行fibonacciNumbers( n – 2)函數，計算它右子樹的值。
因此他會先執行fibonacciNumbers(n – 1)函數，即:F(4) => F(3) … =>F1（圖中的第1行）
當他執行到F(1)的時候，n = 1，觸發基線條件return 1返回到上一層F(2)，即圖中的第2行
返回到F(2)層時，取出當前層Call Stack中存儲的n的值，執行fibonacciNumbers(n – 2)函數，執行到F(0)，即圖中的第3行
此時F(0)中n的值為0，觸發基線條件，return 0，即圖中的第4行
此時(2)節點的左子樹和右子樹的值都計算出來瞭，因此可以執行fibonacciNumbers(n – 1) + fibonacciNumbers( n – 2)函數，將左、右子樹的值相加，即得到瞭F(2)的值，然後return至上一層F(3)，即圖中的第5行。
返回到F(3)時，與第3步一樣，獲取其右子樹的值，然後重復第3至6步的步驟，直至計算出F(3)和F(2)的值，將其相加就得出瞭F(4)的值，此時F(4)處的值就是我們需要求的斐波那契數，即圖中的第6～16行。

以上就是深入瞭解JavaScript中遞歸的理解與實現的詳細內容，更多關於JavaScript遞歸的資料請關註WalkonNet其它相關文章！

深入瞭解JavaScript中遞歸的理解與實現

目錄

前言

遞歸的基本理解