TIPS COM

In this program we will use recursion and Euclids algorithm to find greatest common divisor of two numbers. The definition of Euclids algorithm is as follows:

Also Read: C program to find factorial of any number using recursion
Also Read: How to Convert a Recursive Function or Algorithm to Non-Recursive?

C Program

#include<stdio.h>

int gcd(int n,int m)
{
    if((n>=m)&&((n%m)==0))
        return(m);
    else
        gcd(m,(n%m));
}

int main()
{
    int n,m,result;
    printf("Input the first integer number:");
    scanf("%d",&n);
    printf("Input the second integer number:");
    scanf("%d",&m);
    result=gcd(n,m);
    printf("
GCD of %d and %d is %d",n,m,result);

    return 0;
}

C++ Program

#include<iostream>
#include<cstdlib>

using namespace std;

int gcd(int n,int m)
{
    if((n>=m)&&((n%m)==0))
        return(m);
    else
        gcd(m,(n%m));
}

int main()
{
    int n,m,result;
    cout<<"Input the first integer number:";
    cin>>n;
    cout<<"Input the second integer number:";
    cin>>m;
    result=gcd(n,m);
    cout<<"
GCD of "<<n<<" and "<<m<<" is "<<result;

    return 0;
}