Java Program to Find G.C.D Using Recursion

To understand this example, you should have the knowledge of the following Java programming topics:


This program takes two positive integers and calculates GCD using recursion.

Visit this page to learn how you can calculate the GCD using loops.

Example: GCD of Two Numbers using Recursion

public class GCD {

    public static void main(String[] args) {
        int n1 = 366, n2 = 60;
        int hcf = hcf(n1, n2);

        System.out.printf("G.C.D of %d and %d is %d.", n1, n2, hcf);
    }

    public static int hcf(int n1, int n2)
    {
        if (n2 != 0)
            return hcf(n2, n1 % n2);
        else
            return n1;
    }
}

Output

G.C.D of 366 and 60 is 6.

In the above program, the recursive function is called until n2 is 0. In the end, the value of n1 is the GCD or HCF of the given two numbers.

Execution Steps
No. Recursive call n1 n2 n1 % n2
1 hcf(366, 60) 366 60 6
2 hcf(60, 6) 60 6 0
Final hcf(6, 0) 6 0 -
Did you find this article helpful?

Our premium learning platform, created with over a decade of experience and thousands of feedbacks.

Learn and improve your coding skills like never before.

Try Programiz PRO
  • Interactive Courses
  • Certificates
  • AI Help
  • 2000+ Challenges