I'm coming from a programming aspect of this issue. So in Scheme code
(define (gcd a b)
(if (= b 0)
a
(gcd b (modulo a b))))
works and uses recursion, i.e., the ...(gcd b (modulo a b))))
recursively calls the function gcd
again (and again) until the condition b = 0
is met, to give the answer a
. So to use this function (gcd 12 20)
gives 4
.
Now, if I do this for more than two numbers, say $2, 12, 20, 120$
(gcd 2 (gcd 21 (gcd (20 120))))
I get the right answer too, i.e., 2
. Can someone tell me why this is working correctly from a math standpoint?
On Wikipedia's Euclidean Algorithm article, it says
The GCD of three or more numbers equals the product of the prime
factors common to all the numbers,[11] but it can also be calculated
by repeatedly taking the GCDs of pairs of numbers.[12] For example,
gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)
I'm guessing it has something to do with the commutable "product of all prime factors." But still, this is recursion inside of recursion pair-wise. Why does this work?
No comments:
Post a Comment