Saturday, January 19, 2008

Finding Greatest Common Divisor recursively

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers.

The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The code below shows how to implement gcd function recursively.

* Return the greatest common divisor

public static long gcd(long a, long b) {

if (b==0)
return a;
return gcd(b, a % b);

No comments: