News:三分天注定,七分靠打拼,爱拼才会赢!致力打造专业IT博客。如果你对本博客有任何意见或建议请联系作者,邮箱:blog@caokuan.cn

斐波那契序列递归实现

逝水无痕 248 0 条

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。(摘自百度百科)

斐波那契.jpg

下面将以 Java 代码的形式展示如何使用递归方式实现计算斐波那契序列某一位的值。

普通递归方式

/**
 * 斐波那契序列递归算法
 * 
 * @param x  待计算的位值
 * @return
 */
private static long fbnq(int x) {
    if (x == 0) {
        return 0;
    } else if (x == 1) {
        return 1;
    } else {
        return fbnq(x - 1) + fbnq(x - 2);
    }
}

使用缓存方式实现递归

/**
 * 缓存连续计算的斐波那契序列值
 */
private static Map<Integer, Long> cacheMap = new HashMap<>();

/**
 * 斐波那契序列递归算法(使用缓存计算)
 * 
 * @param x  待计算的位值
 * @return
 */
private static long fbnqWithCache(int x) {
    if (cacheMap.containsKey(x)) {
        return cacheMap.get(x);
    }
    if (x == 0) {
        return 0;
    } else if (x == 1) {
        return 1;
    } else {
        long r = fbnqWithCache(x - 1) + fbnqWithCache(x - 2);
        cacheMap.put(x, r);
        return r;
    }
}

说明

以上两种方式都可以计算出想要的结果值,但是实现效率上差距巨大。下面以实际的代码展示两种方式计算第50位的值所用的时间。

不使用缓存方式

long a = System.nanoTime();
long value = fbnq(50);
System.out.println("第50位序列值为:" + value);
System.out.println("不使用缓存时时间为:" + (System.nanoTime() - a) + " 纳秒");

输出结果为:

第50位序列值为:12586269025
不使用缓存时计算时间为:58767583039 纳秒

使用缓存方式

long a = System.nanoTime();
long value = fbnqWithCache(50);
System.out.println("第50位序列值为:" + value);
System.out.println("使用缓存时计算时间为:" + (System.nanoTime() - a) + " 纳秒");

输出结果为:

第50位序列值为:12586269025
使用缓存时计算时间为:592958 纳秒

对比两次计算的时间发现使用缓存时用时仅不到 0.6 毫秒,而不使用缓存时用时近 59 秒,差距非常的大。所以在以后需要计算斐波那契序列值时尽量使用缓存的方式计算,虽然占用了一些额外内存,但是效率的提升是巨大的。

与本文相关的文章

发表我的评论
icon_mrgreen.gificon_neutral.gificon_twisted.gificon_arrow.gificon_eek.gificon_smile.gificon_confused.gificon_cool.gificon_evil.gificon_biggrin.gificon_idea.gificon_redface.gificon_razz.gificon_rolleyes.gificon_wink.gificon_cry.gificon_surprised.gificon_lol.gificon_mad.gificon_sad.gificon_exclaim.gificon_question.gif

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址