Find Greatest Common Denominator (GCD) in Java

Exercise:

Write a Java Program to find the Greatest Common Denominator (GCD) using recursion.

Click Here to View the Solution!
public class GCDCalculator {
  
     public static void main(String[] args) {
         int num1 = 266, num2 = 40;
         int hcf = hcf(num1, num2);
  
         System.out.printf("G.C.D of %d and %d is %d.", num1, num2, hcf);
     }
  
     public static int hcf(int num1, int num2)
     {
         if (num2 != 0)
             return hcf(num2, num1 % num2);
         else
             return num1;
     } 
 }
Click Here to View the Output!
G.C.D of 266 and 40 is 2.
Click Here to View the Explanation!
  • This program deals with calculating Greatest Common Divisor (G.C.D) by employing Recursion Method.
  • Primarily, two integers having positive values are taken on which Recursion is applied. (266, 40)
  • Those two integers are passed as arguments, to parameters num1 and num2 of hcf(num1, num2) function, hcf(266, 40).
  • The function keeps recurring as long as value of ‘num2’ does not approach ‘0’. Once ‘num2’ becomes ‘0’, value of ‘num1’ will depict Highest Common Factor for those two integers provided as input.
  • During the first step of execution, the return value for hcf(266, 40) is ‘2’.
  • In the next pass of arguments, ‘num2’ becomes ‘num1’ and the previous return value becomes ‘num2’, hcf(40, 2).
  • In the third step, the return value from the previous recursion hcf(40, 2) : 0, is passed as hcf(2, 0) returning a value of ‘2’.
  • As ‘num2’ became ‘0’ in the last step of execution, therefore ‘num1’ which is ‘2’ is the calculated G.C.D for the given values (266, 40).

%d bloggers like this: