如果要用Java實現(xiàn)算法，一定慎用遞歸
現(xiàn)象 ：
遞歸是我們很經(jīng)典的一種算法實現(xiàn)，可以很好的描述一個算法的原理!對于算法的描述、表現(xiàn)和代碼結(jié)構(gòu)理解上，遞歸都是不錯的選擇!
但是本文想說的是java實現(xiàn)一個遞歸算法的時候盡量不要用遞歸實現(xiàn)，而是轉(zhuǎn)換成的非遞歸實現(xiàn)。
最近在實現(xiàn)一個比較復(fù)雜算法的時候，嘗試了一下，非遞歸實現(xiàn)相比遞歸實現(xiàn)速度上能提升1/3。
以下面一個簡單的例子來說：(注：為了描述簡單，所以這里只用一個簡單的例子)
輸入?yún)?shù)：N
輸出結(jié)果: log1+log2+log3+....+logN
兩種實現(xiàn)代碼如下：
Java代碼
- package test;
- public class RecursiveTest {
- /**
- * 遞歸實現(xiàn)
- *
- * @param n
- * @return
- */
- public static double recursive(long n) {
- if (n == 1) {
- return Math.log(1);
- } else {
- return Math.log(n) + recursive(n - 1);
- }
- }
- /**
- * 非遞歸實現(xiàn)
- *
- * @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));
- }
- }
得到運行結(jié)果如下：
- recursive result:7.212475098340103E7
- recursive time used:539457109
- non-recursive result:7.212475098340103E7
- non-recursive time used:282479757
可以看出遞歸的運行時間是非遞歸運行時間將近2倍。
(注:以上代碼還是在-Xss200m的參數(shù)下運行的，如果棧空間不足，直接不能運行)
原因簡單分析：
上圖是java線程棧的結(jié)構(gòu)。java將為每個線程維護一個堆棧，堆棧里將為每個方法保存一個棧幀，棧幀代表了一個方法的運行狀態(tài)。 也就是我們常說的方法棧。***一個為當(dāng)前運行的棧幀。
那么每一次方法調(diào)用會涉及：
1.為新調(diào)用方法的生成一個棧幀
2.保存當(dāng)前方法的棧幀狀態(tài)
3.棧幀上下文切換，切換到***的方法棧幀。
遞歸實現(xiàn)將導(dǎo)致在棧內(nèi)存的消耗(往往需要調(diào)整Xss參數(shù))和因為創(chuàng)建棧幀和切換的性能開銷，最終大大的影響效率!
所以，如果你想提升你的算法效率，不要使用遞歸實現(xiàn)是一個基礎(chǔ)原則!
另外，遞歸是我們用來理解算法的一個方法，當(dāng)用代碼來實現(xiàn)的時候基本都可以轉(zhuǎn)換成非遞歸的代碼實現(xiàn)!
【編輯推薦】
