# 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.

Sweet! Recursion, I love recursive solutions, love recursive solutions, recursive solutions, solutions!

Thanks for the link to Dictionary of Algorithms and Data Structures too

given that php (well, zend engine) does not optimize tail call, I wonder how useful a recursive algoritm is..

I think you’re confusing “useful” with “efficient”. Whether or not it does it’s work optimally, it

doesit.A slick solution. And thanks for all the helpful repsponses to the Sitepoint posts. I nearly always find them educational.

Thanks for the comment G. Wild, I am glad someone finds them useful

i want to learn how to develope in PHP.i am very interested but i have no notion of algoritm.i have a basic knowledge on computer.i also have some basic knowledge on conception and analysis.i do not know if this forum can help me

.

Your function is amazingly simple and well representative of the original algorithm. Thank you for sharing.