深入了解JavaScript中遞歸的理解與實現(xiàn)

更新時間：2022年06月27日 08:55:19 作者：神奇的程序員

本文將通過遞歸的經(jīng)典案例：求斐波那契數(shù)來講解遞歸，通過畫遞歸樹的方式來講解其時間復雜度和空間復雜度以及遞歸的執(zhí)行順序，感興趣的可以了解一下

前言

我們在寫業(yè)務(wù)代碼的時候，或多或少都會遇到需要使用遞歸的場景，比如在遍歷樹形結(jié)構(gòu)時。

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

遞歸的基本理解

表象理解

函數(shù)會自己調(diào)用自己
每一次調(diào)用，函數(shù)的參數(shù)都會收斂變小

實質(zhì)理解

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

具體實現(xiàn)

先寫B(tài)ase case，定義基線條件，判斷其是否為最小號問題，避免死循環(huán)
Recursive rule：遞歸規(guī)則

實例解析

接下來我們通過一個實例來講解遞歸的應(yīng)用。

求斐波那契數(shù)

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

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

我們知道怎么計算斐波那契數(shù)后，就可以用遞歸來將其實現(xiàn)了。

我們可以將上述遞歸的理解中應(yīng)用到求斐波那契數(shù)里，實現(xiàn)思路和實現(xiàn)代碼如下：

Base case: 0號位置的斐波那契數(shù)是0，1號位置的斐波那契數(shù)是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);
}

時間復雜度分析

我們將上述代碼執(zhí)行過程轉(zhuǎn)換成如下圖所示的遞歸樹，觀察二叉樹中的節(jié)點后我們發(fā)現(xiàn)如下規(guī)律：

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

空間復雜度分析

分析空間復雜度我們可以通過遞歸的執(zhí)行順序來分析，我們將上述代碼的執(zhí)行順序整理成遞歸圖標示其執(zhí)行順序，我們發(fā)現(xiàn)如下規(guī)律：

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

執(zhí)行順序分析

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

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