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);
}

時間復(fù)雜度分析

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

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

空間復(fù)雜度分析

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

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

執(zhí)行順序分析

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

當(dāng)函數(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行）
當(dāng)他執(zhí)行到F(1)的時候，n = 1，觸發(fā)基線條件return 1返回到上一層F(2)，即圖中的第2行
返回到F(2)層時，取出當(dāng)前層Call Stack中存儲的n的值，執(zhí)行fibonacciNumbers(n - 2)函數(shù)，執(zhí)行到F(0)，即圖中的第3行
此時F(0)中n的值為0，觸發(fā)基線條件，return 0，即圖中的第4行
此時(2)節(jié)點(diǎn)的左子樹和右子樹的值都計算出來了，因此可以執(zhí)行fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2)函數(shù)，將左、右子樹的值相加，即得到了F(2)的值，然后return至上一層F(3)，即圖中的第5行。
返回到F(3)時，與第3步一樣，獲取其右子樹的值，然后重復(fù)第3至6步的步驟，直至計算出F(3)和F(2)的值，將其相加就得出了F(4)的值，此時F(4)處的值就是我們需要求的斐波那契數(shù)，即圖中的第6～16行。