Euclid’s Algorithm in one line of PHP

Sometimes I am amazed at how forums work. The way in which people come and offer help, myself include, impresses me. I do not fully understand my own personal motivations for participating in forums, but at least one one of the reasons is sometimes the opportunity to write so code just for the fun of it presents itself. One such case was here. The original poster essentially wanted to reduce a fraction (though he was kind of beating around the bush about it). The post had been up on the board for a day, and several people had answered trying to help and clarify the issue at hand.

I dredged up some grade school math memories from long ago, and recalled the way to reduce a fraction was to identify the greatest common denominator, and divide each of the parts of the fraction by the gcd. I jumped to my del.icio.us reference page and located the Dictionary of Algorithms and Data Structures to search for greatest common denominator.

This quickly lead to Euclid’s Algorithm, a heuristic methodology for identifying the greatest common denominator. About a minute of thought later, I implemented the algorithm in a one line recursive function call:

<?php
function gcd($a, $b) {
  return ($b) ? gcd($b, $a % $b) : $a;
} 
?>

With that in hand, it becomes trivial to write the function to reduce the fraction.

So why am I blathering on about this? No particular reason, sometimes I just like the elegance of a particular solution, and this one struck me as one I wanted to mention and save for posterity. It is not an OOP solution, but being object oriented is not a requirement for elegance or utility. As a side effect, it was an opportunity to throw out some links that someone may end up finding useful.