使用递归查找最大公约数的 Java 程序

在本程序中，您将学习使用 Java 中的递归函数查找最大公约数。

要理解此示例，您应该具备以下 Java 编程的知识：

Java 方法
Java 递归

在前面的文章，我们了解了如何使用循环计算最大公约数。而下面的程序采用递归计算两个正整数的最大公约数。

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

public class最大公约数{

    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。

在上面的程序中， hcf 函数是一个递归函数，因为他在函数的内部调用了自己。函数一致被递归调用，直到 n2 为 0。最后 n1 的值就是给定两个数的最大公约数。

执行步骤

#	递归调用	`n1`	`n2`	`n1 % n2`
1	`hcf(366, 60)`	`366`	`60`	`6`
2	`hcf(60, 6)`	`60`	`6`	`0`
…	`hcf(6, 0)`	`6`	`0`	`-`