如果要用java实现算法，一定慎用递归

 

现象 ：

递归是我们很经典的一种算法实现，可以很好的描述一个算法的原理！对于算法的描述、表现和代码结构理解上，递归都是不错的选择！

但是本文想说的是java实现一个递归算法的时候尽量不要用递归实现，而是转换成的非递归实现。

最近在实现一个比较复杂算法的时候，尝试了一下，非递归实现相比递归实现速度上能提升1/3。

以下面一个简单的例子来说：

(注：为了描述简单，所以这里只用一个简单的例子。这个例子可以用更简单的数学公式来实现，所以请大家不要过分在意。 重点是想说明递归可能带来的一些问题)

输入参数：N

输出结果: log1+log2+log3+....+logN

两种实现代码如下：

 

package test;

public class RecursiveTest {
	/**
	 * 递归实现
	 * 
	 * @param n
	 * @return
	 */
	public static double recursive(long n) {
		if (n == 1) {
			return Math.log(1);
		} else {
			return Math.log(n) + recursive(n - 1);
		}
	}

	/**
	 * 非递归实现
	 * 
	 * @param n
	 * @return
	 */
	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参数)和因为创建栈帧和切换的性能开销，最终大大的影响效率！

 

所以，如果你想提升你的算法效率，不要使用递归实现是一个基础原则！

另外，递归是我们用来理解算法的一个方法，当用代码来实现的时候基本都可以转换成非递归的代码实现！

 

评论

32 楼 clarkhill 2014-11-13  

汉诺塔其实有数学公式能够解决。

31 楼 kingsword 2011-09-04  

稍微给楼主纠个字面上的小不妥“java将为每个线程维护一个堆栈，堆栈里将为每个方法保存一个栈帧，”那个“堆栈”说成是Java栈好些，说成是堆栈，容易给初学者造成迷惑。

30 楼 hdenghui 2011-04-08  

学习，学习…

29 楼 tangqs 2011-04-08  

不过对于递归很深的程序由于很容易引发 栈溢出异常，所以在这样的情况下，用非递归算法更合适一些。

28 楼 tangqs 2011-04-08  

在Java中，JVM对递归调用有优化的，所以在很多情况之下递归调用的效率会比非递归高，lz的递归程序的例子并没有普遍意义，因为这个非递归程序没有用到栈结构，如果你真的要做例子，你可以在试试快速排序的递归和非递归算法。

27 楼 seanla 2011-04-08  

kimmking 写道

cttnbcj 写道

除非疯子才一个一个算logx相加 .......
向楼上所说递归是用来简单化来表达数据处理的思想

要是不用递归试试计算 f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)
不管是用非递归或推数学公式(上面公式已经要计算一元五次方程的解了)，会非常复杂

五次方程没有根式解，
手工计算5个根有点累。
计算机计算起来比较容易。

可以考虑用演化计算，选择一个比较好的算子，很快就能算出最优解

26 楼 optimism_best 2011-04-07  

好贴，递归的用法还不是很清楚，在N很大的情况下递归的性能确实不乐观

25 楼 wolf521hf 2011-04-07  

学习了    

24 楼 sdh5724 2011-04-07  

用递归的时候， 得清楚自己是在干么， 否则就不要用。 就跟用正则一样得道理。  很多东西没有完美。用的时候都得想清楚。

23 楼 beykery 2011-04-07  

也要看什么情况啊楼主，有些算法递归实现确实很清晰，还有些算法把递归写成非递归形式还非常困难。比如alpha beta剪支我就不知道怎么写成非递归。

22 楼 gundumw100 2011-04-07  

个人感觉递归用于for循环次数不定的情况.
for
  for
    for
      ......

21 楼 realvalkyrie 2011-04-07  

用迭代来表示，即满足递归的明了，性能也相对来说可以接受：
结果以参数的形式传递，这样可以省去递归由于要保存栈信息而带来的开销。

20 楼 jackra 2011-04-07  

递归本身针对可扩展性多状况结构的数据有很强大处理能力.
如果要做一些可扩展的组件,递归是不可避免的.
不会递归可耻；滥用递归也可耻；不会正确的使用递归同样可耻。

19 楼 kamhung 2011-04-07  

不是递归本身慢， 是java调用方法慢， 例子1跟例子2的区别在于例子2少调用了方法， 这两个例子都运行几次就会发现两个耗时会越来越接近， 因为java对频繁调用的方法进行优化~

18 楼 Crusader 2011-04-07  

递归是用来简化求解难度的
但如果迭代次数过多的话，会影响性能

17 楼 math_xl 2011-04-07  

递归 代码比较整洁

空间消耗代价

16 楼 schweigen 2011-04-07  

在Sun JDK 下跑，第一次确实差距挺大，再运行第二次的结果（也许可能要多运行几次）：

recursive result:7.212475098340103E7
recursive time used:312802755
non-recursive result:7.212475098340103E7
non-recursive time used:312842609

JDK 对尾递归还是会自己做优化的

15 楼 freish 2011-04-07  

每每看到递归都后怕，StackOverflowError是个心理阴影

14 楼 singleant 2011-04-07  

cttnbcj 写道

除非疯子才一个一个算logx相加 .......
向楼上所说递归是用来简单化来表达数据处理的思想

要是不用递归试试计算 f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)
不管是用非递归或推数学公式(上面公式已经要计算一元五次方程的解了)，会非常复杂

你根本就不理解本帖子要说明什么！ 只是想说明递归的开销！
例子不是最重要的，"除非疯子才一个一个算logx相加 ....... "这个大家都懂得，不要过分去在意这个。

13 楼 kimmking 2011-04-07  

cttnbcj 写道

kimmking 写道

cttnbcj 写道

除非疯子才一个一个算logx相加 .......
向楼上所说递归是用来简单化来表达数据处理的思想

要是不用递归试试计算 f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)
不管是用非递归或推数学公式(上面公式已经要计算一元五次方程的解了)，会非常复杂

五次方程没有根式解，
手工计算5个根有点累。
计算机计算起来比较容易。

你确定无解？只是无代数根式解
五次方程符合Galois群理论，就可以有解。。。。(x-a)(x-b)(x-c)(x-d)(x-e)=0 a,b,c,d,e都不相等，这个五次方，你说有解吗？