Euclid's algorithm

The algorithm works as follows: $\text{Euclid}(a,b)$

• if $b=0$ then
  • return $a$
• else
  • return $\text{Euclid}(b,a\text{ mod }b)$