欧几里德算法如何工作？
我刚刚发现这个算法来计算我的讲义中最大的公约数：
public static int gcd( int a, int b ) { while (b != 0) { final int r = a % b; a = b; b = r; } return a; } 所以r是将b分成a （得到mod）时的余数。 然后将b分配给a ，将余数分配给b ，并返回a。 我不能为我的生活看到它是如何运作的！
然后，显然这个算法不适用于所有情况，然后必须使用这个：
public static int gcd( int a, int b ) { final int gcd; if (b != 0) { final int q = a / b; final int r = a % b; // a == r + q * b AND r == a - q * b. gcd = gcd( b, r ); } else { gcd = a; } return gcd; }
我不明白这背后的原因。 我通常得到递归并且擅长Java，但这是在逃避我。 请帮助？
维基百科的文章包含一个解释，但要立即找到它并不容易（同时，程序+certificate并不总是回答“为什么它有用”的问题）。
基本上，它归结为这样的事实：对于两个整数a，b（假设a> = b），总是可以写a = bq + r，其中r 如果d = gcd（a，b），那么我们可以写a = ds和b = dt。 所以我们有ds = qdt + r。 由于左侧可被d整除，因此右侧也必须可被d整除。 由于qdt可被d整除，因此结论是r也必须能被d整除。 总结一下：我们有一个= bq + r，其中r 由于a> = b> r，我们有两种情况： 为什么减少？ 因为r 现在，r = a％b，希望能解释你的代码。
他们是等同的。 首先要注意的是，第二个程序中的q根本没有使用。 另一个区别是迭代与递归。
至于它的工作原理，上面链接的维基百科页面很好。 特别是第一个插图有效地直观地表达了“为什么”，然后下面的动画说明了“如何”。
鉴于从未使用’q’，我没有看到你的普通迭代函数和递归迭代函数之间的区别…两者都做
gdc(first number, second number) as long as (second number > 0) { int remainder = first % second; gcd = try(second as first, remainder as second); } }
除非尝试将此应用于非整数，否则此算法会失败？
（有关详细信息，请参阅http://en.wikipedia.org/wiki/Euclidean_algorithm ）
这是一篇有趣的博客文章： Tominology 。
在讨论欧几里德算法背后的许多直觉的地方，它是用JavaScript实现的，但我相信如果想要的话，将代码转换为Java并不困难。
这是我发现的一个非常有用的解释。
对于那些懒得打开它的人来说，这就是它所说的：
当你必须找到（3084,1424）的GCD时，请考虑这个例子。 让我们假设d是GCD。 这意味着d | 3084和d | 1424（使用符号’|’表示’divides’）。
由此得出d | （3084 – 1424）。 现在我们将尝试尽可能减少这些可被d整除的数字（在本例中为3084和1024），以便我们将0作为数字之一。 请记住，GCD（a，0）是一个。
因为d | （3084 – 1424），它遵循d | （3084-2（1424）），这意味着d | 236。
提示：（3084 – 2 * 1424 = 236）
现在忘记初始数字，我们只需要求解d，并且我们知道d是划分236,1424和3084的最大数。所以我们使用较小的两个数来继续，因为它会将问题收敛到0 。
d | 1424和d | 236意味着d | （1424 – 236）。
所以，d | （1424 – 6（236））=> d | 8。
现在我们知道d是划分8,236,1424和3084的最大数字。再次采用较小的数字，我们有
d | 236和d | 8，暗示d | （236 – 8）。
所以，d | （236 – 29（8））=> d | 4。
同样可被d整除的数字列表会增加并收敛（数字越来越小，越接近0）。 就目前而言，d是划分4,8,236,1424,3084的最大数字。
采取相同的步骤，
d | 8和d | 4意味着d | （8-4）。
所以，d | （8 – 2（4））=> d | 0。
可被d整除的数字列表现在为0,4,8,236,1484,3084。（a，0）的GCD始终为a。 所以，一旦你将0作为两个数字中的一个，另一个数字是原始的两个gcd和所有介于两者之间的数字。
这正是您的代码正在做的事情。 您可以将终端条件识别为GCD（a，0）= a。
另一步是找到两个数字的其余部分，然后选择它和前两个中较小的数字作为新数字。