關(guān)注技術(shù)，關(guān)注生活

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

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

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

但在?Java?編程中，用這種方式表示迭代將導(dǎo)致效率低下，因為大量的遞歸調(diào)用有導(dǎo)致堆棧溢出的危險。??

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

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

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

因為下面的程序中有一個錯誤，所以在運行時會拋出一個異常。但是，就象在本專欄以前的許多文章中已經(jīng)論證的那樣，一個程序拋出的精確異常（跟很棒的錯誤類型標識符一樣）對于找到錯誤藏在程序的什么地方并沒有什么幫助，我們也不想編譯器以這種方式改變程序，以使編譯的結(jié)果代碼拋出一個不同的異常。??

[清單?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?調(diào)用?productHelp。它的值應(yīng)為?1。否則，在類?Example?的任何實例上調(diào)用?product?都將產(chǎn)生?0?值，不管?Iterator?是什么值。??

假設(shè)這個錯誤終于被改正了，但同時，類?Example?的一個子類也被創(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?方法試圖通過當?accumulator?小于“1”時拋出運行時異常來捕捉對?productHelp?的不正確調(diào)用。不幸的是，這樣做將引入一個新的錯誤。如果?Iterator?含有任何?0?值的實例，都將使?productHelp?在自身的遞歸調(diào)用上崩潰。??

現(xiàn)在請注意，在類?Example2?的?main?方法中，創(chuàng)建了?Example2?的一個實例并調(diào)用了它的?product?方法。由于傳給這個方法的?Iterator?包含一個?0，因此程序?qū)⒈罎ⅰ??

然而，您可以看到類?Example?的?productHelp?是嚴格尾遞歸的。假設(shè)一個靜態(tài)編譯器想把這個方法的正文轉(zhuǎn)換成一個循環(huán)，如清單?3?所示：??

[清單?3.?靜態(tài)編譯不會優(yōu)化尾調(diào)用的一個示例]??

int ?productHelp(Iterator?i,? int ?accumulator)? {?
???? while ?(i.hasNext())? {?
??????accumulator? *= ?((Integer)i.next()).intValue();?
????} ?
???? return ?accumulator;?
??} ?

于是，最初對?productHelp?的調(diào)用，結(jié)果成了對超類的方法的調(diào)用。超方法將通過簡單地在?iterator?上循環(huán)來計算其結(jié)果。不會拋出任何異常。??

用兩個不同的靜態(tài)編譯器來編譯這段代碼，結(jié)果是一個會拋出異常，而另一個則不會，想想這是多么讓人感到困惑。??

您的?JIT?會做這種轉(zhuǎn)換嗎？
因此，如清單?3?中的示例所示，我們不能期望靜態(tài)編譯器會在保持語言語義的同時對?Java?代碼執(zhí)行尾遞歸轉(zhuǎn)換。相反地，我們必須依靠?JIT?進行的動態(tài)編譯。JIT?會不會做這種轉(zhuǎn)換是取決于?JVM。??

要判斷您的?JIT?會否轉(zhuǎn)換尾遞歸的一個辦法是編譯并運行如下小測試類：??

[清單?4.?判斷您的?JIT?能否轉(zhuǎn)換尾遞歸]

public ? class ?TailRecursionTest? {?

?? private ? static ? int ?loop( int ?i)? {?
???? return ?loop(i);?
??} ?

?? public ? static ? void ?main(String[]?args)? {?
????loop( 0 );?
??} ?
} ?

我們來考慮一下這個類的?loop?方法。這個方法只是盡可能長時間地對自身作遞歸調(diào)用。因為它永遠不會返回，也不會以任何方式影響任何外部變量，因此如清單?5?所示替換其代碼正文將保留程序的語義。??

[清單?5.?一個動態(tài)轉(zhuǎn)換]

public ? class ?TailRecursionTest? {?

?? private ? static ? int ?loop( int ?i)? {?
???? while ?( true )? {?
????} ?
??} ?

?? public ? static ? void ?main(String[]?args)? {?
????loop( 0 );?
??} ?
} ?

??
而且，事實上這也就是足夠完善的編譯器所做的轉(zhuǎn)換。??

如果您的?JIT?編譯器把尾遞歸調(diào)用轉(zhuǎn)換成迭代，這個程序?qū)o限期地運行下去。它所需的內(nèi)存很小，而且不會隨時間增加。??

另一方面，如果?JIT?不做這種轉(zhuǎn)換，程序?qū)芸旌谋M堆棧空間并報告一個堆棧溢出錯誤。??

我在兩個?Java?SDK?上運行這個程序，結(jié)果令人驚訝。在?SUN?公司的?Hotspot?JVM（版本?1.3?）上運行時，發(fā)現(xiàn)?Hotspot?不執(zhí)行這種轉(zhuǎn)換。缺省設(shè)置下，在我的機器上運行時，不到一秒鐘堆棧空間就被耗盡了。??

另一方面，程序在?IBM?的?JVM（版本?1.3?）上咕嚕嚕運行時卻沒有任何問題，這表明?IBM?的?JVM?以這種方式轉(zhuǎn)換代碼。??

總結(jié)
記住：我們不能寄希望于我們的代碼會總是運行在會轉(zhuǎn)換尾遞歸調(diào)用的?JVM?上。因此，為了保證您的程序在所有?JVM?上都有適當?shù)男阅埽鷳?yīng)始終努力把那些最自然地符合尾遞歸模式的代碼按迭代風(fēng)格編寫。??

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

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