Calculate GCD (Greatest common divisor) of 2 numbers recursively.

In mathematics, the greatest common divisor (gcd) of two positive numbers, when at least one of them is not zero, is the largest positive integer that is a divisor of both numbers. For example : 

  1. The GCD of 8 and 12 is 4.
  2. The GCD of 0 and 7 is 7.

Now we need to calculate the GCD of 2 numbers recursively.

  1. Consider we have 2 numbers as input m,n.
  2. Find the smaller number between m and n. Consider the smaller number is g.
  3. The idea is to try all integers from g down until finding one that divides m and n evenly. 
  4. First, define getGCD() that takes in mn and  g . If g is the common divisor of m and n then return g. Otherwise try with a smaller g.
package com.tuturself.rec;

public class GCDCalculator {

	public static int getGCD(int m, int n, int smaller) {

		if (m < 0 || n < 0) {
			System.out.println("NO GCD FOUND");
			return -1;
		}
		// when one of the number is Zero
		// In that case the non-zero number is the GCD
		if (smaller == 0) {
			return m == 0 ? n : m;
		}
		
		if (((m % smaller) == 0) && ((n % smaller) == 0))
			return smaller;
		else
			return getGCD(m, n, smaller - 1);
	}

	public static void main(String[] args) {
		int a = 55;
		int b = 77;
		int smaller = a > b ? b : a;

		System.out.println("GCD of a: " + a + " and b: " + b + " is: "
				+ getGCD(a, b, smaller));

	}
}

Output of the program is :

GCD of a: 35 and b: 77 is: 7

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself