Go语言视频零基础入门到精通

javalearner

递归是我们很经典的一种算法实现，可以很好的描述一个算法的原理!对于算法的描述、表现和代码结构理解上，递归都是不错的选择! 但是本文想说的是java实现一个递归算法的时候尽量不要用递归实现，而是转换成的非递归实现。       最近在实现一个比较复杂算法的时候，尝试了一下，非递归实现相比递归实现速度上能提升1/3。以下面一个简单的例子来说：(注：为了描述简单，所以这里只用一个简单的例子) 输入参数：N 输出结果: log1+log2+log3+....+logN 两种实现代码如下：

1.     package test;     
   
2.         
   
3.     public class RecursiveTest {     
   
4.         /**   
   
5.          * 递归实现   
   
6.          *     
   
7.          * @param n   
   
8.          * @return   
   
9.          */   
   
10.        public static double recursive(long n) {     
    
11.           if (n == 1) {     
    
12.                return Math.log(1);     
    
13.           } else {     
    
14.               return Math.log(n) + recursive(n - 1);     
    
15.           }     
    
16.       }     
    
17.      
    
18.       /**   
    
19.        * 非递归实现   
    
20.        *     
    
21.        * @param n   
    
22.        * @return   
    
23.        */   
    
24.       public static double directly(long n) {     
    
25.           double result = 0;     
    
26.            for (int i = 1; i <= n; i++) {     
    
27.               result += Math.log(i);     
    
28.           }     
    
29.           return result;     
    
30.       }     
    
31.       
    
32.       public static void main(String[] args) {     
    
33.           int i = 5000000;     
    
34.           long test = System.nanoTime();     
    
35.           long start1 = System.nanoTime();     
    
36.           double r1 = recursive(i);     
    
37.           long end1 = System.nanoTime();     
    
38.           long start2 = System.nanoTime();     
    
39.           double r2 = directly(i);     
    
40.           long end2 = System.nanoTime();     
    
41.       
    
42.           System.out.println("recursive result:" + r1);     
    
43.           System.out.println("recursive time used:" + (end1 - start1));     
    
44.           System.out.println("non-recursive result:" + r2);     
    
45.           System.out.println("non-recursive time used:" + (end2 - start2));     
    
46.       }     
    
47.   }   

复制代码

得到运行结果如下： 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参数)和因为创建栈帧和切换的性能开销，最终大大的影响效率! 所以，如果你想提升你的算法效率，不要使用递归实现是一个基础原则! 另外，递归是我们用来理解算法的一个方法，当用代码来实现的时候基本都可以转换成非递归的代码实现!