Euclid's Algorithm has a very elegant recursive definition:
  • Base Case: GCD(A, 0) = A
  • Recusive Case: GCD(A, B) = GCD(B, A%B)
This of course leads to a one-line algorithm in most any high level programming language. The function is tail recursive, so if you have a good compiler no call stack is built up.