SICP

Greatest Common Divisors

欧几里得算法（Euclid’s Algorithm.） 求 最大公约数
The idea of the algorithm is based on the observation that, if r is the remainder(余数：整数除法中被除数未被除尽部分) when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r. Thus, we can use the equation:
GCD(a,b)=GCD(b,r)
to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example:
GCD(206,40) = GCD(40,6) = GCD(6,4) = GCD(4,2) = GCD(2,0) = 2
a 除以 b 后的余数 r，r 与 b 的最大公约数 与 a 与 b 的最大公约数 相等。

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