Recursive Greatest Common Divisor using C Programming

The greatest common divisor of integers x and y is the largest integer that evenly divides both x and y. Write a recursive function gcd that returns the greatest common divisor of x and y. The gcd of x and y is defined recursively as follows: If y is equal to 0, then gcd(x, y) is x; otherwise gcd(x, y) is gcd(y, x % y) where % is the remainder operator.

Answer:

#include <stdio.h>

// function prototype 
unsigned int gcd( unsigned int xMatch, unsigned int yMatch );

int main()
{ 
   unsigned int x; // first integer 
   unsigned int y; // second integer 
   unsigned int gcDiv; // greatest common divisor of x and y 

   printf( "%s", "Enter two integers: " );
   scanf( "%u%u", &x, &y );

   gcDiv = gcd( x, y );

   printf( "Greatest common divisor of %u and %u is %u\n",
          x, y, gcDiv );
} // end main 

// gcd recursively finds greatest common divisor  
// of xMatch and yMatch 
unsigned int gcd( unsigned int xMatch, unsigned int yMatch )
{ 

   // base case 
   if ( 0 == yMatch ) {
      return xMatch;
   } // end if 
   else { // recursive step 
      return gcd( yMatch, xMatch % yMatch );
   } // end else 
} // end function gcd