斐波那契數(shù)的兩種實(shí)現(xiàn)方式———1.遞歸實(shí)現(xiàn)，2迭代實(shí)現(xiàn)

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

#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;
}

用迭代方法計(jì)算第N 個(gè)斐波那契數(shù)，時(shí)間復(fù)雜度O（N）,空間復(fù)雜度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;
}