递归和循环-斐波那契数列

• 如果我们需要重复地多次计算相同的问题，通常可以选择用递归或者循环两种不同的方法。
• 递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。
• 在面试的时候，如果面试官没有特别的要求，应聘者可以尽量多采用递归。
• 通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，应聘者可以优先采用递归的方法编程。
• 递归还有可能引起更严重的问题：调用栈溢出。

  写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

递归

long Fibonacci(unsigned int n)
{
    if(n <= 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

• 计算量会随着n 的增大而急剧增大
• 用递归方法计算的时间复杂度是以n的指数的方式递增的

更简单的办法是从下往上计算，首先根据f（0）和f（1）算出f（2），再根据f（1）和f（2）算出f（3）……依此类推就可以算出第n 项了，这种思路的时间复杂度是O(n)
面试官期待的实用解法:

long long Fibonacci(unsigned int n)
{
    int result[2] = {0,1};
    if(n<2)
        return result[n];
    long long fibNMinusOne = 1;
    long long fibNMinusTwo = 0;
    long long fibN = 0;
    for (unsigned int i = 2; i < n; ++i)
    {
        fibN             = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo    = fibNMinusOne;
        fibNMinusOne    = fibN;
    }
    return fibN;
}