遞歸解斐波那契數列

斐波那契數列最直觀的遞歸解法：

int fib(int n){if (n<2) { return n;} else {return fib(n-1) + fib(n-2);} }

然而這種解法效率很低，會進行很多重復運算

例如：當計算 fib(5) 時，我們共需要計算1次 fib(4)，2次 fib(3)，3次 fib(2)，5次 fib(1) 和3次 fib(0)。這些無意義的重復計算使得遞歸效率極低。

遞歸解法的優化

實際上像斐波那契這樣的數列還有很多，他們都滿足相同的規律，即從第三項開始，每一項等于前兩項之和。這樣的數列被統稱為可加數列（additive sequence），不同的只是他們的第一項 t₀ 和 t₁。

斐波那契數列：
$$0,1,1,2,3,5,8,13,21,34,55,\dots$$

如果我們將它的第一項和第二項換成3和7，就會變成：
$$3,7,10,17,27,44,71,115,186,\dots$$

因此，求解斐波那契數列第n項的問題可以被轉化成求解一個可加數列的第n項的問題，而且只需要知道 t₀ 和 t₁ 的值，我們就可以求出數列中的任意一項。所以我們可以寫出一個函數：

int additiveSequence(int n, int t0, int t1);

下一步就是實現這個函數。繼續觀察可加數列，我們可以發現一個可加數列S中的第n項等于將這個數列每一項都向前移一位的新數列的第n-1項。

例如，原數列中的t₆ = 71:

當我們將該數列每一位都向前移動一位，得到一個新數列，此時 t₅ = 71：

而這個新的 t₀ 等于原數列的 t₁，新的 t₁ 等于原數列的 t₀ + t₁。

因此函數可以寫為：

int additiveSequence(int n, int t0, int t1){if (n==0) return t0;if (n==1) return t1;return additiveSequence(n-1, t1, t0+t1); }

遞歸求解斐波那契數列的完整函數就可寫為：

int fib(int n){return additiveSequence(n, 0, 1); }int additiveSequence(int n, int t0, int t1){if (n==0) return t0;if (n==1) return t1;return additiveSequence(n-1, t1, t0+t1); }

總結

以上是生活随笔為你收集整理的斐波那契数列递归解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。