🔄📚Intermediate

Find GCD Using Recursion

Euclidean algorithm recursive

The Greatest Common Divisor (GCD) is the largest number that divides both numbers. The Euclidean Algorithm is an efficient method using: GCD(a, b) = GCD(b, a % b)

📐 Euclidean Algorithm

Based on the principle: GCD(a, b) = GCD(b, a mod b)

•Base case: When b = 0, GCD = a
•Recursive case: GCD(a, b) = GCD(b, a % b)

🔢 Example: GCD(48, 18)

GCD(48, 18) → 48 % 18 = 12 → GCD(18, 12)

GCD(18, 12) → 18 % 12 = 6 → GCD(12, 6)

GCD(12, 6) → 12 % 6 = 0 → GCD(6, 0)

GCD(6, 0) → b = 0, return a = 6

∴ GCD(48, 18) = 6

Program Code

gcd_recursion.c

1#include <stdio.h>
2
3// Recursive GCD using Euclidean Algorithm
4int gcd(int a, int b) {
5    if (b == 0) return a;  // Base case: GCD(a, 0) = a
6    return gcd(b, a % b);  // Recursive case
7}
8
9int main() {
10    int a, b;
11    
12    printf("Enter two numbers: ");
13    scanf("%d %d", &a, &b);
14    
15    printf("GCD of %d and %d = %d\n", a, b, gcd(a, b));
16    return 0;
17}

Output

Enter two numbers: 48 18

GCD of 48 and 18 = 6

Factorial Using Recursion

Reverse a Stack Using Recursion

Related Examples

Check Prime Number By Creating Function

Intermediate

Display Prime Numbers Using Functions

Intermediate

Find All Roots of Quadratic Equation

Intermediate

Check if Number is Sum of Two Primes

Intermediate

Want to Learn More?

Explore our comprehensive tutorials for in-depth explanations of C programming concepts.

Browse Tutorials

Back to All Examples