斐波那契数列

什么是斐波那契数列?
前两个数字的之和等于第三个数字,比如:
0 1 1 2 3 5 8 13 21 ...

代码如下:
方法一:

package a02_fbo;
public class Main {
   public static int fib1(int n) {
       if (n <= 1) return n;
       return fib1(n - 1) + fib1(n - 2)
   }
   
   public static void main(String[] args) {
      System.out.print(fib1(0)); // 结果 0
      System.out.print(fib1(1)); // 结果 1
      System.out.print(fib1(2)); // 结果 1
      System.out.print(fib1(3)); // 结果 2
      System.out.print(fib1(4)); // 结果 3
   }
}

上面方法的话在计算结果上不会出现问题,但逻辑过于简单,如果出现再大一些的数字,会出现卡顿!这是因为栈的空间不够支撑那么大的计算量,溢出了!

方法二:

package a02_fbo;

public class Main {
    public static int fib1(int n) {
        if(n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
    }
            
    public static int fib2(int n) {
        if(n <= 1) return n;
        int frist = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = frist + second;
            frist = second;
            second = sum;
        }
        return second;
    }
    
    public static void main(String[] args) {
        System.out.print(fib2(64)); // 结果 1640636603
    }
}

这样写不管多大的数字都能快速给出打印结果