辗转相除法的最简形态

用最简单的代码求最大公约数
直入主题：

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

a一定要比b大吗？

完全不需要

这也是欧几里得算法（辗转相除法）最神奇、最“智能”的地方：它自带自动纠正（Auto-Swap） 功能。
不管你传进去的是 gcd(大, 小) 还是 gcd(小, 大)，结果完全一样，代码不需要做任何修改。

为什么不需要？

如果在第一次调用时，a 比 b 小（比如 a=10, b=25），% 运算会产生一个神奇的效果：
因为在数学中，如果被除数比除数小，余数就是被除数本身。 即：10 % 25 = 10。
让我们来看看如果把小的数放前面，程序会怎么跑：

场景演示：gcd(10, 25)

  • 第 1 轮： 调用 gcd(10, 25)
    • a = 10, b = 25
    • 计算 a % b -> 10 % 25 = 10
    • 执行递归：gcd(25, 10)
    • 看！ 仅仅经过一步，两个数字的位置就自动互换 了，变成“大数在前，小数在后”了。
  • 后面就一样了

用途：

  • 化简分式，6/9—>2/3（最大公约数为3）