GCD Using Recursion
What is GCD?
GCD stands for "Greatest Common Divisor." It is a mathematical concept used to find the largest positive integer that divides two or more numbers without leaving a remainder. In other words, the GCD is the largest number that both numbers can be evenly divided by.
For example, the GCD of 12 and 18 is 6 because 6 is the largest number that divides both 12 and 18 without leaving a remainder. Similarly, the GCD of 24, 36, and 48 is 12 because 12 is the largest number that divides all three numbers evenly.
GCD is a fundamental concept in number theory and has various applications in fields such as mathematics, computer science, and engineering. It's used in simplifying fractions, solving Diophantine equations, and optimizing algorithms, among other things.
How to find GCD using for loop?
Python Example:
def gcd(a, b):
for i in range(min(a, b), 0, -1):
if a % i == 0 and b % i == 0:
return i
print(gcd(48, 18)) # Output: 6
Output:
6
Java Example:
class GCD {
public static int gcd(int a, int b) {
for (int i = Math.min(a, b); i > 0; i--) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1;
}
public static void main(String[] args) {
System.out.println(gcd(48, 18)); // Output: 6
}
}
Output:
6
C++ Example:
#include <iostream>
using namespace std;
int gcd(int a, int b) {
for (int i = min(a, b); i > 0; i--) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1;
}
int main() {
cout << gcd(48, 18); // Output: 6
return 0;
}
Output:
6
C Example:
#include <stdio.h>
int gcd(int a, int b) {
for (int i = (a < b ? a : b); i > 0; i--) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1;
}
int main() {
printf("%d", gcd(48, 18)); // Output: 6
return 0;
}
Output:
6
How to find GCD using Recursion?
Python Example:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
print(gcd(48, 18)) # Output: 6
Output:
6
Java Example:
class GCD {
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static void main(String[] args) {
System.out.println(gcd(48, 18)); // Output: 6
}
}
Output:
6
C++ Example:
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
cout << gcd(48, 18); // Output: 6
return 0;
}
Output:
6
C Example:
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
printf("%d", gcd(48, 18)); // Output: 6
return 0;
}
Output:
6
Explanation:
The GCD function uses the Euclidean algorithm to find the GCD of two numbers a and b. If b is 0, then a is the GCD. Otherwise, it recursively calls itself with b and the remainder of a divided by b. The process continues until b becomes 0, yielding the GCD.