斐波那契数列

面试题：斐波那契数列

题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

// ====================方法1：递归====================
long long Fibonacci_soultion1(unsigned int n)
{
    if(n<= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci_soultion1(n-1)+Fibonacci_soultion1(n-2);
}

// ====================方法2：循环====================
long long Fibonacci_soultion2(unsigned n)
{
    int result[2] = {0, 1};
    if(n<2)
        return result[n];

    long long fibNOne = 1;
    long long fibNTwo = 0;
    long long fibN = 0;

    for(unsigned int i=2; i<=n; i++)
    {
        fibN = fibNOne + fibNTwo;

        fibNTwo = fibNOne;
        fibNOne = fibN;
    }
    return fibN;
}

int main()
{
    int n=0;
    cin>>n;
    cout<<Fibonacci_soultion1(n)<<endl;
    // Fibonacci_soultion1(100)  3.495s
    // Fibonacci_soultion1(100)  3.380s
    return 0;
}

通常基于递归实现的代码比基于循环实现的代码要简洁很多，但同时也有显著的缺点，递归由于是调用自身，而函数调用是有时间和空间消耗的：每一次函数调用都需要在内存堆栈中分配空间以保存参数、返回地址及临时变量，而且往堆栈里压入数据和弹出数据都需要时间。这就不难理解例子中递归效率不如循环。