Posted on 2008-05-31 17:25
dennis 閱讀(2148)
評論(4) 編輯 收藏 所屬分類:
java
第一個程序：
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest {
public static void main(String[] args) {
TailRecursionTest t = new TailRecursionTest();
for (int i = 0; i < 10000; i++)
t.a(0);
}
public void a(int j) {
j++;
List list = new ArrayList<Integer>(100000);
// 對list進行處理
}
}
沒啥特殊的，僅僅是為了測試，我們將a方法調用10000次，a方法創建一個有100000個元素的list的局部變量。
第二個程序：
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest2 {
public static void main(String[] args) {
TailRecursionTest2 t = new TailRecursionTest2();
t.a(0);
}
public void a(int j) {
System.out.println(j);
j++;
if (j == 10000)
return;
List list = new ArrayList<Integer>(100000);
// 對list進行處理
a(j);
}
}
也沒啥特殊的，就是將循環換成了遞歸，a方法做的事情沒變。兩個都跑一下，程序1順利結束，程序2出問題了，啥問題？如下：
161
162
163
164
165
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.ArrayList.<init>(Unknown Source)
at TailRecursionTest2.a(TailRecursionTest2.java:17)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
我倒，才運行166次了，heap就滿了。問題在哪呢？oh,yep，你肯定想到了，是不是重復創建list這個大集合引起的呢？它不是局部變量嗎？怎么也會溢出？是的，list是局部變量，在a的方法棧里引用著，指向heap上的大對象，更關鍵的問題在于，java是沒有尾遞歸優化的，遞歸方法是不會使用同一個棧幀，每一次遞歸調用，都將壓入新的棧幀，并且這個棧幀上又new了一個list變量，引用著heap上新的一個大集合。隨著棧深度的增加，jvm里維持著一條長長的方法調用軌跡以便你能回來，在方法沒有返回之前，這些list變量一直被各自的棧幀引用著，不能被GC，你說，能不OOM嗎？
也許，你想到了個補救方法來挽救程序2，就是每次在處理完list后，我把它設置為null，不讓棧幀繼續引用著它，咱編寫對gc友好的代碼，這不就行了，試試：
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest2 {
public static void main(String[] args) {
TailRecursionTest2 t = new TailRecursionTest2();
t.a(0);
}
public void a(int j) {
System.out.println(j);
j++;
if (j == 10000)
return;
List list = new ArrayList<Integer>(100000);
// 對list進行處理
list = null; //gc友好
a(j);
}
}
得意洋洋，我跑一下看看，這次跑到4000多次，但是：
......
4289
4290
4291
4292
java.lang.StackOverflowError
at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
沒辦法啊，人家sun的jdk就是不支持尾遞歸優化，很不給你面子的棧溢出了。ibm的jdk據說支持尾遞歸優化，上面這個程序在ibm的jdk上可能可以正常結束，未經測試。
總結：在java里，遞歸最好咱還是別用，老老實實地while、for；就算遞歸了，最好遞歸方法不要new太大的對象，除非你能確定遞歸的深度不是那么大。