CODEWITHSUNDEEP
java
mino
mino

Reputation: 7288

Java - Recursive function of the Euclidean Algorithm

I can't seem to convert the following algorithm into Java successfully, please forgive the horrible picture quality but a question I'm working on asks:

Euclidean Algorithm

I have tried to use the following code to represent the Euclidean Algorithm, but it doesn't seem to work. I don't really know how I would go about representing it in Java code. Any help?

public static int gcd(int x, int y) {
    if (y == 0) {
        return x;
    } else if (x >= y && y > 0) {
        return gcd(y, (x % y));
    }
}

Thank you.

Upvotes: 3

Views: 23451

Answers (5)

Sean Rogers
Sean Rogers

Reputation: 499

Here's what I have that accounts for negative numbers:

public static int gcd(int x, int y)
{
    if (y == 0)
        return x;
    if (x < 0)
        return gcd(x * -1, y); //turns the first parameter to a positive if it's initally negative
    if (y < 0)
        return gcd(x, y * -1); //turns the second parameter to a positive if it's initally negative
    if (y <= x && x % y == 0)
        return y;

    return gcd(y, x%y);
}

Note with negative numbers, if you try to find the greatest common divisor, and either of the numbers is negative, you can just change it to a positive and the result would be the same.

If both of the numbers are negative, then I'm not sure what the gcd should be. 1? -1? idk so I left that out. The code I have just treats it as if they were both positive.

Upvotes: 0

勿绮语
勿绮语

Reputation: 9330

There is no arbitrary order between x and y.

Upvotes: 6

Kaushik Shankar
Kaushik Shankar

Reputation: 5619

Your code is not complete!

What if x < y? Your code does not return a value then!

What the book fails to mention is that the two parameters to the function do not necessarily need to be in descending order (ie x >= y). What you need to do is compute the gcd considering this fact.

Simply you can do the following:

public static int gcd ( int x , int y )
{
    if ( y == 0 )                        
        return x;
    else if ( x >= y && y > 0)
        return gcd ( y , x % y );
    else return gcd ( y , x );        // if x < y then go ahead and switch them around.
}

Upvotes: 5

Alexander Pogrebnyak
Alexander Pogrebnyak

Reputation: 45596

You are almost there.

Your code does not compile, because there is no catch all clause that return from the function.

It really depends on whether you are going to pass negative values of y into this function. If you expect only positive values, just throw an exception.

public static int gcd(int x, int y) {

    if (y == 0) {

        return x;

    } else if (x >= y && y > 0) {

        return gcd(y, (x % y));

    }

    throw
        new IllegalArgumentException(
            String.format(
                "Unexpected values for x(%d) and y(%d)",
                Integer.valueOf( x ),
                Integer.valueOf( y )
            )
        );
}

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726919

You are almost there. You need to consider what happens when y > x, and return the result from the final else branch (hint: x and y can freely switch places).

Upvotes: 2

Related Questions