题目描述

       大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

题目分析

1. 很明显当n大于二时f(n) = f(n-1) + f(n-2)，可以使用递归，如：

	public int Fibonacci(int n) {
        if(n <= 1){
	        return n;
        }else if(n = 2){
        	return 1;
        }else{
	        return Fibonacci(n-1) + Fibonacci(n-2);
        }
    }

       这种简单的递归可以解决n比较小的情况，当n比较大时会导致栈溢出。因为重复计算，而且重复的情况还很严重，举个小点的例子，n=4，看看程序怎么跑的：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
                     = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
                     = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
n值越大时，重复越严重。

2. 迭代
          由于递归会导致重复计算严重，所以可以使用两个变量存储上一次的计算结果，正向迭代。

Java代码实现

public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n <= 2){
	        return 1;
        }
        int fn1 = 1,fn2=1;
        //fn1存储n-1的值，fn2存储n-2的值，然后迭代相加，n等于2时结束。
        while(n-- > 2){
            fn1 += fn2;
            fn2 = fn1 - fn2;
        }
        return fn1;
    }