现象 :
递归是我们很经典的一种算法实现,可以很好的描述一个算法的原理!对于算法的描述、表现和代码结构理解上,递归都是不错的选择!
但是本文想说的是java实现一个递归算法的时候尽量不要用递归实现,而是转换成的非递归实现 。
最近在实现一个比较复杂算法的时候,尝试了一下,非递归实现相比递归实现速度上能提升1/3 。
以下面一个简单的例子来说:(注:为了描述简单,所以这里只用一个简单的例子)
输入参数:N
输出结果: log1+log2+log3+....+logN
两种实现代码如下:
Java代码
- package test;
-
-
public class RecursiveTest {
-
-
-
-
-
-
-
public static double recursive(long n) {
-
if (n == 1) {
-
return Math.log(1);
-
} else {
-
return Math.log(n) + recursive(n - 1);
- }
- }
-
-
-
-
-
-
-
-
public static double directly(long n) {
-
double result = 0;
-
for (int i = 1; i <= n; i++) {
- result += Math.log(i);
- }
-
return result;
- }
-
-
public static void main(String[] args) {
-
int i = 5000000;
-
long test = System.nanoTime();
-
long start1 = System.nanoTime();
-
double r1 = recursive(i);
-
long end1 = System.nanoTime();
-
long start2 = System.nanoTime();
-
double r2 = directly(i);
-
long end2 = System.nanoTime();
-
-
System.out.println("recursive result:" + r1);
-
System.out.println("recursive time used:" + (end1 - start1));
-
System.out.println("non-recursive result:" + r2);
-
System.out.println("non-recursive time used:" + (end2 - start2));
- }
- }
得到运行结果如下:
- recursive result:7.212475098340103E7
- recursive time used:539457109
- non-recursive result:7.212475098340103E7
- non-recursive time used:282479757
可以看出递归的运行时间是非递归运行时间将近2倍 。
(注:以上代码还是在-Xss200m的参数下运行的,如果栈空间不足,直接不能运行)
原因简单分析:
上图是java线程栈的结构 。java将为每个线程维护一个堆栈,堆栈里将为每个方法保存一个栈帧,栈帧代表了一个方法的运行状态 。 也就是我们常说的方法栈 。最后一个为当前运行的栈帧 。
那么每一次方法调用会涉及:
1.为新调用方法的生成一个栈帧
2.保存当前方法的栈帧状态
3.栈帧上下文切换,切换到最新的方法栈帧 。
递归实现将导致在栈内存的消耗(往往需要调整Xss参数)和因为创建栈帧和切换的性能开销,最终大大的影响效率!
所以,如果你想提升你的算法效率,不要使用递归实现是一个基础原则!
另外,递归是我们用来理解算法的一个方法,当用代码来实现的时候基本都可以转换成非递归的代码实现!
分享到:
相关推荐
java递归算法,java递归算法,java递归算法
用java实现的经典递归算法.doc
java 用递归实现字符串反转 java 用递归实现字符串反转
Java递归算法构造JSON树形结构,Java递归算法构造JSON树形结构Java递归算法构造JSON树形结构
用Java实现递归算法,有人把递归比做成用字典查找一个词语的意思
快速选择非递归与递归算法实现
java实现的经典递归算法三例 十分的经典,可以学习一下
java编写的递归算法的经典事例。 代码很短,没有点基础理解起来还真有点难度。很有挑战性。 不是我写的。这里只是分享一下。 功能是实现全排列。
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
JAVA递归实现全排列算法,含实现源代码,如a、b、c、d的全排列为: abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc
Java二分查找递归算法
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
Java实现用递归算法和非递归算法求解斐波那契数列问题.docx
本文对经典的堆排序非递归算法进行了详细的分析,并用JAVA实现。用过该问题的JAVA实现,可使学习者清晰的观测到解决该问题的全过程。
一个用JAVA编写的扫雷程序,原创! 可以输入界面的行列数和雷数,此程序的精髓在打开一个不是雷而且周围没有雷的格子时,用到了递归的思想。
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
快速排序算法设计与分析总结 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现 实现树与...
Java递归算法
java 数据结构 递归 八皇后 完美递归 java 数据结构 递归 八皇后 完美递归