Logic behind greatest common denominator algorithm [duplicate]
Can someone explain why we compare b to zero then swap it as a in the argument? What is the reason behind this approach? I am having a hard time understanding this algorithm.
public int gcd(int a, int b) {
if (b==0) return a;
return gcd(b,a%b);
}
Solution 1:
From what I understand, it is a principle called Euclidean algorithm. The Greatest Common Denominator of two values does not change if the larger is replaced by its difference with the smaller value. GCD is the largest positive value that divides two or more values without leaving a remainder.