## 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