# Find GCD of Two Numbers using Recursion – Java Code

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.

Subscribe Our Tutorials

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.

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

Java program to print Fibonacci series upto N number 