Das deutsche Python-Forum

Was ist "günstiger"?
Im ersten Fall hab ich eine "Vertauschung" drin:
a, b = b, a
Ich weiß, dass da nichts vertauscht wird, sondern die Variablen a und b neu erstellt werden.

Code: Alles auswählen

def ggT(a,b):
        if a == b:
                return a
        if a > b:
                a,b = b,a
        return ggT(a,b-a)

Oder ist das hier klüger?
Anstatt zu "Vertauschen" wird ggT einfach mit vertauschten Werten aufgerufen. D.h. ich mach eine Rekursion mehr, bis ich zu dem Schritt komme, den ich gleich nach der "Vertauschung" im obigen Beispiel habe.

Code: Alles auswählen

def ggT(a,b):
        if a == b:
                return a
        if a > b:
               return(b, a)
        return ggT(a, b-a)

letzteres wird wohl nicht funktionieren, weil:

ggT(10,5) => (5, 10)

... oder hab ich da was verpeilt?

Zwei Namen an Werte binden ist auf jeden Fall "billiger" als ein Funktionsaufruf bei dem ja auch a und b an neue lokale Namen gebunden werden müssen plus allem was bei einem Funktionsaufruf so anfällt (Stackrahmen erstellen, hinspringen, Stackrahmen wieder abräumen, zurückspringen, etc.)

Da es sich hier um eine Endrekursion handelt wäre es das klügste es ganz ohne Rekursion zu machen. Und das ist in diesem Fall auch nicht so schwer.

Ich habe hier eine Version mit Rekursion, bei der die wiederholte Subtraktion durch Modulobildung abgekürzt wird:

Code: Alles auswählen

function ggt(a,b):
    if (b == 0):
        return a
    else:
        return ggt(b,a%b)

Helmut

Mir ist schon klar, dass ich den ggT auch als normale Schleife hätte bauen können.
Aber ich habe genau die Antwort bekommen, die ich wollte: ab,bc ist "billiger" als ggT(b,a).

@SeB
Ja, da hast du wohl Recht. Mir ging's aber mehr um die Theorie.
Danke für dein scharfes Auge.

Noch eine praktische Anmerkung: Das Rekusrsionlimit kann mit Deinem `ggT()` ziemlich schnell erreicht werden. `ggT(10000, 5)` endet mit einer Ausnahme.

oh ja, das habe ich auch schon sehr schnell bemerkt, dass es bei solch extremen Werten schnell zum stackoverflow kommt.
Man könnte natürlich noch richtig viel optimieren, aber ich hab das ja eh nur geschrieben, um mir eine Aufgabe zu erleichtern.

Das deutsche Python-Forum

Was ist "billiger": Vertauschen oder noch eine Rek

Was ist "billiger": Vertauschen oder noch eine Rek