Recursion - Building Java Programs: A Back to Basics Approach - page 741

Continued from previous page
gcd(132, 20) = gcd(20, 12)
gcd(20, 12) = gcd(12, 8)
gcd(12, 8) = gcd(8, 4)
gcd(8, 4) = gcd(4, 0)
gcd(4, 0) = gcd(4, 0)
gcd(4, 0) = gcd(4, 0)
gcd(4, 0) = gcd(4, 0)
gcd(4, 0) = gcd(4, 0)
...
In other words, this version generates infinitely many recursive calls. Java
allows you to make a lot of recursive calls, but eventually it runs out of space.
When it does, it gives you a back trace to let you know how you got to the error.
In this case, the back trace is not nearly as helpful as usual because almost all of
the calls will involve the infinite recursion.
Again, think in terms of stacking pieces of paper on top of each other as methods
are called. You'd wind up with a stack containing hundreds or even thousands of
sheets, and you would have to look back through all of these to find the problem.
To handle these situations, you have to look closely at the line number to see
which line of your program generated the infinite recursion. In this simple case,
we know that it is the recursive call for negative x and y values. That alone might
be enough to allow us to pinpoint the error. If the problem isn't obvious, though,
you might need to include println statements to figure out what is going on.
For example, in this code, we could add a println just before the recursive call:
public static int gcd(int x, int y) {
if (x <= 0 || y <= 0) {
// recursive case with negative value(s)
System.out.println("x = " + x + " and y = " + y);
return gcd(Math.abs(x), Math.abs(y));
} else if (y == 0) {
...
}
When we run the program with that println in place, the code produces
hundreds of lines of output of the form:
x = 4 and y = 0
If we examine that case closely, we'll see that we don't have negative values
and will realize that we have to fix the test we are using.