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.