(Recursive Greatest Common Divisor) 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, 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 modulus operator. [Note: For this algo- rithm, x must be larger than y.]

Question

What will be an ideal response?

Answer 1

```
// Recursive greatest common divisor.
#include
using namespace std;

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

int main()
{
unsigned x; // first integer
unsigned y; // second integer

cout << "Enter two integers: ";
cin >> x >> y;

cout << "Greatest common divisor of " << x << " and "
<< y << " is " << gcd( x, y ) << endl;
} // end main

// gcd recursively finds greatest common divisor of a and b
unsigned gcd( unsigned a, unsigned b )
{
if ( b == 0 ) // base case
return a;
else // recursion step
return gcd( b, a % b );
} // end function gcd
```