java - 对于某些测试用例，函数没有在正确的返回语句中返回

Question

这是我的代码。

问题: 我得到的测试用例输出不正确:a=100 b=54。

发现问题: 为什么调用方法 computeGcd 中的第一个 if 条件时(即当 a==b 或 a 可以被 b 整除)它不会从这个 if block 返回到调用它的 main 方法中的那一行？

相反，它会转到方法中的最后一个 return 语句，并从那里返回 'b' 的旧值。我错过了什么？

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if (a >= b) {
        System.out.println("\n\nfinal values are: " + computeGcd(a, b) 
                + " for a is=" + a + " and b=" + b);}
    else
        System.out.println(computeGcd(b, a));
    sc.close();
}

public static int computeGcd(int a, int b) {
    System.out.println("out side a is=" + a + " and b=" + b);
    if (a == b || a % b == 0) {
        System.out.println("Inside final : a is=" + a + " and b=" + b);
        return b;
    } else {
        a = (a - b * (a / b));
        if (a > b) {
            System.out.println("Inside test a>b : a is=" + a + " and b=" + b);
            computeGcd(a, b);
        }
        if (b > a) {
            System.out.println("Inside test a<b : a is=" + a + " and b=" + b);
            computeGcd(b, a);
        } 
    }
    System.out.println("exiting else");
    System.out.println("i m here :P ");
    return b;
}

调试测试用例:100 54

Answer 1

您的递归调用不会返回。

if (a > b) {
    System.out.println("Inside test a>b : a is=" + a + " and b=" + b);
    return computeGcd(a, b); // <-- add return
} else { // if (b > a) {
    System.out.println("Inside test a<b : a is=" + a + " and b=" + b);
    return computeGcd(b, a); // <-- add return
}

或者

最大可能的 gcd 是两项中最小值的平方根。您可以从该值开始并向后迭代。类似的东西，

public static int computeGcd(int a, int b) {
    if (a == b) {
        return a;
    }
    for (int i = (int) Math.sqrt(Math.min(a, b)); i >= 2; i--) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}

返回 2(对于 100, 54)，因为 54 的一半是 27，即 3 ³ 唯一的共同点是 2 和 1。