Exceptional Puzzlers - Java Puzzlers: Traps, Pitfalls, and Corner Cases - page 126

Figure 5.1. The execution of WorkOut .
The figure shows one call from depth 0— the call from main — two calls from depth 1, four calls
from depth 2, and eight calls from depth 3, a total of fifteen calls. The eight calls from depth 3 each
result in an immediate StackOverflowError . At least on a VM that limits the stack depth to 3, the
program is not an infinite loop: It terminates after fifteen calls and eight exceptions.
But what about on a real VM? It still isn't an infinite loop. The call diagram looks just like the one
in Figure 5.1 only much, much bigger.
How much bigger? A quick experiment shows that many VMs limit stack depth to 1,024. The
number of calls is therefore 1 + 2 + 4 + 8 ... + 2 1,024 = 2 1,025 - 1. The number of exceptions thrown
is 2 1,024 . Let's assume that our machine can execute 10 10 calls per second and generate 10 10
exceptions per second, which is quite generous by current standards. Under these assumptions, the
program will terminate in about 1.7 x 10 291 years. To put this in perspective, the lifetime of our sun
is estimated at 10 10 years, so it is a safe bet that none of us will be around to see this program
terminate. Although it isn't an infinite loop, it might as well be.
Technically speaking, the call diagram is a complete binary tree whose depth is the stack depth
limit of the VM. The execution of the Workout program amounts to a preorder traversal of this
tree. In a preorder traversal, the program visits a node and then recursively visits its left and right
subtrees. One call is made for each edge in the tree, and one exception is thrown for each leaf node.
This puzzle doesn't have much in the way of a lesson. It does demonstrate that exponential
algorithms are impractical for all but the smallest inputs, and it shows that you can write an
exponential algorithm without even trying.
< Day Day Up >