欢迎点击「算法与编程之美」↑关注我们!
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。
问题描述
在本周的 java 框架学习中,在讲述 aop 的时候,利用测试递归和迭代两种方式计算斐波拉契数列的效率进行了讲解,由于 java 基础知识不牢固,所以又回顾了递归这种方法。以下是对这种方式的学习见解。
具体内容
一.斐波拉契数列的概念:
指的是这样一个数列: 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* )
二.递归算法
什么是递归?通俗点来讲就是“我自己调用自己”。利用一个简单的例子来讲解:
public class Test {
public static void main(String[] args) {
a();
}
static void a(){
System.out.println(" 禁止套娃 ");
a();
}
}
来看看有什么问题
很明显,这个程序自己给跑死了。
这个程序就这样无休止的调用 a 方法。所以完整的递归,还需要一个什么时候停止的条件,称之为递归头。
接下来完善一下上面的代码,添加递归头。
public class Test {
public static void main(String[] args) {
a();
}
static int i;
static void a(){
System.out.println(" 禁止套娃 ");
i++;
if (i<5){
a();
}else {
return;
}
}
}
现在已经了解了递归算法,接下来就正式来计算斐波拉契数列。
public long calFibonacciByRecursive(long n) {
if (n == 1) {
return 1;
}
else if (n==2){
return 1;
}
return calFibonacciByRecursive(n-2)+calFibonacciByRecursive(n-1);
}
三.迭代算法代码(用作对比)
这是迭代循环的方法:
public long calFibonacciByLoop(long n) {
long n1 = 1;
long n2 = 1;
long n3 = 0;
for (int i = 0; i <n ; i++) {
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
结语
下面的效果是对两种方式的效率统计。通常来讲,能用递归的情况,都可以利用循环的方式来解决,但是应该尽量避免使用递归的方式来解决问题。虽然代码简单,但是这样的程序对占用大量内存,并不利于开发,要尽可能的提高程序效率。
END
编 辑 | 王楠岚
责 编 | 王 宇
温馨提示: 点击页面右下角 “写留言”发表评论,期待您的参与!期待您的转发!
原文
http://mp.weixin.qq.com/s?__biz=MzI5MTQ5NDY1MA==&mid=2247489512&idx=3&sn=fed9ac97acdbe801e6252dd9794f56fc
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java|递归算法计算