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

Get Latest Updates on Facebook

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

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.