Das deutsche Python-Forum

Hallo,
ich möchte, dass die rekursive GCD Methode das Ergebnis und wie oft diese aufgerufen wurde zurück liefert. Ich möchte keine globalen Variablen verwende, da in Python es möglich ist mehrere Werte zurück zu liefern.

Code: Alles auswählen

def gcd(calls, a, b):
  calls += 1
  if b==0:
    return (calls,a)
  return (calls, gcd(calls, b,a%b))

calls, res = gcd(0, 210,150)
print res
print calls

Ich habe es versucht, aber leider bekomme nicht das gewünschte Ergebnis. Woran kann es liegen?

Viele Grüße

Vllt. wird b halt einfach nie Null... Ich weiß allerdings nicht, warum du das rekursiv löst - naja Geschmackssache...

Da ich keinen Interpreter zur Verfügung habe, vermute ich mal, dass du sicher gehen musst, dass im rekursiven Aufruf der zweite Parameter immer größer ist als der dritte.

Die Methode liefert unter anderem 30 zurück welcher auch der richtige Wert ist.
Aber leider sieht die Ausgabe komisch aus

Code: Alles auswählen

(2, (3, 30))
1

Woran kann es liegen?

Deine Rückgabe ist nicht korrekt, eine richtige Rekursion sähe in etwa so aus.

Code: Alles auswählen

def gcd(calls, a, b):
  calls += 1
  if b==0:
    return (calls, a)
  return gcd(calls, b,a%b)

Aber ich denke auch das man besser eine iterative Lösung schreiben sollte
z.B.

Code: Alles auswählen

def gcd(a, b):
  calls = 0
  while b != 0:
    a, b = b, (a % b)
    calls += 1
  return calls, a

Danke. Jetzt über liege ich wie man die Anzahl der Aufrufen von Fibonacci Methode bestimmen kann.

Code: Alles auswählen

def fib(n):
  if n==0:
    return 0
  elif n==1:
    return 1
  elif n > 1:
    return fib(n-2) + fib(n-1)

print fib(6)

I weiss, dass es auch möglich ist diese Methode iterativ zu implementieren, aber ich würde ganz gerne die Rekursion besser verstehen. Wie liefert man hier zwei Werte (Ergebnis und Anzahl der Aufrufe) ohne globale Variable zurück?

mit hat geschrieben:Wie liefert man hier zwei Werte (Ergebnis und Anzahl der Aufrufe) ohne globale Variable zurück?

So:

Code: Alles auswählen

def fib(n):
    if n == 0:
        return (1, 0)
    elif n == 1:
        return (1, 1)
    elif n > 1:
        f1 = fib(n-2)
        f2 = fib(n-1)
        return (f1[0] + f2[0], f1[1] + f2[1])

print fib(6)

Letztendlich wrappst du einfach alles in Tupel..

Wobei ich noch erwähnen will, dass Pythons Funktionen immer nur einen Rückgabewert haben. Wenn man zwei Werte in ein Tupel packt dann ist es immer noch nur ein Rückgabewert (wir sind ja nicht bei Scheme wo es Multiple Return Values gibt).

Danke. Wenn ich dein Code laufen lasse bekomme ich (13, 8 ). Das Ergebnis ist 8 und 13 ist wohl die Anzahl wie oft die Methode aufgerufen wurde.

Was genau bedeutet f1[0], f2[0], f2[1] und f2[1]. Wie kommen diese Arrays zustande und wie speichert die linke Seite die Anzahl und die rechte das Ergebnis?

Ja, 8 ist richtig, aber mit 13 lag ich falsch, das richtige Ergebnis sollte 25 sein. Ich habe den Quelltext etwas umgeschrieben und ausgebessert, damit es einfacher zu erklären wird:

Code: Alles auswählen

def fib(n):
    if n == 0:
        return (1, 0)
    elif n == 1:
        return (1, 1)
    elif n > 1:
        lcalls, lvalue = fib(n-2)
        rcalls, rvalue = fib(n-1)
        return (lcalls + rcalls + 1, lvalue + rvalue)

print fib(6)

Du hast hier einen rekursiven Aufruf, wobei die rekursive Funktion zwei Rekursionsanker hat. Rekursionsanker sind die Zweige der Funktion, die selbst nicht rekursiv sind, d.h. bei denen die Rekursion demnach terminiert.

Diese Anker sind ``fib(0)``, das hat das Ergebnis ``(1, 0)`` weil das Ergebnis 0 ist und dafür ein Funktionsaufruf nötig war. Der andere Anker gibt ``(1, 1)`` zurück, weil das Ergebnis 1 ist und auch dafür nur ein Funktionsaufruf nötig war.

Nun aber zum Fall dass es nicht 0 oder 1 ist, dann muss die Funktion rekursiv aufgerufen werden. Sagen wir mal, wir wollen ``fib(2)`` bestimmen. Da 2 weder gleich 0 noch gleich 1 ist, kommen wir in den ``else``-Zweig. Was müssen wir also machen? Nun, wir müssen erstmal ``fib(n-2)`` berechnen, also ``fib(2-2)`` also ``fib(0)`` berechnen. Das Ergebnis ist ``(1, 0)``. Jetzt nutzen wir Tuple-Unpacking, damit wir uns die Indexerei sparen und sprechende Namen haben: wir binden die 1 an ``lcalls`` weil es die Anzahl der Funktionsaufrufe des linken Operanden ist, und die 0 an ``lvalue`` weil es der zugehörige Wert ist. Selbiges machen wir mit dem ``fib(n-1)``-Teil, also ``fib(2-1)`` also ``fib(1)`` was ``(1, 1)`` ergibt, das binden wir an die entsprechenden rechts-Varianten der Namen.

Nun müssen wir nur noch die rechte und linke Seite zusammenfassen. Wie sieht das aus? Nunja, der Wert ist klar: das ist die Summe vom linken (n-2) und rechten (n-1) Teil der Rekursion. Das geben wir an der zweiten stelle des Tupels zurück. An der ersten Stelle geben wir die Anzahl der Aufrufe zurück. Die wissen wir: Anzahl der Aufrufe rechts plus die Anzahl der Aufrufe links, da wir aber gerade selbst mitten in einem Funktionsaufruf sind, müssen wir natürlich noch 1 draufzählen. Also geben wir ``(neue_anzahl_aufrufe, neue_fib_summe)`` zurück.

Das wars! Falls du noch Fragen hast: einfach nochmal nachhaken. Übrigens empfehle ich "The Little Schemer" zum lernen von Rekursion, das ist ein kleines Buch, das sich genau damit beschäftigt (ist allerdings mit für Python-Programmierer etwas ungewohnter Syntax).

Yoda sinngemäß: "Um Rekursion zu verstehen, Rekursion verstehen du musst"

Vielen Dank!

Ich würde ja bei `return` jeweils die Klammern weglassen und ausnutzen, dass man dort mehrere Argumente in Form eines impliziten Tupels angeben kann und nicht nur ein Argument in Form eines expliziten Tupels benutzen muss.

Stefan

@sma: Was bitte sind "implizite Tupel"? Tupel werden durch Kommata erzeugt. Explizit. Die Klammern dienen in der Regel nur der Lesbarkeit.

Die Grammatik:

Code: Alles auswählen

return_stmt = "return" [expr_list]
expr_list = expression {"," expression} [","]
expression = ... parenth_form ...
parenth_form = "(" [expr_list] ")"

Wenn nach `return` eine Liste basierend auf `expr_list` gefunden wird, nenne ich das ein implizites Tupel. Greift jedoch die Regel, das `expr_list` nur aus einer `expression` besteht, die (nach diversen Regeln) auf `parenth_form` stößt, ist das ein explizites Tupel für mich.

Stefan[/code]

@sma: Die Unterscheidung kann ich nicht nachvollziehen. In beiden Fällen wird das Tupel aus der `expr_list` erzeugt. Die Kommata sind der Ausschlaggebende Faktor für das Tupel. Damit erzeugt man explizit ein Tupel.

Tupel werden mithilfe von Kommata überzeugt. Klammern sind in diesem Fall, wie in anderen auch(Generatoren als eines von mehreren Argumenten), nur dafür da um die Rangfolge zu definieren.

Wenn man dies als Definition für Klammern um Ausdrücke ansieht erklärt sich z.B. sehr leicht dass Verhalten bei ``("foobar")``.

andererseits ist ``x=()`` auch ein tuple

@jbs: Das ist aber der einzige Fall wo die Klammern wirklich das Tupel erzeugen.

BlackJack hat geschrieben:@sma: Die Unterscheidung kann ich nicht nachvollziehen. In beiden Fällen wird das Tupel aus der `expr_list` erzeugt. Die Kommata sind der Ausschlaggebende Faktor für das Tupel. Damit erzeugt man explizit ein Tupel.

Mit oder ohne Klammern nimmt es verschiedene Wege durch den Parser. Daran habe ich implizit und explizit unterschieden. Für mich heißt `return a, b` das zwei Werte zurückgegeben werden, jedoch `return (a, b)` dass ein Wert, nämlich ein Tupel zurückgegeben wird. Das Ergebnis ist das selbe, doch die Intension ist IMHO eine andere.

Stefan

@sma: Also ich würde da nicht von impliziten oder expliziten Tupeln sprechen. In beiden Fällen ist es *ein* Wert, nur im zweiten Fall sind halt noch die Klammern drumherum, um eine Absicht des Programmierers deutlicher zu machen.

Es kann ja aber auch Fälle geben, wo man semantisch gesehen mehrere Werte zurückgeben möchte, aber trotzdem Klammern setzt, weil nicht alles auf einer Zeile Platz findet.

Oder man setzt Klammern um Tupel, nicht weil man die Elemente zusammen als einen Wert sehen möchte, sondern um die Lesbarkeit zu erhöhen. Dabei habe ich jetzt nicht ``return``, sondern zum Beispiel LCs oder Generatorausdrücke im Blick. Gerade neulich hier im Forum passiert, das jemand durch ``[x*y for x, y in spam()]`` verwirrt wurde, weil das Komma als Trenner zwischen zwei Elementen in einer Liste interpretiert wurde. Klammern machen das etwas lesbarer: ``[x*y for (x, y) in spam()]``. Ich würde aber nicht davon sprechen, dass man da unterschiedliche Arten von Tupeln erzeugt.

Welchen Weg das durch den Parser nimmt, ist IMHO auch ein gutes Stück Implementierungsdetail. Grammatiken, die die Grundlage für einen Parser sind, müssen nicht zwingend die sein, die man Programmierern zum Erklären der Syntax zeigt.

Wir haben hier unterschiedliche Meinungen. Hier muss man z.B. wissen, welchen Weg der Parser nimmt, um zu erkennen, welches (implizite) Tupel zurückgegeben wird:

Code: Alles auswählen

return a if b else a, b

Man dann das durch explizite Tupel eindeutig machen:

Code: Alles auswählen

return (a if b else a, b)
return a if b else (a, b)

Stefan

Das deutsche Python-Forum

mehrere Werte zurück liefern

mehrere Werte zurück liefern