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