How to do it…

The int gcd(int x, int y) recursive function finds the GCD of two integers, x and y, using the following three rules:

• If y=0, the GCD of x and y is x.
• If x mod y is 0, the GCD of x and y is y.
• Otherwise, the GCD of x and y is gcd(y, (x mod y)).

Follow the given steps to find the GCD of two integers recursively:

1. You will be prompted to enter two integers. Assign the integers entered to two variables, u and v:

printf("Enter two numbers: ");
scanf("%d %d",&x,&y);

2. Invoke the gcd function and pass the x and y values to it. The x and y values will be assigned to the a and b parameters, respectively. Assign the GCD value returned by the gcd function to the g variable:

g=gcd(x,y);

3. In the gcd function, a % b is executed. The % (mod) operator divides the number and returns the remainder:

m=a%b;

4. If the remainder is non-zero, call the gcd function again, but this time the arguments will be gcd(b,a % b), that is, gcd(b,m), where m stands for the mod operation:

gcd(b,m);

5. If this again results in a non-zero remainder, that is, if b % m is non-zero, repeat the gcd function with the new values obtained from the previous execution:

gcd(b,m);

6. If the result of b % m is zero, b is the GCD of the supplied arguments and is returned back to the main function:

return(b);

7. The result, b, that is returned back to the main function is assigned to the g variable, which is then displayed on the screen:

printf("Greatest Common Divisor of %d and %d is %d",x,y,g);

The gcd.c program explains how the greatest common divisor of two integers is computed through the recursive function:

#include <stdio.h>
int gcd(int p, int q);
void main()
{
    int x,y,g;
    printf("Enter two numbers: ");
    scanf("%d %d",&x,&y);
    g=gcd(x,y);
    printf("Greatest Common Divisor of %d and %d is %d",x,y,g);
}
int gcd(int a, int b)
{
    int m;
    m=a%b;
    if(m==0)
        return(b);
    else
        gcd(b,m);
}

Now, let's go behind the scenes.