一、原理

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

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

二、代碼實現(xiàn)

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

public class MyClass {public static void main(String[] args){int n = 10;System.out.println("斐波那契數(shù)列第 " + n + " 個數(shù)為 " + Fibonacci(n));}//遞歸  n代表第幾個數(shù)public static int Fibonacci(int n) {//前兩個數(shù)為 1//第三個數(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;}}}

時間復雜度：

• 最好情況下，當 n 等于 1 或 2 時，直接返回 1，時間復雜度為 O(1)。
• 最壞情況下，當 n 大于 2 時，需要遞歸調用 Fibonacci() 函數(shù)計算前兩個數(shù)的和，時間復雜度為 O(2^n)。因為每次遞歸調用會產(chǎn)生兩個子問題，每個子問題又會產(chǎn)生兩個更小的子問題，以此類推，直到遞歸到 n 等于 1 或 2。
• 平均情況下，時間復雜度也是 O(2^n)，因為每個數(shù)都需要通過遞歸調用計算得到。

空間復雜度：

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

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

三、運行結果

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