面试题：斐波那契数列

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

f(n)=f(n-1)+f(n-2) 

f(0)=0

f(1)=1

思路：教科书上演示递归的方法并不好，因为递归要从上至下到底后再反弹，要空间存储,费时又费力。说明递归方法不好的最好途径就是画树，一目了然，因为使用递归，出现了太多重复计算，而且因此还需占用大量空间。当n=100，递归就明显能感觉到很慢了。所以使用递推明显更好，也是根据定义，由f(n-2)和f(n-1)的和得到f(n)。这样，每个f(n)就只计算一次，即时间复杂度是O(n)。

代码如下：

static long Fibonacci(int n)

        {

            if (n < 0)

                return -1;

            int[] result = { 0, 1 };

            if (n < 2)

                return result[n];

            long fibNMinusOne = 1;

            long fibNMinusTwo = 0;

            long fibN = 0;

            for (int i = 2; i <= n; i++)

            {

                fibN = fibNMinusOne + fibNMinusTwo;

                fibNMinusTwo = fibNMinusOne;

                fibNMinusOne = fibN;

            }

            return fibN;

        }

心得：斐波那契数列数列有很多应用，常见的《兔子繁殖》《青蛙跳台阶》，核心就是这个n规模的问题与n-1和n-2规模的问题有直接的联系。因为递归要从上至下又会弹，所以一般递归的都很烧时间，而且还要不小的辅助空间，改良的方法就是从下到上，也就是递推去改良不必要的计算。