Recursion - Building Java Programs: A Back to Basics Approach

Java Reference

In-Depth Information

Continued from previous page

The original code tests whether they are strictly less than 0 . It doesn't seem like

this variation should make much difference, but it does. If we execute this version

of the code to solve our original problem of finding the GCD of 132 and 20, the

program produces many lines of output that look like the following:

at Bug.gcd(Bug.java:9)

The first time you see this, you are likely to think that something has broken

on your computer because you will get so many lines of output. The number of

lines of output will vary from one system to another, but it's likely to be hun-

dreds, if not thousands. If you scroll all the way back up, you'll see that the

output begins with this message:

Exception in thread "main" java.lang.StackOverflowError

at Bug.gcd(Bug.java:9)

...

Java is letting you know that the call stack has gotten too big. Why did this

happen? Remember the trace of execution for this case:

gcd(132, 20) = gcd(20, 12)

gcd(20, 12) = gcd(12, 8)

gcd(12, 8) = gcd(8, 4)

gcd(8, 4) = gcd(4, 0)

...

Consider what happens at this point, when we call gcd(4, 0) . The value of y is

0 , which is our base case, so normally we would expect the method to return the

value 4 and terminate. But the method begins by checking whether either x or y

is less than or equal to 0 . Since y is 0 , this test evaluates to true , so the method

makes a recursive call with the absolute values of x and y . But the absolute values

of 4 and 0 are 4 and 0. So the method decides that gcd(4, 0) must be equal to

gcd(4, 0) , which must be equal to gcd(4, 0) :

Continued on next page

Search WWH ::

Custom Search

Home