现象 ：
递归是我们很经典的一种算法实现，可以很好的描述一个算法的原理！对于算法的描述、表现和代码结构理解上，递归都是不错的选择！
但是本文想说的是java实现一个递归算法的时候尽量不要用递归实现，而是转换成的非递归实现。
最近在实现一个比较复杂算法的时候，尝试了一下，非递归实现相比递归实现速度上能提升1/3。
以下面一个简单的例子来说：（注：为了描述简单，所以这里只用一个简单的例子）
输入参数：N
输出结果：log1+log2+log3+….+logN
两种实现代码如下：
Java代码
packagetest; publicclassRecursiveTest{ /***递归实现**@paramn*@return*/ publicstaticdoublerecursive(longn){ if(n==1){ returnMath.log(1); }else{ returnMath.log(n)+recursive(n-1); } } /***非递归实现**@paramn*@return*/ publicstaticdoubledirectly(longn){ doubleresult=0; for(inti=1;i<=n;i++){ result+=Math.log(i); } returnresult; } publicstaticvoidmain(String[]args){ inti=5000000; longtest=System.nanoTime(); longstart1=System.nanoTime(); doubler1=recursive(i); longend1=System.nanoTime(); longstart2=System.nanoTime(); doubler2=directly(i); longend2=System.nanoTime(); System.out.println(“recursiveresult:”+r1); System.out.println(“recursivetimeused:”+(end1-start1)); System.out.println(“non-recursiveresult:”+r2); System.out.println(“non-recursivetimeused:”+(end2-start2)); } }
得到运行结果如下：
recursiveresult:7.212475098340103E7 recursivetimeused:539457109 non-recursiveresult:7.212475098340103E7 non-recursivetimeused:282479757
可以看出递归的运行时间是非递归运行时间将近2倍。
（注：以上代码还是在-Xss200m的参数下运行的，如果栈空间不足，直接不能运行）
原因简单分析：
上图是java线程栈的结构。java将为每个线程维护一个堆栈，堆栈里将为每个方法保存一个栈帧，栈帧代表了一个方法的运行状态。 也就是我们常说的方法栈。最后一个为当前运行的栈帧。
那么每一次方法调用会涉及：
1. 为新调用方法的生成一个栈帧
2. 保存当前方法的栈帧状态
3. 栈帧上下文切换，切换到最新的方法栈帧。
递归实现将导致在栈内存的消耗（往往需要调整Xss参数）和因为创建栈帧和切换的性能开销，最终大大的影响效率！
所以，如果你想提升你的算法效率，不要使用递归实现是一个基础原则！
另外，递归是我们用来理解算法的一个方法，当用代码来实现的时候基本都可以转换成非递归的代码实现！
黄色蓝色或者砖红色，犹如童话世界。
