跟我一起学算法系列10---斐波那契数列

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

2.算法分析
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。
该算法可以通过两种方式解决，一种是常规的规律法，另一种是递归算法。

3.代码实例
常规算法

public static int Fibo(int n) {
        if (n < 1)
            return 1;
        int n1 = 1;
        int n2 = 1;
        int result = 0;
        for (int i = 2; i <= n; i++){
            result = n1 + n2;
            n1 = n2;
            n2 = result;
        }

        return result;
    }

递归算法

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