递归算法
因为递归需要不断的调用自身，当n过大的时候，程序将会很慢效率不高，不推荐使用，关于递归实现算法，也很简单，很多教科书上都是这种解法。
//递归算法
long long Fibonacci(unsigned int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
非递归算法
我主要讲述一下非递归算法的实现，非递归算法是比较实用的，也是面试官比较喜欢的一种方法
递归的代码之所以慢是因为重复的计算太多，我们只需要想办法避免重复计算就好了。比如我们将已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查一下，如果前面已经计算过了句不用重复计算了，更简单的办法就是从下往上计算，首先呢根据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 fibone = 0;
long long fibtwo = 1;
long long fibn = 0;
for (unsigned int i = 2; i <= n; i++)
{
fibn = fibone + fibtwo;
fibtwo = fibn;
fibone = fibtwo;
}
return fibn;
}
