尾遞歸轉(zhuǎn)換能加快應(yīng)用程序的速度，但不是所有的 JVM 都會(huì)做這種轉(zhuǎn)換

　　很多算法用尾遞歸方法表示會(huì)顯得格外簡(jiǎn)明。編譯器會(huì)自動(dòng)把這種方法轉(zhuǎn)換成循環(huán)，以提高程序的性能。但在 Java 語(yǔ)言規(guī)范中，并沒有要求一定要作這種轉(zhuǎn)換，因此，并不是所有的 Java 虛擬機(jī)（JVM）都會(huì)做這種轉(zhuǎn)換。這就意味著在 Java 語(yǔ)言中采用尾遞歸表示可能導(dǎo)致巨大的內(nèi)存占用，而這并不是我們期望的結(jié)果。Eric Allen 在本文中闡述了動(dòng)態(tài)編譯將會(huì)保持語(yǔ)言的語(yǔ)義，而靜態(tài)編譯則通常不會(huì)。他說(shuō)明了為什么這是一個(gè)重要問(wèn)題，并提供了一段代碼來(lái)幫助判斷您的即時(shí)（JIT）編譯器是否會(huì)在保持語(yǔ)言語(yǔ)義的同時(shí)做尾遞歸代碼轉(zhuǎn)換。

　　尾遞歸及其轉(zhuǎn)換

　　相當(dāng)多的程序包含有循環(huán)，這些循環(huán)運(yùn)行的時(shí)間占了程序總運(yùn)行時(shí)間的很大一部分。這些循環(huán)經(jīng)常要反復(fù)更新不止一個(gè)變量，而每個(gè)變量的更新又經(jīng)常依賴于其它變量的值。

　　如果把迭代看成是尾遞歸函數(shù)，那么，就可以把這些變量看成是函數(shù)的參數(shù)。簡(jiǎn)單提醒一下：如果一個(gè)調(diào)用的返回值被作為調(diào)用函數(shù)的值立即返回，那么，這個(gè)遞歸調(diào)用就是尾遞歸；尾遞歸不必記住調(diào)用時(shí)調(diào)用函數(shù)的上下文。

　　由于這一特點(diǎn)，在尾遞歸函數(shù)和循環(huán)之間有一個(gè)很好的對(duì)應(yīng)關(guān)系：可以簡(jiǎn)單地把每個(gè)遞歸調(diào)用看作是一個(gè)循環(huán)的多次迭代。但因?yàn)樗�有可變的參�?shù)值都一次傳給了遞歸調(diào)用，所以比起循環(huán)來(lái)，在尾遞歸中可以更容易地得到更新值。而且，難以使用的 break 語(yǔ)句也常常為函數(shù)的簡(jiǎn)單返回所替代。

　　但在 Java 編程中，用這種方式表示迭代將導(dǎo)致效率低下，因?yàn)榇罅康倪f歸調(diào)用有導(dǎo)致堆棧溢出的危險(xiǎn)。

　　解決方案比較簡(jiǎn)單：因?yàn)槲策f歸函數(shù)實(shí)際上只是編寫循環(huán)的一種更簡(jiǎn)單的方式，所以就讓編譯器把它們自動(dòng)轉(zhuǎn)換成循環(huán)形式。這樣您就同時(shí)利用了這兩種形式的優(yōu)點(diǎn)。

　　但是，盡管大家都熟知如何把一個(gè)尾遞歸函數(shù)自動(dòng)轉(zhuǎn)換成一個(gè)簡(jiǎn)單循環(huán)，Java 規(guī)范卻不要求做這種轉(zhuǎn)換。不作這種要求的原因大概是：通常在面向?qū)ο蟮恼Z(yǔ)言中，這種轉(zhuǎn)換不能靜態(tài)地進(jìn)行。相反地，這種從尾遞歸函數(shù)到簡(jiǎn)單循環(huán)的轉(zhuǎn)換必須由 JIT 編譯器動(dòng)態(tài)地進(jìn)行。

　　要理解為什么會(huì)是這樣，考慮下面一個(gè)失敗的嘗試：在 Integers 集上，把 Iterator 中的元素相乘。

　　因?yàn)橄旅娴某绦蛑杏幸粋�(gè)錯(cuò)誤，所以在運(yùn)行時(shí)會(huì)拋出一個(gè)異常。但是，就象在本專欄以前的許多文章中已經(jīng)論證的那樣，一個(gè)程序拋出的精確異常（跟很棒的錯(cuò)誤類型標(biāo)識(shí)符一樣）對(duì)于找到錯(cuò)誤藏在程序的什么地方并沒有什么幫助，我們也不想編譯器以這種方式改變程序，以使編譯的結(jié)果代碼拋出一個(gè)不同的異常。

　　清單 1. 一個(gè)把 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 方法中的錯(cuò)誤。product 方法通過(guò)把 accumulator 賦值為 0 調(diào)用 productHelp。它的值應(yīng)為 1。否則，在類 Example 的任何實(shí)例上調(diào)用 product 都將產(chǎn)生 0 值，不管 Iterator 是什么值。

　　假設(shè)這個(gè)錯(cuò)誤終于被改正了，但同時(shí)，類 Example 的一個(gè)子類也被創(chuàng)建了，如清單 2 所示：

　　清單 2. 試圖捕捉象清單 1 這樣的不正確的調(diào)用

　　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 方法試圖通過(guò)當(dāng) accumulator 小于“1”時(shí)拋出運(yùn)行時(shí)異常來(lái)捕捉對(duì) productHelp 的不正確調(diào)用。不幸的是，這樣做將引入一個(gè)新的錯(cuò)誤。如果 Iterator 含有任何 0 值的實(shí)例，都將使 productHelp 在自身的遞歸調(diào)用上崩潰。