很多算法用尾遞歸方法表示會顯得格外簡明。編譯器會自動把這種方法轉換成循環，以提高程序的性能。但在 Java 語言規范中，並沒有要求一定要作這種轉換，因此，並不是所有的 Java 虛擬機（JVM）都會做這種轉換。這就意味著在 Java 語言中采用尾遞歸方法將導致巨大的內存占用，而這並不是我們期望的結果。Eric Allen 在本文中闡述了動態編譯將會保持語言的語義，而靜態編譯則通常不會。他說明了為什麼這是一個重要問題，並提供了一段代碼來幫助判斷您的即時（JIT）編譯器是否會在保持語言語義的同時做尾遞歸代碼轉換。
尾遞歸及其轉換
相當多的程序包含有循環，這些循環運行的時間占了程序總運行時間的很大一部分。這些循環經常要反復更新不止一個變量，而每個變量的更新又經常依賴於其它變量的值。
如果把迭代看成是 尾遞歸函數，那麼，就可以把這些變量看成是函數的參數。簡單提醒一下：如果一個調用的返回值被作為調用函數的值立即返回，那麼，這個遞歸調用就是尾遞歸；尾遞歸不必記住調用時調用函數的上下文。
由於這一特點，在尾遞歸函數和循環之間有一個很好的對應關系：可以簡單地把每個遞歸調用看作是一個循環的多次迭代。但因為所有可變的參數值都一次傳給了遞歸調用，所以比起循環來，在尾遞歸中可以更容易地得到更新值。而且，難以使用的 break 語句也常常為函數的簡單返回所替代。
但在 Java 編程中，用這種方式表示迭代將導致效率低下，因為大量的遞歸調用有導致堆棧溢出的危險。
解決方案比較簡單：因為尾遞歸函數實際上只是編寫循環的一種更簡單的方式，所以就讓編譯器把它們自動轉換成循環形式。這樣您就同時利用了這兩種形式的優點。
但是，盡管大家都熟知如何把一個尾遞歸函數自動轉換成一個簡單循環，Java 規范卻不要求做這種轉換。不作這種要求的原因大概是：通常在面向對象的語言中，這種轉換不能靜態地進行。相反地，這種從尾遞歸函數到簡單循環的轉換必須由 JIT 編譯器動態地進行。
要理解為什麼會是這樣，考慮下面一個失敗的嘗試：在 Integers 集上，把 Iterator 中的元素相乘。
因為下面的程序中有一個錯誤，所以在運行時會拋出一個異常。但是，就象在本專欄以前的許多文章中已經論證的那樣，一個程序拋出的精確異常（跟很棒的錯誤類型標識符一樣）對於找到錯誤藏在程序的什麼地方並沒有什麼幫助，我們也不想編譯器以這種方式改變程序，以使編譯的結果代碼拋出一個不同的異常。
清單 1. 一個把 Integer 集的 Iterator 中的元素相乘的失敗嘗試
import java.util.Iterator;
public class Example {
public int product(Iterator i) {
return productHelp(i, 0);
}
int productHelp(Iterator i, int accumulator) {
if (i.hasNext()) {
return productHelp(i, accumulator * ((Integer)i.next()).intValue());
}
else {
return accumulator;
}
}
}
注意 product 方法中的錯誤。 product 方法通過把 accumulator 賦值為 0 調用 productHelp 。它的值應為 1。否則，在類 Example 的任何實例上調用 product 都將產生 0 值，不管 Iterator 是什麼值。
假設這個錯誤終於被改正了，但同時，類 Example 的一個子類也被創建了，如清單 2 所示：
清單 2. 試圖捕捉象清單 1 這樣的不正確的調用
import java.util.*;
class Example {
public int product(Iterator i) {
return productHelp(i, 1);
}
int productHelp(Iterator i, int accumulator) {
if (i.hasNext()) {
return productHelp(i, accumulator * ((Integer)i.next()).intValue());
}
else {
return accumulator;
}
}
}
// And, in a separate file:
import java.util.*;
public class Example2 extends Example {
int productHelp(Iterator i, int accumulator) {
if (accumulator < 1) {
throw new RuntimeException("accumulator to productHelp must be >= 1");
}
else {
return super.productHelp(i, accumulator);
}
}
public static void main(String[] args) {
LinkedList l = new LinkedList();
l.add(new Integer(0));
new Example2().product(l.listIterator());
}
}
類 Example2 中的被覆蓋的 productHelp 方法試圖通過當 accumulator 小於“1”時拋出運行時異常來捕捉對 productHelp 的不正確調用。不幸的是，這樣做將引入一個新的錯誤。如果 Iterator 含有任何 0 值的實例，都將使 productHelp 在自身的遞歸調用上崩潰。
現在請注意，在類 Example2 的 main 方法中，創建了 Example2 的一個實例並調用了它的 product 方法。由於傳給這個方法的 Iterator 包含一個 0，因此程序將崩潰。
然而，您可以看到類 Example 的 productHelp 是嚴格尾遞歸的。假設一個靜態編譯器想把這個方法的正文轉換成一個循環，如清單 3 所示：
清單 3. 靜態編譯不會優化尾調用的一個示例
int productHelp(Iterator i, int accumulator) {
while (i.hasNext()) {
accumulator *= ((Integer)i.next()).intValue();
}
return accumulator;
}
於是，最初對 productHelp 的調用，結果成了對超類的方法的調用。超方法將通過簡單地在 iterator 上循環來計算其結果。不會拋出任何異常。
用兩個不同的靜態編譯器來編譯這段代碼，結果是一個會拋出異常，而另一個則不會，想想這是多麼讓人感到困惑。
您的 JIT 會做這種轉換嗎？
因此，如清單 3 中的示例所示，我們不能期望靜態編譯器會在保持語言語義的同時對 Java 代碼執行尾遞歸轉換。相反地，我們必須依靠 JIT 進行的動態編譯。JIT 會不會做這種轉換是取決於 JVM。
要判斷您的 JIT 會否轉換尾遞歸的一個辦法是編譯並運行如下小測試類：
清單 4. 判斷您的 JIT 能否轉換尾遞歸
public class TailRecursionTest {
private static int loop(int i) {
return loop(i);
}
public static void main(String[] args) {
loop(0);
}
}
我們來考慮一下這個類的 loop 方法。這個方法只是盡可能長時間地對自身作遞歸調用。因為它永遠不會返回，也不會以任何方式影響任何外部變量，因此如清單 5 所示替換其代碼正文將保留程序的語義。
清單 5. 一個動態轉換
public class TailRecursionTest {
private static int loop(int i) {
while (true) {
}
}
public static void main(String[] args) {
loop(0);
}
}
而且，事實上這也就是足夠完善的編譯器所做的轉換。
如果您的 JIT 編譯器把尾遞歸調用轉換成迭代，這個程序將無限期地運行下去。它所需的內存很小，而且不會隨時間增加。
另一方面，如果 JIT 不做這種轉換，程序將會很快耗盡堆棧空間並報告一個堆棧溢出錯誤。
我在兩個 Java SDK 上運行這個程序，結果令人驚訝。在 SUN 公司的 Hotspot JVM（版本 1.3 ）上運行時，發現 Hotspot 不執行這種轉換。缺省設置下，在我的機器上運行時，不到一秒鐘堆棧空間就被耗盡了。
另一方面，程序在 IBM 的 JVM（版本 1.3 ）上咕噜噜運行時卻沒有任何問題，這表明 IBM 的 JVM 以這種方式轉換代碼。
總結
記住：我們不能寄希望於我們的代碼會總是運行在會轉換尾遞歸調用的 JVM 上。因此，為了保證您的程序在所有 JVM 上都有適當的性能，您應始終努力把那些最自然地符合尾遞歸模式的代碼按迭代風格編寫。
但是請注意：就象我們的示例所演示的那樣，以這種方式轉換代碼時很容易引入錯誤，不論是由人工還是由軟件來完成這種轉換。
