定义：

斐波那契数列（Fibonacci sequence），又称[黄金分割]数列、因[数学家]列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“[兔子数列]”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

递推公式：

F(n)=F(n - 1)+F(n - 2)，（n≥ 3，n ∈ N*）

算法思路;

很容易看出，f(n)的值取决于f(n-1)与f(n-2)之和，当我们需要求f(n)的值时，就需要先求f(n-1)和f(n-2)的值，而要求f(n-1)的值就需要先求f(n-2)和f(n-3)的值，以此类推，直到求f(1)和f(2)的值，因为f(1)和f(2)已知，故可以得出f(n)的值。
具体实现时分两个方向：
①从要求的数值以此向前求，这是递归方法。
②从3开始求，逐渐向后推，直到推到要求的数值则停止，这是迭代法。

算法设计：

①递归算法：
时间复杂度：O(2^n)

public static long GetByRecursion(long n){
   if(n==1||n==2)return 1;
   else return GetByRecursion(n-1)+GetByRecursion(n-2); //递归调用
}

②迭代算法
时间复杂度：O(n)

public static long GetByIteration(long n){
    long a=1,b=1;
    for(long i=3;i<n;i++){
        long temp=a+b;
        a=b;
        b=temp;
    }
    return b;
}