JAVA program to find gcd/hcf using Euclidean algorithm using recursion

JAVA program to find gcd/hcf using Euclidean algorithm using recursion

This JAVA program is to find gcd/hcf using Euclidean algorithm using recursion. HCF(Highest Common Factor)/GCD(Greatest Common Divisor) is the largest positive integer which divides each of the two numbers.

For example gcd of 42 and 18 is 6 as divisors of 42 are 1,2,3,4,6,7,14,21 and divisors of 18 are 1,2,3,6,9,18 , so the greatest common divisor is 6.

Logic

We subtract smaller number from larger number i.e. we decrease the larger number, or gcd will not change if we do it vice versa. So if we keep subtracting repeatedly the larger of two, we end up with gcd.For recursion, instead of performing subtraction, we keep dividing by the smaller number and the algorithm stops when we find remainder 0.

Dry Run of the Program

Take input as n1=12 and n2=8

We enter function gcd()

int gcd(int a,int b)

a=12 and b=8

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(8%12,12)  i.e. return gcd(8,12)

A recursive call[gcd(8,12)]

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(12%8,8)  i.e. return gcd(4,8)

A recursive call[gcd(4,8)]

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(8%4,4)  i.e. return gcd(0,4)

A recursive call[gcd(0,4)]

if(a==0) true

return b;  i.e. return 4….final answer

Program

import java.util.*;

class mr11
{
	public static void main(String args[])
	{
    		int n1,n2,answer=1;
		Scanner sc = new Scanner(System.in);
    		System.out.println("Enter 1st no");
    		n1=sc.nextInt();
    		System.out.println("Enter 2nd no");
    		n2=sc.nextInt();    	
		
		answer=gcd(n1,n2);
   		System.out.println("GCD("+n1+","+n2+") = "+answer);
	}

	static int gcd(int a, int b)
	{
    		if(a==0)
        		return b;
    		else
        		return gcd(b%a,a);
	}
}

Output

Share Me!