1、普通递归方法

    1. private static int febonache(int n) {
    2.     if(n == 1){
    3.         return 1;
    4.     }else if(n == 2 ){
    5.         return 2;
    6.     }else {
    7.         return febonache(n-1) + febonache(n-2);
    8.     }
    9. }

    这个递归的时间复杂度是O(2^n)，因为里面包含了大量重复的计算
    2、不用递归方法

    1. private static  int noDiguiFebonache(int n){
    2.     if(n<=2){
    3.         return 1;
    4.     }
    5.     int a = 1;
    6.     int b = 1;
    7.     int c = 2;
    8.     for (int i = 2; i <= n; i++) {
    9.         c = a + b;
    10.         a = b;
    11.         b = c;
    12.     }
    13.     return c;
    14. }

    借助一个数组

    1. private static int arrFebonache(int n){
    2.     if(n<=2){
    3.         return 1;
    4.     }
    5.     int[] data = new int[n];
    6.     data[0] = 1;
    7.     data[1] = 1;
    8.     for (int i = 2; i < n; i++) {
    9.         data[i] = data[i-1] + data[i-2];
    10.     }
    11.     return data[n-1];
    12. }

    3、改造递归的方法，因为在递归的过程中产生了大量重复的计算，如果把每一个计算结果存储起来，下次计算的时候可以直接来取，就省了一次运算，这样就可以节省空间和时间

    1. private static int[] data = new int[100];   //借助一个数组作为缓存
    3. private static int betterDiguiFebonache(int n){
    4.     if(n <= 2){
    5.         return 1;
    6.     }
    7.     if(data[n] > 0){
    8.         return data[n];   //先从缓存中获取数据，如果有，就不需要再通过递归获取了
    9.     }
    10.     int re = betterDiguiFebonache(n-1) + betterDiguiFebonache(n-2);
    11.     data[n] = re;   //把已经查到的数据放入缓存中
    12.     return re;
    13. }