斐波那契数列

关于递归和循环

1、通常基于递归的代码比基于循环的代码要简洁很多，更加容易实现，如果面试官没有特殊的要求，应聘者可以优先先采用递归的方法实现编程。

2、但是递归的缺点也很明显，递归时函数的调用自身，函数的调用是有时间和空间的消耗的，每次的函数调用都需要在内存栈中分配空间以用来保存参数，返回地址，临时变量，往栈中压入数据弹出数据都需要时间，故递归的实现效率一般不如循环。而且递归中有可能有大部分的计算都是重复的，导致性能变差。

3、递归也有可能引起严重的问题：调用栈溢出（每个进程的栈的容量是有限的，递归调用层级太，便会溢出）。

题目一：写一个函数，输入n,求斐波那契数列的第n项，斐波那契数列的定义如下：

　　　　　0, n=0;

f(n)=　　 1, 　 n=1;

　　　　　f(n-1)+f(n-2) 　　n>1;

根据这个递归式，就可以直接写出相差不大的递归版本代码实现，但是这样的自上而下的递归导致大量的重复计算，如下图：

几乎大量的重复计算上述递归树中的非叶子结点值，导致效率下降，而对于大数字也会导致，递归栈溢出。

故更好的方法是从底向上计算，直到计算出f(n).先计算f(2)=1+0;,然后保存住f(2),f(1),用来求出f(3),然后同理的每次更新f(n-1)和f(n-2),直至求出f(n);

递归（自顶向下）和循环（自底向上）的代码实现如下：

 1 #include<iostream>
 2 using namespace std;
 3 long long Fibonacci(unsigned int n)//递归版本，大量的重复计算
 4 {
 5     if (n <= 0)
 6         return 0;
 7     else if (n == 1)
 8         return 1;
 9     else{
10         return Fibonacci(n - 1) + Fibonacci(n - 2);
11     }
12 }
13 long long Fibonacci1(unsigned int n)//自底向上去除重复计算
14 {
15     int result[2] = { 0, 1 };
16     if (n < 2)
17         return result[n];
18     long long fibNMinusone = 1;
19     long long fibNMinustwo = 0;
20     long long fibN = 0;
21     for (int i = 2; i <= n; i++)
22     {
23         fibN = fibNMinusone + fibNMinustwo;
24         fibNMinustwo = fibNMinusone;//注意这两行的先后顺序，一定不可变
25         fibNMinusone = fibN;
26     }
27     return fibN;
28 }
29 int main()
30 {
31     //cout << Fibonacci(40) << endl;//VS2013 update 4挂掉
32     cout << Fibonacci1(100) << endl;//依然可以计算
33     system("pause");
34     return 0;
35 }

以下是斐波那契数列的几种变形：

题目二：一只青蛙一次可以跳1级台阶，也可以调2级台阶，问青蛙跳上n级台阶有多少种跳法？

题目三：