本謎題將測試你對遞歸的了解程度。下面的程序?qū)⒆鲂┦裁茨兀?BR> public class Workout {
public static void main(String[] args) {
workHard();
System.out.println("It’s nap time.");
}
private static void workHard() {
try {
workHard();
} finally {
workHard();
}
}
}
要不是有try-finally語句，該程序的行為將非常明顯：workHard方法遞歸地調(diào)用它自身，直到程序拋出StackOverflowError，在此刻它以這個(gè)未捕獲的異常而終止。但是，try-finally語句把事情搞得復(fù)雜了。當(dāng)它試圖拋出StackOverflowError時(shí)，程序?qū)?huì)在finally語句塊的workHard方法中終止，這樣，它就遞歸調(diào)用了自己。這看起來確實(shí)就像是一個(gè)無限循環(huán)的秘方，但是這個(gè)程序真的會(huì)無限循環(huán)下去嗎？如果你運(yùn)行它，它似乎確實(shí)是這么做的，但是要想確認(rèn)的方式就是分析它的行為。
Java虛擬機(jī)對棧的深度限制到了某個(gè)預(yù)設(shè)的水平。當(dāng)超過這個(gè)水平時(shí)，VM就拋出StackOverflowError。為了讓我們能夠更方便地考慮程序的行為，我們假設(shè)棧的深度為3，這比它實(shí)際的深度要小得多。現(xiàn)在讓我們來跟蹤其執(zhí)行過程。
main方法調(diào)用workHard，而它又從其try語句塊中遞歸地調(diào)用了自己，然后它再一次從其try語句塊中調(diào)用了自己。在此時(shí)，棧的深度是3。當(dāng)workHard方法試圖從其try語句塊中再次調(diào)用自己時(shí)，該調(diào)用立即就會(huì)以StackOverflowError而失敗。這個(gè)錯(cuò)誤是在最內(nèi)部的finally語句塊中被捕獲的，在此處棧的深度已經(jīng)達(dá)到了3。在那里，workHard方法試圖遞歸地調(diào)用它自己，但是該調(diào)用卻以StackOverflowError而失敗。這個(gè)錯(cuò)誤將在上一級的finally語句塊中被捕獲，在此處站的深度是2。該finally中的調(diào)用將與相對應(yīng)的try語句塊具有相同的行為：最終都會(huì)產(chǎn)生一個(gè)StackOverflowError。這似乎形成了一種模式，而事實(shí)也確實(shí)如此。
WorkOut的運(yùn)行過程如左面的圖所示。在這張圖中，對workHard的調(diào)用用箭頭表示，workHard的執(zhí)行用圓圈表示。所有的調(diào)用除了一個(gè)之外，都是遞歸的。會(huì)立即產(chǎn)生StackOverflowError異常的調(diào)用用由灰色圓圈前導(dǎo)的箭頭表示，try語句塊中的調(diào)用用向左邊的向下箭頭表示，finally語句塊中的調(diào)用用向右邊的向下箭頭表示。箭頭上的數(shù)字描述了調(diào)用的順序。
這張圖展示了一個(gè)深度為0的調(diào)用（即main中的調(diào)用），兩個(gè)深度為1的調(diào)用，四個(gè)深度為2的調(diào)用，和八個(gè)深度為3的調(diào)用，總共是15個(gè)調(diào)用。那八個(gè)深度為3的調(diào)用每一個(gè)都會(huì)立即產(chǎn)生StackOverflowError。至少在把棧的深度限制為3的VM上，該程序不會(huì)是一個(gè)無限循環(huán)：它在15個(gè)調(diào)用和8個(gè)異常之后就會(huì)終止。但是對于真實(shí)的VM又會(huì)怎樣呢？它仍然不會(huì)是一個(gè)無限循環(huán)。其調(diào)用圖與前面的圖相似，只不過要大得多得多而已。
那么，究竟大到什么程度呢？有一個(gè)快速的試驗(yàn)表明許多VM都將棧的深度限制為1024，因此，調(diào)用的數(shù)量就是1+2+4+8…+21,024=21,025-1，而拋出的異常的數(shù)量是21,024。假設(shè)我們的機(jī)器可以在每秒鐘內(nèi)執(zhí)行1010個(gè)調(diào)用，并產(chǎn)生1010個(gè)異常，按照當(dāng)前的標(biāo)準(zhǔn)，這個(gè)假設(shè)的數(shù)量已經(jīng)相當(dāng)高了。在這樣的假設(shè)條件下，程序?qū)⒃诖蠹s1.7×10291年后終止。為了讓你對這個(gè)時(shí)間有直觀的概念，我告訴你，我們的太陽的生命周期大約是1010年，所以我們可以很確定，我們中沒有任何人能夠看到這個(gè)程序終止的時(shí)刻。盡管它不是一個(gè)無限循環(huán)，但是它也就算是一個(gè)無限循環(huán)吧。
從技術(shù)角度講，調(diào)用圖是一棵完全二叉樹，它的深度就是VM的棧深度的上限。WorkOut程序的執(zhí)行過程等于是在先序遍歷這棵樹。在先序遍歷中，程序先訪問一個(gè)節(jié)點(diǎn)，然后遞歸地訪問它的左子樹和右子樹。對于樹中的每一條邊，都會(huì)產(chǎn)生一個(gè)調(diào)用，而對于樹中的每一個(gè)節(jié)點(diǎn)，都會(huì)拋出一個(gè)異常。
本謎題沒有很多關(guān)于教訓(xùn)方面的東西。它證明了指數(shù)算法對于除了最小輸入之外的所有情況都是不可行的，它還表明了你甚至可以不費(fèi)什么勁就可以編寫出一個(gè)指數(shù)算法。
public static void main(String[] args) {
workHard();
System.out.println("It’s nap time.");
}
private static void workHard() {
try {
workHard();
} finally {
workHard();
}
}
}
要不是有try-finally語句，該程序的行為將非常明顯：workHard方法遞歸地調(diào)用它自身，直到程序拋出StackOverflowError，在此刻它以這個(gè)未捕獲的異常而終止。但是，try-finally語句把事情搞得復(fù)雜了。當(dāng)它試圖拋出StackOverflowError時(shí)，程序?qū)?huì)在finally語句塊的workHard方法中終止，這樣，它就遞歸調(diào)用了自己。這看起來確實(shí)就像是一個(gè)無限循環(huán)的秘方，但是這個(gè)程序真的會(huì)無限循環(huán)下去嗎？如果你運(yùn)行它，它似乎確實(shí)是這么做的，但是要想確認(rèn)的方式就是分析它的行為。
Java虛擬機(jī)對棧的深度限制到了某個(gè)預(yù)設(shè)的水平。當(dāng)超過這個(gè)水平時(shí)，VM就拋出StackOverflowError。為了讓我們能夠更方便地考慮程序的行為，我們假設(shè)棧的深度為3，這比它實(shí)際的深度要小得多。現(xiàn)在讓我們來跟蹤其執(zhí)行過程。
main方法調(diào)用workHard，而它又從其try語句塊中遞歸地調(diào)用了自己，然后它再一次從其try語句塊中調(diào)用了自己。在此時(shí)，棧的深度是3。當(dāng)workHard方法試圖從其try語句塊中再次調(diào)用自己時(shí)，該調(diào)用立即就會(huì)以StackOverflowError而失敗。這個(gè)錯(cuò)誤是在最內(nèi)部的finally語句塊中被捕獲的，在此處棧的深度已經(jīng)達(dá)到了3。在那里，workHard方法試圖遞歸地調(diào)用它自己，但是該調(diào)用卻以StackOverflowError而失敗。這個(gè)錯(cuò)誤將在上一級的finally語句塊中被捕獲，在此處站的深度是2。該finally中的調(diào)用將與相對應(yīng)的try語句塊具有相同的行為：最終都會(huì)產(chǎn)生一個(gè)StackOverflowError。這似乎形成了一種模式，而事實(shí)也確實(shí)如此。
WorkOut的運(yùn)行過程如左面的圖所示。在這張圖中，對workHard的調(diào)用用箭頭表示，workHard的執(zhí)行用圓圈表示。所有的調(diào)用除了一個(gè)之外，都是遞歸的。會(huì)立即產(chǎn)生StackOverflowError異常的調(diào)用用由灰色圓圈前導(dǎo)的箭頭表示，try語句塊中的調(diào)用用向左邊的向下箭頭表示，finally語句塊中的調(diào)用用向右邊的向下箭頭表示。箭頭上的數(shù)字描述了調(diào)用的順序。
這張圖展示了一個(gè)深度為0的調(diào)用（即main中的調(diào)用），兩個(gè)深度為1的調(diào)用，四個(gè)深度為2的調(diào)用，和八個(gè)深度為3的調(diào)用，總共是15個(gè)調(diào)用。那八個(gè)深度為3的調(diào)用每一個(gè)都會(huì)立即產(chǎn)生StackOverflowError。至少在把棧的深度限制為3的VM上，該程序不會(huì)是一個(gè)無限循環(huán)：它在15個(gè)調(diào)用和8個(gè)異常之后就會(huì)終止。但是對于真實(shí)的VM又會(huì)怎樣呢？它仍然不會(huì)是一個(gè)無限循環(huán)。其調(diào)用圖與前面的圖相似，只不過要大得多得多而已。
那么，究竟大到什么程度呢？有一個(gè)快速的試驗(yàn)表明許多VM都將棧的深度限制為1024，因此，調(diào)用的數(shù)量就是1+2+4+8…+21,024=21,025-1，而拋出的異常的數(shù)量是21,024。假設(shè)我們的機(jī)器可以在每秒鐘內(nèi)執(zhí)行1010個(gè)調(diào)用，并產(chǎn)生1010個(gè)異常，按照當(dāng)前的標(biāo)準(zhǔn)，這個(gè)假設(shè)的數(shù)量已經(jīng)相當(dāng)高了。在這樣的假設(shè)條件下，程序?qū)⒃诖蠹s1.7×10291年后終止。為了讓你對這個(gè)時(shí)間有直觀的概念，我告訴你，我們的太陽的生命周期大約是1010年，所以我們可以很確定，我們中沒有任何人能夠看到這個(gè)程序終止的時(shí)刻。盡管它不是一個(gè)無限循環(huán)，但是它也就算是一個(gè)無限循環(huán)吧。
從技術(shù)角度講，調(diào)用圖是一棵完全二叉樹，它的深度就是VM的棧深度的上限。WorkOut程序的執(zhí)行過程等于是在先序遍歷這棵樹。在先序遍歷中，程序先訪問一個(gè)節(jié)點(diǎn)，然后遞歸地訪問它的左子樹和右子樹。對于樹中的每一條邊，都會(huì)產(chǎn)生一個(gè)調(diào)用，而對于樹中的每一個(gè)節(jié)點(diǎn)，都會(huì)拋出一個(gè)異常。
本謎題沒有很多關(guān)于教訓(xùn)方面的東西。它證明了指數(shù)算法對于除了最小輸入之外的所有情況都是不可行的，它還表明了你甚至可以不費(fèi)什么勁就可以編寫出一個(gè)指數(shù)算法。