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

Question

我正在使用 euclids 算法的简化版本来查找两个整数的 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;
 }  
}

Answer 1

当你找到最大公约数时，你最终会传入 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);
}