用Java计算gcd

Question

我正在自学Java,所以我正在从加州大学伯克利分校CS 61B做实验.我正在尝试编写一个gcd方法来使我的toString方法工作.

toString方法以非简化形式打印Fraction.检查toString方法中的代码.它正在调用另一个名为gcd的方法,它计算两个正整数的最大公约数(GCD).如果此方法正常工作,toString将以缩小的形式打印分数.我必须重写gcd的主体,以便它是一个正确计算GCD的递归函数.

这是我的toString方法:

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

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

我的目标是编写正确的gcd函数,以便toString以不可缩减的形式返回一个fracyion.这是我写的:

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

        }
    }

}

说明是关于使用以下伪代码编写递归gcd函数,但我不确定如何完全实现它:

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

我的gcd功能有什么问题？我如何让我的工作？我将如何编写递归函数？

Answer 1

为什么不遵循说明？

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

此函数称为尾递归,因为最后一行是递归调用.尾递归函数很容易转换为while循环:

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

正如您所看到的,转换使得while循环谓词等于谓词来调用递归函数,而while循环的内容只是将x和y设置为与递归函数的输入相同.这一般是正确的(参见维基文章).