Java实现“斐波那契数列”的两种方式——数组与优化递归

本文使用了三种方式实现了斐波那契数列——数组、递归、优化递归。

此文重点是对斐波那契数列的实现方式效率的比较及优化。

一、数组实现斐波那契数列

测试代码：

public class ArrayTest {
   public static void main(String[] args) {
      // 开始计时
      long start = System.currentTimeMillis();
      // 斐波那契
      long[] array = new long[50];
      array[0] = 1L;
      array[1] = 1L;
      for (int i = 2; i < array.length; i++) {
         array[i] = array[i-1] + array[i-2];
      }
      System.out.println("第50位斐波那契数列的数字：" + array[49]);
      // 结束计时
      long end = System.currentTimeMillis();
      System.out.println(end - start + " ms");
   }
}

控制台输出结果：

第50位斐波那契数列的数字：12586269025
1 ms

Process finished with exit code 0

通过数组实现仅需要1毫秒。

二、递归实现斐波那契数列

测试代码：

public class RecursionTest {

   public static void main(String[] args) {
      // 开始计时
      long start = System.currentTimeMillis();
      // 斐波那契
      long fibonacci_50 = fibonacci(50);
      System.out.println("第50位斐波那契数列的数字：" + fibonacci_50);
      // 结束计时
      long end = System.currentTimeMillis();
      System.out.println(end - start + " ms");
   }

   public static long fibonacci(int index){
      if(index == 1 || index == 2){
         return 1;
      }
      return fibonacci(index - 1) + fibonacci(index - 2);
   }

}

控制台输出结果：

第50位斐波那契数列的数字：12586269025
44750 ms

Process finished with exit code 0

传统递归方式近45秒。

三、分析与优化

数组的效率为1毫秒，传统递归的效率为45秒。

那么，是什么原因导致数组与传统递归这两种方式效率差距这么大呢？

通过DEBUG跟踪代码，我们发现传统递归每一次获取当前index的时候，都要重新获取之前的index。查找重复的index增加了计算成本，因此降低了效率。

如果你还没有get我的意思… 好比我现在要问你的祖籍。问你，你不知道，那就找你的爸比；问你爸比，你爸比也不知道，那就问你爷爷；问你爷爷，你爷爷也不知道，那就问你曾爷爷；问你曾爷爷，你曾爷爷也…；直到问到你的鼻祖，鼻祖摸了摸胡须想了想，哦，我家搁东北的。

现在知道了你的祖籍，然后要问你爸比的祖籍，你爸比不知道，又来问你爷爷；你爷爷也不知道，再问问你曾爷爷…直到问到了鼻祖，鼻祖摸了摸胡须缓缓说道，刚不是问过了吗，东北的。

知道了爸比的祖籍，现在要问你爷爷的祖籍，你爷爷不知道，就问曾爷爷，曾爷爷不知道，就问太爷爷…直到又问到了鼻祖，鼻祖摸了摸胡须怒怼道，憋问了，问就是东北的。

找到了病因，便可以对症下药。

解决办法： 我们在全局变量中设置一个容器，用于记录已查询过的斐波那契数列。每次计算对应下标的斐波那契数字，先从容器中获取，容器中存在便直接获取，反之则计算出结果存入容器。

四、优化递归实现斐波那契数列

测试代码：

public class OptimizedRecursionTest {

   private static final Map<Integer, Long> FIBONACCI_MAP = new HashMap<>();

   public static void main(String[] args) {
      // 开始计时
      long start = System.currentTimeMillis();
      // 斐波那契
      FIBONACCI_MAP.put(1, 1L);
      FIBONACCI_MAP.put(2, 1L);
      long fibonacci_50 = optimizedFibonacci(50);
      System.out.println("第50位斐波那契数列的数字：" + fibonacci_50);
      // 结束计时
      long end = System.currentTimeMillis();
      System.out.println(end - start + " ms");
   }

   public static long optimizedFibonacci(int index){
      if (FIBONACCI_MAP.containsKey(index)){
         return FIBONACCI_MAP.get(index);
      }else {
         FIBONACCI_MAP.put(index, optimizedFibonacci(index - 1) + optimizedFibonacci(index - 2));
      }
      return optimizedFibonacci(index - 1) + optimizedFibonacci(index - 2);
   }

}

控制台输出结果：

第50位斐波那契数列的数字：12586269025
2 ms

Process finished with exit code 0

优化之后的递归仅需要2毫秒。鼻祖再也不用担心别人问你祖籍了，因为每次的结果，都已经被记录下来。下次再问你祖籍的时候，如果容器里有，直接拿走不谢；如果没有，每个祖宗最多只问一次！

五、总结

虽然经过优化之后的递归效率依然不及数组，但2毫秒相较于44750毫秒，已然是神乎其技。

这种优化递归的思想，使用场景不局限于斐波那契，若能融会贯通，在开发业务流程中使用递归的时候，大可不必再担心效率问题。

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