為了理解遞歸寫的。真想求Fibonacci前n項，迭代是更好的選擇，簡單并且速度快。另外，注意一下溢出問題。

遞歸算法速度慢的原因

遞歸調用本身需要使用系統棧,每次分配函數內存以及棧都需要時間.不過這個過程耗時并不多,可以說,單純的遞歸本身并不比非遞歸慢多少.
然而,實踐中就會發現,遞歸處理部分問題,特別是遞推類問題時會表現出效率極低.這個問題的出現是因為重復計算.
舉例說,用遞歸求解斐波那契數列的第n項,一般的遞歸公式為

f(n) = f(n-1)+f(n-2)
f(2) = 1
f(1) = 1

請嘗試模擬計算機運行這個遞歸,你會發現,其中的某一項f(x)并不是只算了一次. 當你計算f(5)的時候,你會試圖計算f(4)和f(3),然而在你計算f(4)的時候其實也要計算f(3),這樣f(3)就被調用了兩次.
計算Fibonacci(5)為例：

從上圖可以看出，在計算Fib(5)的過程中，Fib(1)計算了兩次、Fib(2)計算了3次，Fib(3)計算了兩次，本來只需要5次計算就可以完成的任務卻計算了9次。這個問題隨著規模的增加會愈發凸顯，以至于Fib(1000)已經無法再可接受的時間內算出。
想象這個過程是指數型擴展的,效率會隨著n的增大極快地下降.
要解決這個問題,可以使用記憶化思想.
定義記憶數組r,函數體改為:

define f(n):
if r[n] is defined, then simply return r[n] as the answer.
else, f(n) = f(n-1) + f(n-2)
before return the value, take it down in r[n].

如此改進之后的遞歸函數效率上與遞推算法相差無幾.

遞歸代碼

到后面計算速度巨慢

運行效果

計算斐波那契數列的前多少項?(輸入過大可能溢出)
30
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 請按任意鍵繼續. . .

//輸入一個數num，打印斐波那契數列的前num項 #include<iostream> using namespace std; int fib(int num)//n是當前項的值，num是當前項數 {if (num<=1)return 1;else return fib(num - 1) + fib(num - 2); } int main() {//輸入int num;cout << "計算斐波那契數列的前多少項?(輸入過大可能溢出)\n";cin >> num;//計算并輸出int i;for (i = 0; i < num; i++){cout << fib(i) << ' ';}system("pause"); }

迭代代碼

幾乎瞬間計算出來

運行效果

計算前多少項？
50
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 請按任意鍵繼續. . .

//打印斐波那契前n項 #include<iostream> using namespace std; int main() {//輸入int num;cout << "計算前多少項？\n";cin >> num;//計算long long int a[50] = { 1,1 };int i;for (i = 2; i < num; i++){a[i] = a[i - 1] + a[i - 2];cout << a[i] << ' ';}system("pause"); }

總結

以上是生活随笔為你收集整理的算法设计与分析（第三周）递归/迭代求Fibonacci前n项 【以及递归算法速度慢的原因】的全部內容，希望文章能夠幫你解決所遇到的問題。

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