如果要用Java實現算法，一定慎用遞歸

現象 ：

遞歸是我們很經典的一種算法實現，可以很好的描述一個算法的原理!對於算法的描述、表現和代碼結構理解上，遞歸都是不錯的選擇!

但是本文想說的是Java實現一個遞歸算法的時候盡量不要用遞歸實現，而是轉換成的非遞歸實現。

最近在實現一個比較復雜算法的時候，嘗試了一下，非遞歸實現相比遞歸實現速度上能提升1/3。

以下面一個簡單的例子來說：(注：為了描述簡單，所以這裡只用一個簡單的例子)

輸入參數：N

輸出結果: log1+log2+log3+....+logN

兩種實現代碼如下：

Java代碼

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參數)和因為創建棧幀和切換的性能開銷，最終大大的影響效率!

所以，如果你想提升你的算法效率，不要使用遞歸實現是一個基礎原則!

另外，遞歸是我們用來理解算法的一個方法，當用代碼來實現的時候基本都可以轉換成非遞歸的代碼實現!