如何用遞歸的方法計算并輸出斐波那契數列的第n項？

關于斐波那契數列求第n項，通常有遞歸求法、遞推求法、公式求法、矩陣快速冪求法，遞歸的方法效率是最低的。那么我就來分別講這幾種方法

一. 遞歸方法

雖然同樣是遞歸，但是不同的寫法也是有講究的，例如可以有如下兩種寫法

二. 遞推求法

遞推求法比較直接，通過數組，那么有fib[n] = fib[n - 1] + fib[n - 2]，直接遞推就可以了。

三. 公式求法

直接通過如下公式求即可，但缺點是精度可能會損失。

四. 矩陣快速冪

通過構造矩陣，進行遞推得到

然后通過快速冪進行分治求解，時間復雜度為O(log(n))。