GCD

[funprogrammer]

What is wrong with this GCD program?

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

If I change return gcd(b,b%a) to return gcd(b,a%b) it works. In the examples I am trying both the algorithms work, but when I use this gcd method on online coding problem, return gcd(b,a%b) works but not the other. Can someone throw some light and provide an example where return gcd(b,b%a) fails?

[kevinkjt2000]

Possibly if a is 0, b%a would fail. Whereas in a%b, b cannot be 0 because of the return statement in if(b==0).

[funprogrammer]

Wow, good point @kevinkjt2000. That explains thanks :)

[anup30]

int gcd(int a, int b){
	int GCD;
	for(int i=1; i<=a && i<=b; i++){
		if(a%i==0 && b%i==0){
			GCD=i;
		}
	}
return GCD;	
}

[kevinkjt2000]

@anup30: your example will return undefined values when either a or b is less than or equal to 0

[anup30]

gcd(0,a) = a (wikipedia)

int gcd(int a, int b){
	if(a==0) return b;
	if(b==0) return a;
	int GCD;
	for(int i=1; i<=a && i<=b; i++){
		if(a%i==0 && b%i==0){
			GCD=i;
		}
	}
return GCD;	
}