If your main goal here is reducing fractions, then you really don't anything more than the standard algorithm gcd(N,M) = gcd(M, N mod M). The binary version is a slight improvement over the original (based on your source) and I doubt it's really worth messing up (beyond curiosity). Consider:

Code:

#include <iostream.h>
int GCD(int N, int M)
{
if (N % M == 0)
{
return M;
}
else
{
return GCD(M, N % M);
}
}
int main()
{
int numerator, denominator, g;
cout<<"Numerator: ";
cin>>numerator;
cout<<"Denominator: ";
cin>>denominator;
g = GCD(numerator, denominator);
cout<<endl<<numerator / g<<" / "<<denominator / g<<endl;
return 0;
}

This should do everything you need it to. Alturnatively you could write
Code:

(N % M == 0)?(return M):(return GCD(M, N%M))

in place of the if-else statement