斐波纳契数列各种解法

1、求第n个斐波纳契数？

第一种解法：使用递归方式

 /**
 *  斐波那数列
 *
 *  0 1 1 2 3 5 8 。。。。
 *
 *  使用递归方式 思路 就是 当n <=1的时候直接返回 0或者1 只有从n=2到开始计算   数列的和 =  第一个数 + 第二个数  也就是 sum = (n-1) + (n-2);
 *使用这个递归方式 如果是n比较大 算法上 耗时比较长 有性能问题 设置个n=65 就卡住了
 * @param n
 */  
public static   int  fib1(int n){
     //如果不做这个判断那就死循环了
    if (n <= 1) return n;

    return  fib1(n-1) + fib1(n-2);

}

第二种解法：使用for循环

 /**
 *  斐波那数列
 *
 *  0 1 1 2 3 5 8 。。。。
 *
 *  使用递归方式 思路 就是 当n <=1的时候直接返回 0或者1 只有从n=2到开始计算   数列的和 =  第一个数 + 第二个数  也就是 sum = (n-1) + (n-2);
 *使用这个递归方式 如果是n比较大 算法上 耗时比较长 
     * @param n
   */  
  public static   int  fib2(int n){
    if (n <= 1) return n;
    int first = 0;
    int second = 1;

    for (int i =0 ;i< n-1;i ++){
      int sum = first + second;
      first = second;
      second =sum;
    }
    return  second;
}