關注技術，關注生活

尾遞歸及其轉換?
相當多的程序包含有循環，這些循環運行的時間占了程序總運行時間的很大一部分。這些循環經常要反復更新不止一個變量，而每個變量的更新又經常依賴于其它變量的值。?

如果把迭代看成是尾遞歸函數，那么，就可以把這些變量看成是函數的參數。簡單提醒一下：如果一個調用的返回值被作為調用函數的值立即返回，那么，這個遞歸調用就是尾遞歸；尾遞歸不必記住調用時調用函數的上下文。?

由于這一特點，在尾遞歸函數和循環之間有一個很好的對應關系：可以簡單地把每個遞歸調用看作是一個循環的多次迭代。但因為所有可變的參數值都一次傳給了遞歸調用，所以比起循環來，在尾遞歸中可以更容易地得到更新值。而且，難以使用的?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?上都有適當的性能，您應始終努力把那些最自然地符合尾遞歸模式的代碼按迭代風格編寫。??

但是請注意：就象我們的示例所演示的那樣，以這種方式轉換代碼時很容易引入錯誤，不論是由人工還是由軟件來完成這種轉換。

文章摘自： http://www-900.ibm.com/
作者：Eric?Allen