Der Algorithmus von Euklid (ca. 300 v. Chr.) berechnet den größten gemeinsamen Teiler (ggT) für zwei positive ganze Zahlen a und b. Als größten gemeinsamen Teiler bezeichnen wir die größte positive Zahl z(= ggT (a, b)), die a und b ohne Rest teilt; anders ausgedrückt: $$z = ggt(a, b) ⇔ (a, b, z ∈ N) ∧ (z|a) ∧ (z|b) ∧ (¬∃z': (z' > z) ∧ (z'|a) ∧ (z'|b))$$
Der Algorithmus von Euklid nutzt die Tatsache, dass der ggT sich bei der Modulo-Operation nicht ändert: $$∀a, b: ggT (a, b) = ggT(a~mod~b, b).$$ In jedem Schritt wird deshalb die größere der beiden Zahlen modulo der kleineren gerechnet und durch das Ergebnis ersetzt. Die Zahlen werden so immer kleiner, bis eine der Zahlen null ergibt. Die andere entspricht dem gesuchten ggT.
Implementrieren Sie den Euklidschen Algorithmus einmal rekursiv und einmal iterativ.