CODEWITHSUNDEEP
crecursion
Qwe Rty
Qwe Rty

Reputation: 1

Recursion in C. Making a non-recursive function a recursive one

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;
    }
}
}

Upvotes: 0

Views: 719

Answers (3)

SomeWittyUsername
SomeWittyUsername

Reputation: 18368

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.

Upvotes: 6

Raymond Chen
Raymond Chen

Reputation: 45172

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.

Upvotes: 1

hqt
hqt

Reputation: 30284

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.

Upvotes: 2

Related Questions