CIS 210 Problem 6.2

Last updated 2007/11/08 11:39:59

Problem 6.2 - Finding greatest common divisors with recursion

The last problem in Assignment 3 described the Euclidean algorithm for finding the greatest common divisor of two numbers. In that problem, you coded a solution that used a loop. Each time through the loop, the larger number was replaced by the difference between the two numbers, and this continued until the two numbers were the same, and that was the desired GCD value.

A faster form of Euclid's algorithm reduces one of the numbers to the remainder of division by the other. This will get smaller a lot faster than the subtraction. We can state this improved algorithm as a recursive definition of the greatest common divisor of two numbers a and b:


Base case:         GCD(a,0) = a

Recursive case:    GCD(a,b) = GCD(b,a%b)

(Remember the % operator is the Java modulus operator, also called the remainder operator.) To convince yourself that it works, try it out on a couple of examples by hand, e.g., GCD(10,0), GCD(4,16), GCD(16,4), GCD(1,23). Trace these out by hand and make sure you believe your results.

Implement a recursive solution for finding the GCD as a recursively called method named computeGCD in the class RecursiveGCD. You can use this code as a start (this is almost identical to the starting code in problem 3.3). The main method takes two numbers from the command line and computes and displays the GCD of the numbers. If you don't give command line parameters, this driver code will prompt you for the numbers.

Test your code with the examples you did by hand.

Note

Look over your code carefully before running it and make sure that you have dealt with the base case properly so that the algorithm eventually terminates.

Make sure your code correctly handles negative numbers.

What to turn in

Turn in your RecursiveGCD.java. Make sure that it compiles and works for a variety of test cases.