Jabarkan Implementasi dari Algoritme Euklides

Algoritme ini dapat dinyatakan dengan menggunakan rekursi kanan:

return fpb(b, a modulus b);

Secara iteratif, fungsi ini dapat ditulis sebagai:

Euklides pada mulanya merumuskan masalah ini secara geometri, sebagai masalah untuk mencari "satuan" yang dapat dipakai untuk panjang dari dua buah garis, dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang. Implementasi ini sama dengan implementasi berikut ini, yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas: