# Recursive and iterative Euclidean algorithms

Is this code too cryptic? Simple yes or no question. Feedback is optional.

int recursive_euclidean( int num1, int num2 )
{
int gcd=0;
if( num1 == num2 || num1 < 0 || num2 < 0 )
( ( num1 == num2 ) ? ( gcd = num1 ) : ( ( num1 < 0) ? ( gcd = num2 ) :
( gcd = num1 ) ) );
else
( ( num1 > num2 ) ? ( gcd = recursive_euclidean( num1-num2, num2 ) ) :
( gcd = recursive_euclidean( num1, num2-num1 ) ) );
return gcd;
}

int iterative_euclidean( int num1, int num2 )
{
while( num1 != num2 && num1 > 0 && num2 > 0 )
(( num1 > num2 ) ? (num1-=num2) : (num2-=num1) );
return (num1>0) ? num1 : num2;
}

• Mathematically this is not quite correct, gcd(2, -2) = 2 is a better choice. gcd(2, -2) = -2 is also correct, as in terms of divisibility n and -n are essentially the same. – starblue Aug 8 '11 at 11:15
• Note that for an efficient gcd computation you need to use the % operator. – starblue Aug 8 '11 at 11:16
• perhaps you mean "too cryptic" – Malvolio Aug 8 '11 at 16:42
• Yes this code is WAY too cryptic. gcd? what's that? If it's greatest common denominator, then name your variable "greatest_common_denominator". Favor read-time convenience over write-time convenience. It reminds me of the cryptic K&R old school C style. Make your code read like English. I'd suggest reading the books "Code Complete" and also "Clean Code". – User Aug 24 '11 at 1:04

I don't like the multiple different assignments inside the operator.
They currently all assign to gcd but you need to study it in detail to work that out.
I would make the assignment explicit and the ternary operator return the correct value.

The other thing with ternary operator is that they are not trivial to read. So use white space to try and make it obvious that it's happening. Also I prefer to explicitly use '{' '}' to make sure that things don't accidentally become associated with the a different statement. I would lay it out like this:

int recursive_euclidean( int num1, int num2 )
{
int gcd;

if( num1 == num2 || num1 < 0 || num2 < 0 )
{
gcd = (num1 == num2)
? num1
: (num1 < 0)
? num2
: num1;
}
else
{
gcd = (num1 > num2)
? recursive_euclidean( num1-num2, num2 )
: recursive_euclidean( num1, num2-num1 );
}
return gcd;
}


Actually reading this again I would refactor more to this:

int recursive_euclidean( int num1, int num2 )
{
int gcd;

if ( num1 == num2)
{    gcd = num1;
}
else if (num1 < 0)
{    gcd = num2;
}
else if (num2 < 0)
{    gcd = num1;
}
else
{
gcd = (num1 > num2)
? recursive_euclidean( num1-num2, num2 )
: recursive_euclidean( num1, num2-num1 );
}
return gcd;
}


Then here, I would not personally not use the ternary operator.

int iterative_euclidean( int num1, int num2 )
{
while( num1 != num2 && num1 > 0 && num2 > 0 )
{
if (num1 > num2 )
{ num1-=num2;}
else{ num2-=num1;}
}
return (num1>0) ? num1 : num2;
}


Why do you use || between the three conditions only to then make a decision about the conditions seperately? Why don't you write it like this:

int recursive_euclidean( int num1, int num2 )
{
if( num1 == num2 )
return num1;
else if( num1 < 0 )
return num2;
else if( num2 < 0)
return num1;
else if( num1 > num2)
return gcd = recursive_euclidean( num1-num2, num2 ) ) :
else
return recursive_euclidean( num1, num2-num1 ) ) );
}


I hereby ban you from use of the ternary operator due to egregious abuse. Not seriously, but its not clear why you are trying to bring it in here.

• Thanks for you banning me from using the ternary operator. I wrote the code to spite my friend who likes curly braces. We had long debates over if my code was kosher, so I decided to get outside opinions. This is not how I usually code. – Matthew Hoggan Aug 9 '11 at 18:44
• @Matthew, I feel a lot better then. But writing code to spite people, that's just odd. – Winston Ewert Aug 9 '11 at 18:57

I think the simple test would be to have an outsider read the code and understand what it does. I did just that, and its perfectly readable to me. Actually, I find it to be a perfect mix of readability and compactness.

I just like this:

int recursive_euclidean( int num1, int num2 )
{
return    num1 == num2 ?  num1
: num1 < 0     ?  num2
: num2 < 0     ?  num1
: num1 > num2  ?  recursive_euclidean( num1-num2, num2 )
:                 recursive_euclidean( num1, num2-num1 );
}