C Programs

Share with a Friend

Functions in C

GCD using Recursive function

GCD (Greatest Common Divisor) is one of the most common and useful mathematical operations in C programming.

GCD (Greatest Common Divisor) using Recursion demonstrates a cleaner and more elegant version of the Euclidean algorithm.

C Program: GCD using Recursive function

#include <stdio.h>
 
// Function declaration
int gcd(int a, int b);
 
int main() {
    int num1, num2, result;
 
    // Input two numbers
    printf("Enter two positive integers: ");
    scanf("%d %d", &num1, &num2);
 
    // Validate input
    if (num1 <= 0 || num2 <= 0) {
        printf("Please enter positive integers only.\n");
    } else {
        // Function call
        result = gcd(num1, num2);
        printf("GCD of %d and %d is %d\n", num1, num2, result);
    }
 
    return 0;
}
 
// Recursive function definition
int gcd(int a, int b) {
    if (b == 0)
        return a;              // Base case
    else
        return gcd(b, a % b);  // Recursive call
}

 
OUTPUT 1 :
Enter two positive integers: 48 18
GCD of 48 and 18 is 6

OUTPUT 2 :

 

Explanation

1. Recursive Logic
   • The function keeps calling itself with smaller values:

gcd(a, b) = gcd(b, a % b)

until b becomes 0.

2. Base Case
   • When b == 0, the recursion stops, and a is returned as the GCD.
3. Example Trace

            gcd(48, 18)

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

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

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

             → return 6