一、原理

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱“兔子數(shù)列”，其數(shù)值為：1、1、2、3、5、8、13、21、34……

在數(shù)學(xué)上，這一數(shù)列以如下遞推的方法定義：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

二、代碼實(shí)現(xiàn)

要計(jì)算第 n 個(gè)斐波那契數(shù)列的數(shù)字，我們可以使用以下遞歸函數(shù)：

public class MyClass {public static void main(String[] args){int n = 10;System.out.println("斐波那契數(shù)列第 " + n + " 個(gè)數(shù)為 " + Fibonacci(n));}//遞歸  n代表第幾個(gè)數(shù)public static int Fibonacci(int n) {//前兩個(gè)數(shù)為 1//第三個(gè)數(shù)及后面的數(shù)為前面兩數(shù)之和//如果輸入的 n 不合法將返回 -1if (n == 1 || n == 2) {return 1;} else if (n > 2) {return Fibonacci(n - 1) + Fibonacci(n - 2);} else {return -1;}}}

時(shí)間復(fù)雜度：

• 最好情況下，當(dāng) n 等于 1 或 2 時(shí)，直接返回 1，時(shí)間復(fù)雜度為 O(1)。
• 最壞情況下，當(dāng) n 大于 2 時(shí)，需要遞歸調(diào)用 Fibonacci() 函數(shù)計(jì)算前兩個(gè)數(shù)的和，時(shí)間復(fù)雜度為 O(2^n)。因?yàn)槊看芜f歸調(diào)用會(huì)產(chǎn)生兩個(gè)子問題，每個(gè)子問題又會(huì)產(chǎn)生兩個(gè)更小的子問題，以此類推，直到遞歸到 n 等于 1 或 2。
• 平均情況下，時(shí)間復(fù)雜度也是 O(2^n)，因?yàn)槊總€(gè)數(shù)都需要通過遞歸調(diào)用計(jì)算得到。

空間復(fù)雜度：

• 由于遞歸調(diào)用會(huì)在堆棧中保存每次調(diào)用的局部變量和返回地址，所以空間復(fù)雜度取決于遞歸的深度。在最壞情況下，遞歸深度為 n，所以空間復(fù)雜度為 O(n)。

綜上所述，該遞歸實(shí)現(xiàn)的斐波那契數(shù)列函數(shù)的時(shí)間復(fù)雜度為指數(shù)級的 O(2^n)，空間復(fù)雜度為線性的 O(n)。由于指數(shù)級的時(shí)間復(fù)雜度，在計(jì)算較大的斐波那契數(shù)時(shí)，遞歸實(shí)現(xiàn)會(huì)變得非常慢。

三、運(yùn)行結(jié)果

斐波那契數(shù)列第 10 個(gè)數(shù)為 55