BlogsDope image BlogsDope

GCD using recursion

Feb. 28, 2021 JAVA RECURSION 7971

The Greatest Common Divisor (GCD) of two numbers is the greatest number that divides both of them.

GCD Example

Input:63 and 21.

       Output:21 

Input:10 and 5

       Output:5

  • In the first case, when we have taken the input of 63 and 21, the output is 21 because  63=7*3*3  and 21=7*3. The common divisors are 7 and 3 and greatest common divisor is 7*3=21.
  • In the second case, when we have taken input 10 and 5, the output is 5 because 10=2*5 and 5=1*5. The common divisor is 5 and it is also the greatest one.

Brute Force Approach for GCD

The basic idea is to try all integers from n (where n is the given second number, i.e., the smaller one) down until finding one that divides both the numbers.
 Let's take an example of 24 and 12.
  • 24%12=0 and 12%12=0. 12 divides both the numbers completely. Therefore, 12 is the GCD of these two numbers.

Another example of 6 and 4.

  • 6%4=2 and 4%4=0. 4 doesn't divide both the numbers completely. Therefore, decrementing value by 1(4-1=3).
  • 6%3=0 and 4%3=1. 3 doesn't divide both the numbers completely. Therefore, decrementing value by 1(3-1=2).
  • 6%2=0 and 4%2=0. 2 divides both the numbers completely. Therefore, 2 is the GCD of these two numbers.

Program

package codesdope;
import java.util.*;
public class codesdope 
{
	public static int gcd(int num1,int num2,int d)
	{
	   if(num2==0)
		return 0;
	   if(((num1%d)==0) && ((num2%d)==0))
		return d;
	   else 
	       return gcd(num1,num2,num2-1);
	} 
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int num1=sc.nextInt();
		int num2=sc.nextInt();
		System.out.println("gcd is "+gcd(num1,num2,num2));
	}
}

​63

21

gcd is 21

Let us take an example of of 6 and 4. And, dry run this code-

RECURSIVE CALL
Num1%d
Num2%d
d
gcd(6,4,4)
6%4=2
4%4=0
4-1=3
gcd(6,4,3)
6%3=0
4%3=1
3-1=2
gcd(6,4,2)
6%2=0
4%2=0
2

In last, 2 divides 6 and 4 completely. Therefore, 2 is the gcd of these two numbers.

Euclid's Algorithm Approach

The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b. In this approach firstly we divide the greater number with the smaller one. In the next step, we divide the divisor of the previous step with the remainder and continue till we get 0 as remainder.
Let's suppose a is the greater number among a and b. We will proceed like:
Step
Dividend
Divisor
Remainder
1
a
b
c
2
b
c
d
3
c
d
e
So, every time we are dividing the divisor of the previous step by the remainder of it. This will continue until we get 0 as remainder.
First, let me show the computations for a=210 and b=45.
  • Divide 210 by 45, and get the result 4 with remainder 30, so 210=4*45+30. 
  • Divide 45 by 30, and get the result 1 with remainder 15, so 45=1*30+15. 
  • Divide 30 by 15, and get the result 2 with remainder 0, so 30=2*15+0. 
  • The greatest common divisor of 210 and 45 is 15.

Program

package codesdope;
import java.util.*;
public class codesdope 
{
	public static int gcd(int num1,int num2)
	{
		if(num2==0)
			return num1;
		return gcd(num2,num1%num2);
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int num1=sc.nextInt();
		int num2=sc.nextInt();
		System.out.println("gcd is "+gcd(num1,num2));
	}
}

63 

21 

gcd is 21

Let us take an example of 6 and 4 and, dry run this code.
RECURSIVE CALL​
NUM1
NUM2
NUM1%NUM2
gcd(6,4)
6
4
6%4=2
gcd(4,2)
4
2
4%2=0
gcd(2,0)
2
0
-

Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).