【Java】斐波那契数列（Fibonacci Sequence、兔子数列）的3种计算方法（递归实现、递归值缓存实现、循环实现、尾递归实现）...-白红宇

【Java】斐波那契数列（Fibonacci Sequence、兔子数列）的3种计算方法（递归实现、递归值缓存实现、循环实现、尾递归实现）...

阅读量：6224 次

发布时间：2019-06-21

本文共 9789 字，大约阅读时间需要 32 分钟。

斐波那契数列：0、1、1、2、3、5、8、13…………

他的规律是，第一项是0，第二项是1，第三项开始（含第三项）等于前两项之和。

> 递归实现

看到这个规则，第一个想起当然是递归算法去实现了，于是写了以下一段：

public class RecursionForFibonacciSequence {    public static void main(String[] args) {        System.out.println(recursion(10));    }        public static double recursion(double i) {        if (i == 0) {            printResult(i, 0);            return 0;        }        if (i == 1) {            printResult(i, 1);            return 1;        }                double result = recursion(i - 1) + recursion(i - 2);        printResult(i, result);                return result;    }        /**     * 打印结果     */    public static void printResult(double i, double result) {        System.out.println(i + " -> " + result);    }    }

它能正常运行，比如计算第10项的结果为55。

但是，计算数字大点的数据，则很慢很慢，因为重复计算太多了。

日志：

1.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.06.0 -> 8.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.07.0 -> 13.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.06.0 -> 8.08.0 -> 21.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.06.0 -> 8.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.07.0 -> 13.09.0 -> 34.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.06.0 -> 8.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.07.0 -> 13.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.05.0 -> 5.01.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.01.0 -> 1.00.0 -> 0.02.0 -> 1.04.0 -> 3.06.0 -> 8.08.0 -> 21.010.0 -> 55.055.0

View Code

> 递归值缓存实现

用最直观的方式优化，既然重复计算太多了，而重复计算的结果都是一样的，那么我们就将重复计算的结果集缓存起来吧。

因为上例的递归效率低，不能执行太多的项数，所以只执行到10，而下面这个写法的效率大为提高，所以我们执行到100看看。

import java.util.HashMap;import java.util.Map;public class CacheForFibonacciSequence {    public static void main(String[] args) {        System.out.println(recursion(100));    }        // 缓存计算结果集    public static Map
     
       map = new HashMap
      
       ();        public static double recursion(double i) {        if (i == 0) {            printResult(i, 0);            return 0;        }        if (i == 1) {            printResult(i, 1);            return 1;        }                if (map.containsKey(i)) {            return map.get(i);        }                double result = recursion(i - 1) + recursion(i - 2);        printResult(i, result);        map.put(i, result);                return result;    }        /**     * 打印结果     */    public static void printResult(double i, double result) {        System.out.println(i + " -> " + result);    }    }

日志：

1.0 -> 1.00.0 -> 0.02.0 -> 1.01.0 -> 1.03.0 -> 2.04.0 -> 3.05.0 -> 5.06.0 -> 8.07.0 -> 13.08.0 -> 21.09.0 -> 34.010.0 -> 55.011.0 -> 89.012.0 -> 144.013.0 -> 233.014.0 -> 377.015.0 -> 610.016.0 -> 987.017.0 -> 1597.018.0 -> 2584.019.0 -> 4181.020.0 -> 6765.021.0 -> 10946.022.0 -> 17711.023.0 -> 28657.024.0 -> 46368.025.0 -> 75025.026.0 -> 121393.027.0 -> 196418.028.0 -> 317811.029.0 -> 514229.030.0 -> 832040.031.0 -> 1346269.032.0 -> 2178309.033.0 -> 3524578.034.0 -> 5702887.035.0 -> 9227465.036.0 -> 1.4930352E737.0 -> 2.4157817E738.0 -> 3.9088169E739.0 -> 6.3245986E740.0 -> 1.02334155E841.0 -> 1.65580141E842.0 -> 2.67914296E843.0 -> 4.33494437E844.0 -> 7.01408733E845.0 -> 1.13490317E946.0 -> 1.836311903E947.0 -> 2.971215073E948.0 -> 4.807526976E949.0 -> 7.778742049E950.0 -> 1.2586269025E1051.0 -> 2.0365011074E1052.0 -> 3.2951280099E1053.0 -> 5.3316291173E1054.0 -> 8.6267571272E1055.0 -> 1.39583862445E1156.0 -> 2.25851433717E1157.0 -> 3.65435296162E1158.0 -> 5.91286729879E1159.0 -> 9.56722026041E1160.0 -> 1.54800875592E1261.0 -> 2.504730781961E1262.0 -> 4.052739537881E1263.0 -> 6.557470319842E1264.0 -> 1.0610209857723E1365.0 -> 1.7167680177565E1366.0 -> 2.7777890035288E1367.0 -> 4.4945570212853E1368.0 -> 7.2723460248141E1369.0 -> 1.17669030460994E1470.0 -> 1.90392490709135E1471.0 -> 3.08061521170129E1472.0 -> 4.98454011879264E1473.0 -> 8.06515533049393E1474.0 -> 1.304969544928657E1575.0 -> 2.11148507797805E1576.0 -> 3.416454622906707E1577.0 -> 5.527939700884757E1578.0 -> 8.944394323791464E1579.0 -> 1.447233402467622E1680.0 -> 2.3416728348467684E1681.0 -> 3.7889062373143904E1682.0 -> 6.1305790721611584E1683.0 -> 9.9194853094755488E1684.0 -> 1.60500643816367072E1785.0 -> 2.5969549691112256E1786.0 -> 4.2019614072748966E1787.0 -> 6.7989163763861222E1788.0 -> 1.10008777836610189E1889.0 -> 1.77997941600471398E1890.0 -> 2.880067194370816E1891.0 -> 4.6600466103755305E1892.0 -> 7.5401138047463465E1893.0 -> 1.2200160415121877E1994.0 -> 1.9740274219868226E1995.0 -> 3.19404346349901E1996.0 -> 5.168070885485833E1997.0 -> 8.362114348984843E1998.0 -> 1.3530185234470676E2099.0 -> 2.189229958345552E20100.0 -> 3.54224848179262E203.54224848179262E20

View Code

> 循环方式

还有我们也可以用循环的方式，只用两个变量缓存前两项的值：

public class ForeachForFibonacciSequence {    public static void main(String[] args) {        System.out.println(foreach(100));    }        public static double foreach(double i) {        if (i <= 0d) {            return 0d;        }                if (i == 1d) {            return 1d;        }                double temp1 = 0d;        double temp2 = 1d;        double tempSum = 0;        for (double d = 2; d <= i; d++) {            tempSum = temp1 + temp2;            printResult(d, tempSum);                        temp1 = temp2;            temp2 = tempSum;        }                return tempSum;    }        /**     * 打印结果     */    public static void printResult(double i, double result) {        System.out.println(i + " -> " + result);    }    }

日志：

2.0 -> 1.03.0 -> 2.04.0 -> 3.05.0 -> 5.06.0 -> 8.07.0 -> 13.08.0 -> 21.09.0 -> 34.010.0 -> 55.011.0 -> 89.012.0 -> 144.013.0 -> 233.014.0 -> 377.015.0 -> 610.016.0 -> 987.017.0 -> 1597.018.0 -> 2584.019.0 -> 4181.020.0 -> 6765.021.0 -> 10946.022.0 -> 17711.023.0 -> 28657.024.0 -> 46368.025.0 -> 75025.026.0 -> 121393.027.0 -> 196418.028.0 -> 317811.029.0 -> 514229.030.0 -> 832040.031.0 -> 1346269.032.0 -> 2178309.033.0 -> 3524578.034.0 -> 5702887.035.0 -> 9227465.036.0 -> 1.4930352E737.0 -> 2.4157817E738.0 -> 3.9088169E739.0 -> 6.3245986E740.0 -> 1.02334155E841.0 -> 1.65580141E842.0 -> 2.67914296E843.0 -> 4.33494437E844.0 -> 7.01408733E845.0 -> 1.13490317E946.0 -> 1.836311903E947.0 -> 2.971215073E948.0 -> 4.807526976E949.0 -> 7.778742049E950.0 -> 1.2586269025E1051.0 -> 2.0365011074E1052.0 -> 3.2951280099E1053.0 -> 5.3316291173E1054.0 -> 8.6267571272E1055.0 -> 1.39583862445E1156.0 -> 2.25851433717E1157.0 -> 3.65435296162E1158.0 -> 5.91286729879E1159.0 -> 9.56722026041E1160.0 -> 1.54800875592E1261.0 -> 2.504730781961E1262.0 -> 4.052739537881E1263.0 -> 6.557470319842E1264.0 -> 1.0610209857723E1365.0 -> 1.7167680177565E1366.0 -> 2.7777890035288E1367.0 -> 4.4945570212853E1368.0 -> 7.2723460248141E1369.0 -> 1.17669030460994E1470.0 -> 1.90392490709135E1471.0 -> 3.08061521170129E1472.0 -> 4.98454011879264E1473.0 -> 8.06515533049393E1474.0 -> 1.304969544928657E1575.0 -> 2.11148507797805E1576.0 -> 3.416454622906707E1577.0 -> 5.527939700884757E1578.0 -> 8.944394323791464E1579.0 -> 1.447233402467622E1680.0 -> 2.3416728348467684E1681.0 -> 3.7889062373143904E1682.0 -> 6.1305790721611584E1683.0 -> 9.9194853094755488E1684.0 -> 1.60500643816367072E1785.0 -> 2.5969549691112256E1786.0 -> 4.2019614072748966E1787.0 -> 6.7989163763861222E1788.0 -> 1.10008777836610189E1889.0 -> 1.77997941600471398E1890.0 -> 2.880067194370816E1891.0 -> 4.6600466103755305E1892.0 -> 7.5401138047463465E1893.0 -> 1.2200160415121877E1994.0 -> 1.9740274219868226E1995.0 -> 3.19404346349901E1996.0 -> 5.168070885485833E1997.0 -> 8.362114348984843E1998.0 -> 1.3530185234470676E2099.0 -> 2.189229958345552E20100.0 -> 3.54224848179262E203.54224848179262E20

View Code

> 尾递归方式

从回复的网友“Mr_listening”的博文中了解到，还可以用尾递归的方式实现，看以下代码：

public class RecursionTailForFibonacciSequence {    public static void main(String[] args) {        System.out.println(recursionTail(10, 1, 1));    }        public static double recursionTail(int i, double temp1, double temp2) {        if (i < 2) {            return temp1;        }                double result = recursionTail(i - 1, temp2, temp1 + temp2);        printResult(i - 1, temp2, temp1 + temp2, result);        return result;    }        /**     * 打印结果     */    public static void printResult(double i, double temp1, double temp2, double result) {        System.out.println("recursionTail(" + i + ", " + temp1 + ", " + temp2 + ") -> " + result);    }    }

日志：

recursionTail(1.0, 55.0, 89.0) -> 55.0recursionTail(2.0, 34.0, 55.0) -> 55.0recursionTail(3.0, 21.0, 34.0) -> 55.0recursionTail(4.0, 13.0, 21.0) -> 55.0recursionTail(5.0, 8.0, 13.0) -> 55.0recursionTail(6.0, 5.0, 8.0) -> 55.0recursionTail(7.0, 3.0, 5.0) -> 55.0recursionTail(8.0, 2.0, 3.0) -> 55.0recursionTail(9.0, 1.0, 2.0) -> 55.055.0

View Code

转载地址：http://zvyna.baihongyu.com/

你可能感兴趣的文章

Spring Cloud Alibaba迁移指南（二）：零代码替换 Eureka