Write a Java program to find GCD of two numbers using Recursion. Given two input integers, we have to write a code to find GCD of two numbers using recursion. For this program, I assume you are familiar with the concept of recursion. If you don’t know about recursion then check my previous post on recursion vs iteration.

## GCD – Greatest Common Divisor

The GCD refers to Greatest Common Divisor. So, The GCD of two numbers A and B is the largest positive integers that divide both the integers (A and B).

For example – Let’s take two numbers 63 and 21.

Factors of 63 – 3, 7, 9, 21 and 63

Factors of 21 – 3, 7, 21

Highest factors of both the numbers are 21. So the GCD (63,21) is 21.

In this tutorial, we use **Euclidean Algorithm** to find GCD of two numbers.

## Algorithm to Find GCD of Two Numbers – Euclidean Algorithm

Euclidean Algorithm for finding GCD of two integers A and B.

i) If A = 0 then GCD(A, B) = B. If A is zero then Greatest common divisor of both the numbers A and B is B.

ii) If B = 0 then GCD(A, B) = A. If B is zero then Greatest common divisor of both the numbers A and B is A.

iii) If A > B then GCD(A, B) = GCD (A % B, B). If B > A then GCD(A, B) = GCD (A, B % A). This process is repeated until any of the numbers become zero.

Let’s understand this algorithm through example –

Suppose we have to find the GCD of 63 and 21.

GCD(63, 21) : A = 63 and B = 21

i) A > B. GCD (63 % 21, 21).

ii) In the second step, the value of A is 0 and B are 21. So the GCD (0, 21) is 21.

## Find GCD of Two Numbers using Recursion – Java Code

We understood the algorithm to calculate GCD of two numbers using recursion. Let’s implement them using Java code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | public class GCD { public static int calculateGCD(int a, int b) { //If both the number are equal if (a == b) { return a; /* If a is equal to zero then return b */ } else if (a == 0) { return b; /* If b is equal to zero then return a */ } else if (b == 0) { return a; } else if (a > b) { //Recursive call return calculateGCD(a % b, b); } else { //Recursive call return calculateGCD(a, b % a); } } public static void main(String[] args) { int a = 63; int b = 21; System.out.println(calculateGCD(a, b)); } } /*** Output ***/ 21 |

Java program to find the first non-repeated character in a String