gcd should be a recursive function. It should return void. It should take two positive integers and place the GCD in the third parameter.
Here is my coded gcd function. However, I realized that it is not a recursive function. How would I change this code so it is a recursive function?
void gcd(int *x, int *y) {
int i;
getValuesForGCD(x, y);
for (i = *x; i >= 1; i--)
{
if (*x % i == 0 && *y % i == 0)
{
printf("The GCD of %d and %d is %d", *x, *y, i);
break;
}
}
}
GCD is naturally defined as a recurrent formulae. It's straightforwardly transformed into a recursive function:
gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
Write this in a C format and that's it.
int gcd(int a, int b) {
if (b == 0)
then return a
else return gcd(b, a % b);
}
You should notice that a and b must be non-negative number.
and the nice thing is, this is a tail-recursion, so it run as fast as non-recursive method.
Normally, people work to remove recursion, not introduce it.
If you want a literal conversion of your iterative algorithm to recursive, it would go like this:
void gcdrecursive(int *x, int *y, int i)
{
if (i >= 1) {
if (*x % i == 0 && *y % i == 0) {
printf("The GCD of %d and %d is %d", *x, *y, i);
} else {
gcdrecursive(x, y, i - 1);
}
}
}
void gcd(int *x, int *y) {
getValuesForGCD(x, y);
gcdrecursive(x, y, *x);
}
To convert an iterative solution to recursive, you convert each loop to a recursive function that performs one iteration of the loop, then calls itself recursively for the next iteration. Breaking the loop corresponds to stopping the recursion. In your example, the loop breaks for two reasons: Either the GCD is found or i reaches zero.
Note that this is not the best algorithm for gcd, but it takes the function you provided and converts it to recursive, as requested.
istart from min(x,y).gcdis one of them. Although, in this case it's probably a hw...