快捷導(dǎo)航

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

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

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

前言

我們?cè)趯憳I(yè)務(wù)代碼的時(shí)候，或多或少都會(huì)遇到需要使用遞歸的場(chǎng)景，比如在遍歷樹(shù)形結(jié)構(gòu)時(shí)。

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

遞歸的基本理解

表象理解

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

實(shí)質(zhì)理解

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

具體實(shí)現(xiàn)

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

實(shí)例解析

接下來(lái)我們通過(guò)一個(gè)實(shí)例來(lái)講解遞歸的應(yīng)用。

求斐波那契數(shù)

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

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

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

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

Base case: 0號(hào)位置的斐波那契數(shù)是0，1號(hào)位置的斐波那契數(shù)是1。即:n === 0 return 0, n === 1 return 1;
Recursive rule: n號(hào)位置的值 = 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);
}

時(shí)間復(fù)雜度分析

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

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

空間復(fù)雜度分析

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

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

執(zhí)行順序分析

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

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