Java 递归算法求最大公约数 (GCD) 示例

本文将展示使用 Java 递归方法求解两个正整数的最大公约数 (GCD) 的示例代码。

public class GCDRecursiveExample {
    public static int gcd(int m, int n) {
        if (n == 0) {
            return m;
        } else {
            return gcd(n, m % n);
        }
    }
    
    public static void main(String[] args) {
        int m = 48;
        int n = 36;
        
        int result = gcd(m, n);
        
        System.out.println('最大公约数为：' + result);
    }
}

在上述代码中，我们定义了 gcd() 方法，使用递归的方式来求解最大公约数。在每一次递归中，我们判断如果 n 等于 0，则直接返回 m；否则，我们将 n 和 m 对 n 取模的结果作为参数再次调用 gcd() 方法。这样，递归持续进行直到找到最大公约数。

在 main() 方法中，我们定义了两个正整数 m 和 n，并调用 gcd() 方法来求解它们的最大公约数。最后，我们将结果输出。

运行该程序，输出结果如下：

最大公约数为：12

这表明正整数 48 和 36 的最大公约数是 12。验证了递归方法求最大公约数的正确性。