Java 程序：使用递归寻找最大公约数

要理解这个示例，你应该具备以下 Java 编程 主题的知识：

• Java 方法
• Java 递归

这个程序接收两个正整数并使用递归计算它们的最大公约数（GCD）。

访问此页面了解如何使用循环计算最大公约数（GCD）。

示例：使用递归计算两个数字的最大公约数

public class GCD {

    public static void main(String[] args) {
        int n1 = 366, n2 = 60;
        int hcf = hcf(n1, n2);

        System.out.printf("%d 和 %d 的最大公约数是 %d。", n1, n2, hcf);
    }

    public static int hcf(int n1, int n2)
    {
        if (n2 != 0)
            return hcf(n2, n1 % n2);
        else
            return n1;
    }
}

输出

366 和 60 的最大公约数是 6。

在上述程序中，递归函数一直被调用，直到 n2 为 0。最终，n1 的值是给定两个数字的最大公约数（GCD）或最高公因数（HCF）。

执行步骤

序号	递归调用	n1	n2	n1 % n2
1	hcf(366, 60)	366	60	6
2	hcf(60, 6)	60	6	0
最终	hcf(6, 0)	6	0	-