Posted on 2008-05-31 17:25
dennis 閱讀(2156)
評論(4) 編輯 收藏 所屬分類:
java
第一個(gè)程序：
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進(jìn)行處理
}
}
沒啥特殊的，僅僅是為了測試，我們將a方法調(diào)用10000次，a方法創(chuàng)建一個(gè)有100000個(gè)元素的list的局部變量。
第二個(gè)程序：
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進(jìn)行處理
a(j);
}
}
也沒啥特殊的，就是將循環(huán)換成了遞歸，a方法做的事情沒變。兩個(gè)都跑一下，程序1順利結(jié)束，程序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)
我倒，才運(yùn)行166次了，heap就滿了。問題在哪呢？oh,yep，你肯定想到了，是不是重復(fù)創(chuàng)建list這個(gè)大集合引起的呢？它不是局部變量嗎？怎么也會(huì)溢出？是的，list是局部變量，在a的方法棧里引用著，指向heap上的大對象，更關(guān)鍵的問題在于，java是沒有尾遞歸優(yōu)化的，遞歸方法是不會(huì)使用同一個(gè)棧幀，每一次遞歸調(diào)用，都將壓入新的棧幀，并且這個(gè)棧幀上又new了一個(gè)list變量，引用著heap上新的一個(gè)大集合。隨著棧深度的增加，jvm里維持著一條長長的方法調(diào)用軌跡以便你能回來，在方法沒有返回之前，這些list變量一直被各自的棧幀引用著，不能被GC，你說，能不OOM嗎？
也許，你想到了個(gè)補(bǔ)救方法來挽救程序2，就是每次在處理完list后，我把它設(shè)置為null，不讓棧幀繼續(xù)引用著它，咱編寫對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進(jìn)行處理
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就是不支持尾遞歸優(yōu)化，很不給你面子的棧溢出了。ibm的jdk據(jù)說支持尾遞歸優(yōu)化，上面這個(gè)程序在ibm的jdk上可能可以正常結(jié)束，未經(jīng)測試。
總結(jié)：在java里，遞歸最好咱還是別用，老老實(shí)實(shí)地while、for；就算遞歸了，最好遞歸方法不要new太大的對象，除非你能確定遞歸的深度不是那么大。