Erstens ist Ihre Implementierung (möglicherweise) nicht ganz korrekt:
else if((m < 0) || (n < 0))
return -1;
Die GCD von zwei negativen Zahlen ist perfekt definiert. Wenn Sie wirklich nicht möchten, dass der Benutzer negative Zahlen übergibt, machen Sie dies in der Funktionssignatur explizit:
unsigned greatestCommonDivisor(unsigned m, unsigned n)
Der Euklid-Algorithmus ist eines der grundlegendsten Beispiele für die Rekursion:
unsigned greatestCommonDivisor(unsigned m, unsigned n)
{
if(n == 0) return m;
return greatestCommonDivisor(n, m % n);
}
Wir prüfen zunächst den Basisfall, der 2 ist: Wenn r 0 ist, ist n die Antwort; Wenn r nicht 0 ist, fahren Sie mit Schritt 3 fort. Der rekursive Aufruf kombiniert tatsächlich die Schritte 1 und 3 hier: m % n
Setzt n als Rest r
, und wir rufen die Funktion erneut mit auf n = m
.
Eine letzte Bemerkung: Viele Leute vermeiden rekursive Funktionen in C / C ++, da die meisten Compiler die Aufrufaufrufe nicht optimieren, um konstanten Stackspeicherplatz zu verwenden. Der Euclid-Algorithmus führt jedoch nur O(log N)
Schritte aus. Daher ist er auf jedem Computer mit (vernünftiger) Stapelgröße leicht zu sehen. Dies führt nicht zu einem Stapelüberlauf für Zahlen, deren Größe durch int
oder eingeschränkt ist unsigned
.