The gcd(m, n) can also be defined recursively as follows:

Question

• If m % n is 0, gcd (m, n) is n.
• Otherwise, gcd(m, n) is gcd(n, m % n).

Write a recursive function to find the GCD. Write a test program that computes gcd(24, 16) and gcd(255, 25).

Answer 1

```
#include
using namespace std;

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

int main()
{
// Enter the first number
cout << "Enter the first number: ";
int m;
cin >> m;

// Enter the first number
cout << "Enter the second number: ";
int n;
cin >> n;

cout << "The GCD of " << m << " and " << n << " is " <<
gcd(m, n) << endl;

return 0;
}
```