Java Program to Find GCD Using Recursion

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.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);
Enter Two Number
20 36
GCD = 4