java - 编写一个使用递归找到两个整数之间的最大公约数的方法？

Question

Euclid 算法告诉我们如何计算两个正整数和的最大公约数(GCD) 。使用欧几里得算法，求 和 的 GCD （例如），首先求除以时的余数。然后再次使用相同的想法找到 和这个余数（结果是）的 GCD 。当您到达第二个数字为 的点时，第一个数字将是您要查找的 GCD ， 如下所示。ab2064020640406020640

gcd(206, 40)
= gcd(40, 6)
= gcd(6, 4)
= gcd(4, 2)
= gcd(2, 0)
= 2

编写一个名为gcd. 您必须在此方法中使用递归（在方法中调用方法）。此方法应使用欧几里得算法返回两个正整数的最大公约数。

所以基本上我不知道如何用递归来做到这一点（对不起，我之前没有意外写过）递归..请帮忙！:(我已经坚持了这么久..我写了一个方法，但它不使用递归，它只适用于给定的206和40..

Answer 1

使用递归很容易实现：

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

该算法在此Wikipedia 页面中进行了说明。