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