GCD Program in Java Using Recursion

GCD Program in Java Using Recursion. The greatest common divisor (GCD) of two or more integers is the precise divisor number that divides them. It’s also known as the greatest common factor (HCF). Because both integers can be split by two, the largest common factor of 10 and 5 is 5.

class Main
{
static int gcd(int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;
if (a == b)
return a;
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
public static void main(String[] args)
{
int a = 10, b = 5;
System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}

Output:

GCD of 10 and 5 is 5

GCD Program in Java Using Recursion

A GCD is a Greatest Common Divisor in mathematics. A GCF, or greatest common factor, is another term for this. The GCD is the biggest integer that can be divided into a collection of numbers with a remainder of zero in each case. In this approach, the largest number in the provided set of numbers is divided by the second-largest number, and the second-largest number is divided by the remainder of the preceding operation, and so on until the residual is zero.

HCF in Java

HCF’s properties are listed below. When two or more numbers are divided by HCF, each number is divided without a residual. A factor of each of the numbers is the HCF of two or more numbers. When two or more integers are added together, the HCF is always less than or equal to each of the numbers. When two or more prime numbers are added together, the HCF is always 1.