int do_gcd (int x, int y)
{
if (y == 0)
{
return x;
}
else
{
return do_gcd (y, x % y);
}
}

int gcd (int x, int y)
{
return x > y ? do_gcd (x, y) : do_gcd (y, x);
}

こんなかんじでどうでしょう。