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全稱(chēng)為：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行。