java - 实现递归函数以查找HCF/GCD Java

我正在使用euclids algorythm的简化版本来查找两个整数的hcf。使用递归函数。似乎没有用，它总是一直返回c。任何想法为什么它最终不返回a + b？

 public class Euclid {

  public static void main(String[] args) {
    // TODO Class to find HCF (GCD) of two ints, using recursion

    Euclid r = new Euclid();
    System.out.println(r.hcf(188, 112));
  }

  public int hcf(int a, int b){
   int c = -11;
    if(a == 0 || b == 0){
      return a+b; // base case
    }
    else if (a > b){
      return hcf(a-b, b);
    }
    else if (b > a){
      return hcf(b-a, a);
    }
  return c;
 }
}

最佳答案

当您找到最大公约数时，您最终将a和b传递为a==b。您不处理这种情况，因此返回c。

一个简单的解决方法是只删除最后一个if分支，以便在那里处理a==b情况。

if(a == 0 || b == 0){
   return a+b; // base case
}
else if (a > b){
   return hcf(a-b, b);
}
else { // b > a or a == b
   return hcf(b-a, a);
}