title: Computing gcd in Java
body: <p>I am teaching myself Java so I am doing labs from UC Berkeley <a href="http://www.cs.berkeley.edu/~jrs/61b/lab/lab2/" rel="nofollow">CS 61B</a>. I am trying to write a gcd method to make my toString method work.</p>
  
  <p>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.</p>
  
  <p>Here is my toString method:</p>
  
  <pre><code>public String toString() {
      int thisGcd = gcd(numerator, denominator);
  
      return (numerator / thisGcd + "/" + denominator / thisGcd);
    }
  </code></pre>
  
  <p>My goal is to write the correct gcd function so that toString returns a fracyion in irreductible form. Here is what I wrote:</p>
  
  <pre><code>private static int gcd(int x, int y) {
      int div;
      if(x&lt;0 || y&lt;0){
          return -1;
      }
      else {
  
          if(x&gt;y){
              div = y ;
          }
          else{
              div = x;
          }
          while( div !=0){
              if( (x % div==0 )&amp;&amp;(y % div == 0) ) {
                  return div;
  
              }
              div --;
  
          }
      }
  
  }
  </code></pre>
  
  <p>The instructions were about writing a recursive gcd function with the following pseudocode but I am not sure how to implement it exactly:</p>
  
  <pre><code>function gcd(a, b)
  if b = 0
    return a
  else
    return gcd(b, a mod b)
  </code></pre>
  
  <p>What is wrong with my gcd function ? How do I make mine work ? And how would I write the recursive function ? </p>