Computing gcd in Java

Question

I am teaching myself Java so I am doing labs from UC Berkeley CS 61B. I am trying to write a gcd method to make my toString method work.

the toString method prints a Fraction in non-reduced form. Examine the code in the toString method. It is calling another method called gcd that computes the greatest common divisor (GCD) of two positive integers. If this method worked correctly, toString would print Fractions in reduced form. I have to rewrite the body of gcd so that it is a recursive function that correctly computes the GCD.

Here is my toString method:

public String toString() {
    int thisGcd = gcd(numerator, denominator);

    return (numerator / thisGcd + "/" + denominator / thisGcd);
  }

My goal is to write the correct gcd function so that toString returns a fracyion in irreductible form. Here is what I wrote:

private static int gcd(int x, int y) {
    int div;
    if(x<0 || y<0){
        return -1;
    }
    else {

        if(x>y){
            div = y ;
        }
        else{
            div = x;
        }
        while( div !=0){
            if( (x % div==0 )&&(y % div == 0) ) {
                return div;

            }
            div --;

        }
    }

}

The instructions were about writing a recursive gcd function with the following pseudocode but I am not sure how to implement it exactly:

function gcd(a, b)
if b = 0
  return a
else
  return gcd(b, a mod b)

What is wrong with my gcd function ? How do I make mine work ? And how would I write the recursive function ?

Answer 1

Why not follow the instructions?

private static int gcd(int x, int y) {
  if (y == 0) {
    return x;
  }
  return gcd(y, x % y);
}

This function is called tail-recursive because the last line is a recursive call. Tail recursive functions are very easy to transform into while loops:

private static int gcd(int x, int y) {
  while (y != 0) {
    int tempX = x;
    x = y;
    y = tempX % y;
  }
  return x;
}

As you can see the transformation makes the while loop predicate equal the predicate to call the recursive function and the contents of the while loop are just setting x and y to be the same as the input to the recursive function. This is true in general (see wiki article).

Answer 2

Recursive function:

public int gcd(int a, int b)
{
 if(b == 0) return a;
 else return gcd(b, a % b);
}