Recursion - Data Structures and Problem Solving Using Java - page 314

7.4.3 greatest common divisor
and multiplicative inverses

Given two nonnegative integers A and B, their greatest common divisor,
gcd( A, B ), is the largest integer D that divides both A and B . For instance,
gcd(70, 25) is 5. In other words, the greatest common divisor (gcd) is the larg-
est integer that divides two given integers.
We can easily verify that gcd( A, B ) ≡ gcd( A - B, B ). If D divides both A
and B, it must also divide A - B; and if D divides both A - B and B, then it
must also divide A .
This observation leads to a simple algorithm in which we repeatedly sub-
tract B from A, transforming the problem into a smaller one. Eventually A
becomes less than B, and then we can switch roles for A and B and continue
from there. At some point B will become 0. Then we know that gcd( A, 0) ≡ A,
and as each transformation preserves the gcd of the original A and B, we have
our answer. This algorithm is called Euclid's algorithm and was first
described more than 2,000 years ago. Although correct, it is unusable for large
numbers because a huge number of subtractions are likely to be required.
A computationally efficient modification is that the repeated subtractions
of B from A until A is smaller than B is equivalent to the conversion of A to
precisely A mod B . Thus gcd( A, B ) ≡ gcd( B, A mod B ). This recursive defini-
tion, along with the base case in which B = 0, is used directly to obtain the
routine shown in Figure 7.17. To visualize how it works, note that in the pre-
vious example we used the following sequence of recursive calls to deduce
that the gcd of 70 and 25 is 5: gcd(70, 25) ⇒

The greatest com-
mon divisor (gcd) of
two integers is the
largest integer that
divides both of
them.

gcd(25, 20) ⇒ gcd(20, 5) ⇒

gcd(5, 0) ⇒ 5.
The number of recursive calls used is proportional to the logarithm of A,
which is the same order of magnitude as the other routines that we have pre-
sented in this section. The reason is that, in two recursive calls, the problem is
reduced at least in half. The proof of this is left for you to do as Exercise 7.11.

figure 7.17
Computation of
greatest common
divisor

1 /**
2 * Return the greatest common divisor.
3 */
4 public static long gcd( long a, long b )
5 {
6 if( b == 0 )
7 return a;
8 else
9 return gcd( b, a % b );
10 }