# 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.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
```