# Recursive GCD Function

## Program Listing

• This program uses a recursive function to compute the GCD of a pair of integers.

### RecursiveGCD.cpp

 ```/**************************************************************************** * * * Program: RecursiveGCD * * * * Purpose: This program will test the GCD() and LCM() functions * * * ****************************************************************************/ // Header files #include #include #include using namespace std; // Functions prototypes int GCD(int a, int b); int LCM(int a, int b); /**************************************************************************** * * * Function: main * * * * Purpose: To test the GCD() and LCM() functions * * * ****************************************************************************/ int main() { // Get two integers from the user cout << "Enter two integers: " << flush; int x, y; // Two integers for the test cin >> x >> y; // Find the greatest common divisor and print it int div = GCD(x, y); // Get the g.c.d. cout << "The g.c.d. of " << x << " and " << y << " is " << div << endl; // Find the least common multiple and print it int mult = LCM(x, y); // Get the l.c.m. cout << "The l.c.m. of " << x << " and " << y << " is " << mult << endl; return 0; } /**************************************************************************** * * * Function: GCD * * * * Purpose: To find the greatest common divisor of two integers * * * * Note: This function computes the GCD recursively * * * ****************************************************************************/ int GCD(int a, int b) { // Make sure integers are nonnegative a = abs(a); // Make first int nonneg b = abs(b); // Make second int nonneg // Make sure at least one of them is positive if (b == 0) // Divisor is zero return a; // Return other integer else // Divisor is nonzero return GCD(b, a % b); // Continue Euclidean algorithm } /**************************************************************************** * * * Function: LCM * * * * Purpose: To find the least common multiple of two integers * * * * Note: This function uses the GCD to find the LCM * * * ****************************************************************************/ int LCM(int a, int b) { // Make sure a and b are not both 0 if (a == 0 && b == 0) return 0; else return (a*b)/GCD(a, b); } ```

### Sample Run

 ```Enter two integers: 321 987 The g.c.d. of 321 and 987 is 3 The l.c.m. of 321 and 987 is 105609 ```