Java:为什么欧几里得GCD函数返回不正确的值

Question

我对编程很陌生，我正在使用Think学习Java。我正试着做第六章实践10。本练习涉及使用欧几里德算法编写求最大公因子(GCD)的递归函数。我想出了两个主意。我不知道为什么我的第二个想法返回一个不正确的值。

这个想法工作得很好：

public class exercise10 {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        else return gcd(b, a % b);
    }
    public static void main(String[] arguments){
        System.out.println(gcd(36,20));
    }
}

此想法返回一个不正确的值：

public class exercise10 {
    public static int gcd(int a, int b) {
        if (b > 0) {
            int r = a % b;
            gcd(b, r);
        }
        return a;
    }
    public static void main(String[] arguments){
        System.out.println(gcd(36,20));
    }

}

这不是任何课堂作业的一部分。我只是简单地使用开源教科书来自学java。

在Win64机器上运行java版本

Answer 1

BorisTheSpider指出了我的代码出了什么问题，但他的帖子不知何故被删除了。总之，他指出，我的第二个想法是在递归函数return前面缺少一个gcd(b, r)语句。

public class exercise10 {
    public static int gcd(int a, int b) {
        if (b > 0) {
            int r = a % b;
            gcd(b, r); <--- missing return
        }
        return a;
    }
    public static void main(String[] arguments){
        System.out.println(gcd(36,20));
    }

}

所以正确的代码应该是：

public class exercise10 {
    public static int gcd(int a, int b) {
        if (b > 0) {
            int r = a % b;
            return gcd(b, r);
        }
        return a;
    }
    public static void main(String[] arguments){
        System.out.println(gcd(36,20));
    }

}

贷给BorisTheSpider.