1、循环方式获得斐波那契数列某位的数

   public static int fibo(int n){
      int[] nums = new int[n];
      for (int i = 0; i < n; i++) {
         if(i==0 || i==1)
            nums[i]=1;  //第一和第二位填入1
         else
            nums[i]=nums[i-1]+nums[i-2];   //除第一第二位外其余数据等于前两位之和
      }
      return nums[n-1];
   }

耗时最长的方法，同时也是最简单的方法

2、递归方式获取斐波那契数列某位的数

   public static int fibo(int n){
      if(n==1 || n==2)
         return 1;
      else{
         return fibo(n-1)+fibo(n-2);
      }
   }

相比于普通循环的方式来说耗时更短

3、优化递归方式获取斐波那契数列某位的数

   public static int fibo(int n,int[] nums){
      if(n==1 || n==2)
         return 1;
      if(nums[n-1]>0){
         return nums[n-1];
      }
      nums[n-1] = fibo(n-1,nums)+fibo(n-2,nums);
      return nums[n-1];
   }

在斐波那契数列这个案例中，很多数据会被重复计算，影响效率。比如f(3) 被重复计算两次。

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

如果你使用递归的时候不进行优化，会有非常多的子问题被重复计算的。因此，使用递归的时候，必要须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。通过数组将数据保存起来，在读取的时候只需要通过下标读取数组中的数即可，极大的消除了不必要的重复运算。

原文地址：https://blog.csdn.net/tiaowuji/article/details/126413201?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168474995516800188548878%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168474995516800188548878&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-26-126413201-null-null.142^v87^control_2,239^v2^insert_chatgpt&utm_term=java%E4%BC%98%E5%8C%96