CODEWITHSUNDEEP
javascriptmath
user3808307
user3808307

Reputation: 1549

Why does this function to obtain maximum common divisor does not compare which numer is greater

I am looking at examples of common divisor functions.

I see this one using Euclid's algorithm

var gcd = function(a, b) {  
    if (b == 0) {
        return a;
    }
return gcd(b, a % b);
};

console.log(gcd(126,553443));

But why does it not compare which number is the greatest between a and b before doing the first recursive call?

I mean, why is not

if (a > b)
  return gcd(a, b % a); 
else
  return gcd(b, a % b);

Here is another example. I don't see where the swapping is taking place

Upvotes: 0

Views: 54

Answers (1)

Pointy
Pointy

Reputation: 413712

If a is less than b, then a % b will be a. Thus on the next iteration, a will be smaller than b.

Try it. 12 % 20 is 12 because the quotient is 0, and the remainder is 12.

Upvotes: 1

Related Questions