C Program to Find GCD of Two Numbers Using Recursion

In this post, we will learn how to find GCD of two numbers using recursion in C Programming language.

C Program to Find GCD of Two Numbers Using Recursion

The greatest common divisor (GCD) of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b.

We will define a custom recursive function which will calculate the GCD of two numbers.

So, without further ado, let’s begin this tutorial.

C Program to Find GCD of Two Numbers Using Recursion

// C Program To Find GCD of Two Number Using Recursion
#include <stdio.h>
int GCD(int x, int y);
int main(){
    int a, b;
    
    // Asking for Input
    printf("Enter Two Positive Integers: \n");
    scanf("%d\n %d", &a, &b);
    
    printf("GCD of %d and %d is %d.", a, b, GCD(a, b));
    return 0;
}

int GCD(int x, int y){
    if( y != 0)
        return GCD(y, x % y);
    else 
        return x;
}

Output

Enter Two Positive Integers: 
40
412
GCD of 40 and 412 is 4.

How Does This Program Work ?

    int a, b;

In this program, we have declared two int data type variables named as a and b.

    // Asking for Input
    printf("Enter Two Positive Integers: \n");
    scanf("%d\n %d", &a, &b);

Then, the user is asked to enter the value of two integers. The value of these two integers will get stored in a and b respectively.

    printf("GCD of %d and %d is %d.", a, b, GCD(a, b));

We print the GCD of two numbers using printf() function. Here, we called our custom function which will calculate the GCD of two numbers.

int GCD(int x, int y){
    if( y != 0)
        return GCD(y, x % y);
    else 
        return x;
}

We have declared a recursive function named GCD which will compute and return the GCD of two numbers.

Conclusion

I hope after going through this post, you understand how to find gcd of two numbers using recursion in C Programming language.

If you have any doubt regarding the program, feel free to contact us in the comment section. We will be delighted to help you

Also Read:

Leave a Comment

Your email address will not be published.