GCD Recursion Algorithm
The GCD Recursion Algorithm, also known as the Euclidean Algorithm, is a time-tested technique for finding the greatest common divisor (GCD) of two integers. The GCD is the largest positive integer that divides both numbers without leaving a remainder. The algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. By applying this rule recursively, the algorithm reduces the problem of finding the GCD of two numbers to a series of smaller instances, until the GCD is finally obtained.
The algorithm starts with two positive integers, a and b, where a is usually the larger number. If either number is zero, the GCD is the non-zero number. Otherwise, the algorithm calls itself recursively with the pair of numbers (b, a % b), where % represents the modulo operation. This process continues until the second number (b) becomes zero. At that point, the first number (a) is the GCD of the original pair. This recursion-based algorithm is efficient and widely used in various applications, including simplifying fractions, solving Diophantine equations, and cryptography.
package Maths;
/**
* @author https://github.com/shellhub/
*/
public class GCDRecursion {
public static void main(String[] args) {
System.out.println(gcd(20, 15)); /* output: 5 */
System.out.println(gcd(10, 8)); /* output: 2 */
System.out.println(gcd(gcd(10, 5), gcd(5, 10))); /* output: 5 */
}
/**
* get greatest common divisor
*
* @param a the first number
* @param b the second number
* @return gcd
*/
public static int gcd(int a, int b) {
if (a < 0 || b < 0) {
throw new ArithmeticException();
}
if (a == 0 || b == 0) {
return Math.abs(a - b);
}
if (a % b == 0) {
return b;
} else {
return gcd(b, a % b);
}
}
}
