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