void swap(int& a, int& b)
{ int temp = a; a = b; b = temp; }
int gcd(int a, int b){
assert (a || b);
if ( a < 0 ) a = -a;
if ( b < 0 ) b = -b;
if ( a < b ) swap(a,b); // Force a >= b.
if ( b == 0 ) return a;
int r = a%b;
if (r == 0) return b;
else return gcd(b, r);
}
Notation. If a % b == 0, then a
is divisible by b, and we say that "b divides a".
What this means is that there exists an integer q such that
a == q*b.
First, the function enforces the precondition a >=b. The greatest common divisor (gcd) of two integers is the same as the gcd of their absolute values. Therefore, the function can just replace negative integers by their negatives, which are positive.
Next, the function checks for the base case of the recursion: gcd(a,0) == a, because every number divides 0 (zero is divisible by every integer, but nothing is divisible by zero).
Finally, the function proceeds by recursion. It reduces its given problem to a smaller, equivalent problem, using the fact that if a = q*b + r for integers q and r, with 0 <= r < b, then gcd(a,b) == gcd(b,r). Because 0 <= b < a and 0 <= r < b, r gets smaller at each step, but never becomes negative. Therefore, this recursion must eventually terminate with r== 0.
Here is why gcd(a,b) == gcd(b,r). Let g denote the gcd of a and b. (We don't know the value of g yet, but we do know that it must exist --- we could use a slow algorithm to compute it, like comparing all the divisors of a to all the divisors of b and taking the largest common one.) Divide a by b and get the quotient q and the remainder r; i.e., a == q*b + r. Now, because g divides a and g divides b, there exist integers c and d such that a == g*c and b == g*d. Substituting in a == q*b + r, we get g*c == q*g*d + r, or g*c - q*g*d == r, and so g*(c - q*d) == r, and so r is necessarily a multiple of g as well. Therefore, g divides both b and r. It must be the greatest common divisor of b and r, because, by similar reasoning to the above, any common divisor of b and r must be a common divisor of a and b. (Suppose h > g and b == e*h and r == f*h some integers e and f. Then
a == q*b + r == q*e*h + f*h == h*(q*e+f),so a is also a multiple of h. Thus if g weren't the gcd of b and r, then g would not be the greatest common divisor of a and b, a contradiction. Therefore, the gcd of b and r is the same as the gcd of a and b.
Remarks.