How to find GCD of two numbers. In this tutorial, I am going to discuss multiple approaches 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 example:
Input n1 : 36 n2 : 54
Output 18
Explanation :
The divisiors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36 and the divisiors of 54 are 1, 2, 3, 6, 9, 18, 27, 54.
Common divisors are 1, 2, 3, 6, 9, 12 and 18.
The GCD (Greatest Common Divisior) for 36 and 54 is 18.
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 of two numbers A and B is the largest positive common divisor 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
The common divisiors of both the numbers are 3, 7, 21. Out of which the greatest common divisior is 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
