遞歸和循環計算斐波那契數列第n項的值

遞歸和循環計算斐波那契數列第n項的值。遞歸的底層實現原理。

開始

計算斐波那契數列第n項的值。

斐波那契數列

斐波那契數列，是數學家以兔子繁殖為例子引入，又稱為兔子數列。如下：

1、1、2、3、5、8、12、21、34…

第一項和第二項為1，其後，每一項都是它之前兩項的和。歸納公式如下：

f(1) = 1

f(2) = 2

f(n) = f(n-1) + f(n-2) （n>=3，n∈N*）

算法

我們可以通過遞歸的方式，得到結果，如下：

遞歸

遞歸是一個程序自身調用自身的一個過程，這句話，聽起來說起來簡單，理解起來又有些複雜。那應該怎麼去理解它呢？我們從兩個層面去理解：

1． 自己調用自己。在一個方法的內部調用這個方法本身，這是遞歸的基本結構。有這個結構，才叫遞歸。

2． 有終止條件。這個其實不算是遞歸的結構，但卻是一個正確的遞歸方法的必要條件。因為，如果沒有終止條件，那麼，自己將不斷調用自己，好像陷入了一個無底洞一般。（注意，這是不是死循環）。所以，一個正確的遞歸方法，必然需要一個有效的終止條件。

計算階乘的遞歸

棧

棧是一種線性表數據結構，一端為棧頂，另一端為棧底，所有元素只能從棧頂進入，稱為入棧，也只能從棧頂取出，稱為出棧。

從JVM內存角度來看，棧是一塊特殊的內存空間，這塊內存空間，之所以稱之為棧，就是因為，它和數據結構棧有著相似的操作方式。

每開啟一個線程，JVM就會為它分配一個棧，棧中，以幀為單位，保存線程的運行狀態，JVM對棧的操作只有兩種，入棧一個幀，或者出棧一個幀。

幀用來保存線程的運行狀態，那麼，線程的運行狀態指什麼？我們說，線程的的運行狀態，指的是當前線程正在執行的方法，以及調用這個方法時傳入的參數，方法的局部變量和中間運行結果。正在執行的方法，這個不用解釋。調用方法時傳入的參數，因為同一個方法，參數不同，結果自然不同，所以，這肯定是一個運行狀態。局部變量，方法中的每個局部變量都和方法的最終結果相關，所以，這也算一個運行狀態。中間運行結果，當前方法執行到了哪一步，某個表達式的運算結果是什麼，也這和方法的結果相關。

綜上，我們發現，幀，對應了一個方法。事實上，JVM也是這麼做的，每開始調用一個方法，就會入棧一個幀，每執行完成一個方法，就會出棧一個幀。

假設某線程中，方法A調用B，B又調用了C。那麼，JVM對棧的操作可能如下：

幀（A）入棧

幀（B）入棧

幀（C）入棧

幀（C）出棧

幀（B）出棧

幀（A）出棧

假設某線程中，包含A方法的遞歸操作，那麼，JVM對棧的操作可能如下：

幀（A1）入棧

幀（A2）入棧

幀（A3）入棧

………………

幀（A3）出棧

幀（A2）出棧

幀（A1）出棧

A後面不同的數字，代表它們是同一個方法，不同的幀。

所以，我們發現，遞歸，事實上是同一個方法，不斷的入棧，等到達終止條件後，再不斷的出棧的過程。假設有一段臺階，從下至上，每層臺階上都放著一個蘋果，已知每層臺階的蘋果是否有毒，都和上一層臺階的蘋果結論相反，且至少有某一層，蘋果上有明確的標識說明是否有毒。那麼，該如果得知每一層的蘋果是否有毒呢？你只有一層一層向上，找到有明確標識的那一層，再一層一層向下，計算得到第一層蘋果是否有毒。遞歸，就是這樣一個拾階而上，再逐階而下的過程。

這個例子中，如果沒有任何一層的蘋果有明確是否有毒，那麼，你就會一直向上，而得不到結果。也就是說，如果遞歸沒有有效的終止條件，就會一直入棧，而無法出棧。我們知道，棧是一塊內存空間，自然有大小限制。不斷的入棧，就會導致棧深越界的錯誤發生。

循環

滿足特定條件時，不斷重複某一操作（循環體），即為循環。

對於JVM來說，循環是語句跳轉的一種，JVM通過一塊叫做程序計數器的內存空間，來存儲當前執行的語句的位置，並通過修改這個值，來達到語句跳轉的目的。

也就是說，循環是沒有不斷入棧和不斷出棧這個過程的，它只是在進入這個方法時，入棧一次，方法運行結束時，出棧一次，所以，一般來說，循環都比遞歸的效率要高，而且，也不會佔用大量的棧內存空間。

遞歸算法，一般也可以寫成循環。

如拾蘋果的例子，你就可以在上臺階的過程中，記住上了臺階的數量，在得到有標記的蘋果時，通過計算，得到第一層蘋果是否有毒。

再比如說斐波那契數列的循環實現方式如下：

結論

能用循環解決的問題，就不要用遞歸。