In this java program, we will learn about how to find the GCD or HCF using a recursion.
The Greatest Common Divisor(GCD) of two or more integers, is the largest positive integer that divides the numbers without a remainder. GCD is also known as Highest Common Factor (HCF).
The recursive equation for GCD calculation is as follows. It is called Euclidean algorithm.
gcd(a, b) = gcd(b, a%b)
= a, if b == 0
where, a and b are two integers.
To understand this java program, you should have understanding of the following Java programming concepts:
Java program to find gcd of two numbers using recursion
public class GcdRecursion {
public static void main(String[] args) {
int a, b, gcd;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter Two Number");
a = scanner.nextInt();
b = scanner.nextInt();
gcd = getGcd(a, b);
System.out.println("GCD = " + gcd);
}
public static int getGcd(int a, int b) {
if (b == 0) {
return a;
} else {
return getGcd(b, a % b);
}
}
}
Output
Enter Two Number 20 36 GCD = 4