斐波那契數的兩種實現方式———1.遞歸實現，2迭代實現

    對于斐波那契數，若是采用遞歸的算法，每個遞歸調用都將觸發另外兩個遞歸調用，而這兩個中調用任意一個還會觸發另外兩個的調用。遞歸調用的時間復雜度O(2^N),空間復雜度為O(N)，所以在計算略大的數會花費一定的時間和空間。遞歸程序如下：

#include<iostream>
using namespace std;

unsigned long long Fib(size_t num)
{
    if (num < 2)
    {
        return num;
    }
    else
        return Fib(num - 1) + Fib(num - 2);
}
int main()
{
    unsigned long long ret = Fib(10);
    cout << ret << endl;
    system("pause");
    return 0;
}

用迭代方法計算第N 個斐波那契數，時間復雜度O（N）,空間復雜度O（1），程序如下：

#include<iostream>
using namespace std;

unsigned long long Fib(size_t num)
{
    unsigned long long first = 0;
    unsigned long long second = 1;
    unsigned long long sum = 0;
    if (num < 2)
        return num;
    else
       for (size_t i = 2; i <= num; i++)
       {
           sum = first + second;
           first = second;
           second = sum;
       }
       return sum;
}

int main()
{
    unsigned long long ret = Fib(10);
    cout <<"Fibonacci(10)="<< ret << endl;
    system("pause");
    return 0;
}