斐波那契列數列的遞歸與迭代

談到斐波那契數列

• 常想到的是遞歸，由于在電腦中存儲數據是開辟棧來存儲，若是所要計算的值太大，要面對兩個問題，一個是時間問題：對一數的計算，遞歸和回溯過程中會重復對一個值（例如f（3））進行開辟空間釋放空間，因而會十分耗時；另一個問題是空間問題：由于系統分給程序的?？臻g是有限的，當數字太大，最終產生的?？臻g的情況，即棧溢出，導致我們無法計算。

• 第二個想到的是通過數組來存儲，即將每一個計算后的值都存到數組里，雖然解決了在時間上的問題，但也會出現棧溢出，無法計算大的斐波那契數。

為了解決大數問題同時提高時間上的效率我們采用迭代的方法（實際上通過循環來實現）。
下面為其代碼描述：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int number;
    int first, second, third;
    scanf("%d", &number);
    first = 1;
    second = 1;
    if (number < 3)
        third = 1;
    while (number >= 3)
    {
        third = first + second;
        first = second;
        second = third;
        number--;
    }
    printf("%d\n", third);
    system("pause");
    return 0;
}

在Linux操作系統下可看出兩者計算同一個f(n)迭代所需要的時間比遞歸所需要的時間要少的多多多。。而且所求的數多大都可以，因為沒有限制，只是進行加法和賦值運算，也沒有需要很多的空間。
通過該例子，可發現迭代的實現往往比遞歸實現效率高，但并不是遞歸就沒有自身的優點。
遞歸相當于其他方法，他的可讀性很高，另外當一個問題很復雜時，使用迭代或其他方法會很難實現（例如Hanoi問題，青蛙跳臺階問題）此時用遞歸思想可以將問題簡潔明了的解決，這樣就補償了他所帶來的運行時開銷。