gcd(20, 30) = gcd(30, 20 mod 30) = gcd(30, 20)
= gcd(20, 30 mod 20) = gcd(20, 10) = gcd(10, 20 mod 10) =
gcd(10, 0) = 10.
gcd(112, 42) = gcd(42, 112 mod 42) = gcd(42, 28)
= gcd(28, 42 mod 28) = gcd(28, 14) = gcd(14, 28 mod 14) = gcd(14,0) = 0.
gcd(x, y) = x when y = 0
and the recursive component is
gcd(x, y) = gcd(y, x mod y), y > 0.
x < y,
the first application of the definition
gives us gcd(x, y) = gcd(y, x mod y) = gcd(y, x).
Following this, the first parameter is > the
second. So, we may consider only the case when
x >= y.
x = y, an application
of the definition results in gcd(x,y) = gcd(y, x mod y)
= gcd(y,0) which is an occurrence of gcd
in the base component.
x > y, an application
of the definition results in gcd(x,y) = gcd(y, x mod y)
= gcd(y,z), where 0 <= z < y.
Each application of the recursive component decreases the second
parameter. Therefore, after a sufficient number of
applications (at most y), the second
parameter will become 0 and we will
have an occurrence of
gcd which is
in the base component.
applications.GCD.*
are given below.
/** @return the gcd of x and y
* @throws IllegalArgumentException when x or y < 0 */
public static int gcd(int x, int y)
{
if (x < 0 || y < 0)
throw new IllegalArgumentException("x and y must be >= 0, "
+ "x = " + x + " y = " + y);
return rgcd(x, y);
}
/** @return the gcd of x and y
* assumes x,y >= 0 */
private static int rgcd(int x, int y)
{return (y == 0) ? x : rgcd(y, x % y);}