What is GCD?
The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder.
Examples:
- GCD(48, 18) = 6
- GCD(56, 98) = 14
Recursive Idea (Euclidean Algorithm)
The Euclidean algorithm is the most efficient recursive method for GCD: gcd(a,b)={aif b=0gcd(b,a%b)if b≠0\text{gcd}(a, b) = \begin{cases} a & \text{if } b = 0 \\ \text{gcd}(b, a \% b) & \text{if } b \neq 0 \end{cases}
Java Code
public class GCDRecursion {
// Recursive method to calculate GCD
public static int gcd(int a, int b) {
if (b == 0) {
return a; // Base case
}
return gcd(b, a % b); // Recursive case
}
public static void main(String[] args) {
int num1 = 48, num2 = 18;
int result = gcd(num1, num2);
System.out.println("GCD of " + num1 + " and " + num2 + " is: " + result);
}
}
Output
GCD of 48 and 18 is: 6