rekursionsproblem

[breathe_easy]

Vielleicht ein Problem welches hier nicht hingehört, aber ich weiß einfach nicht mehr weiter. Warum ist a vom Typ None?

Code: Alles auswählen

#! usr/bin/python

def euklid (a, b):
	print "Aufruf"
	if a or b == 0:
		return a
	if b != 0:
		rest = a % b
		a = b
		b = rest
		print a
		print b
		euklid(a,b)

erste = input ("zahl: ")
zweite = input ("zahl: ")
print euklid (erste, zweite)

Seht vom Style bitte ab. Es ist nur ein Rekursionsversuch.

[audax]

Code: Alles auswählen

def euklid (a, b):
    print "Aufruf"
    if a or b == 0:
        return a
    if b != 0:
        rest = a % b
        a = b
        b = rest
        print a
        print b
        return euklid(a,b) 

Du musst die return-Werte auch den ganzen Callstack wieder nach oben geben.

Mach dich am besten mal mit dem pdb-Debugger vertraut, der hilft bei vielen Fehlern!

[breathe_easy]

Verstehe ich nicht! Ich rufe ganz einfach die Funktion wieder für a und b neu auf. Warum muß ich die ganz Funktion zurückgeben?

[Tiefflieger]

Weil Du ihren Rückgabewert ausgeben möchtest:

Code: Alles auswählen

print euklid (erste, zweite)

Außerdem bedeutet

Code: Alles auswählen

if a or b == 0:

daß abgefragt wird, ob "a" wahr ist oder ob "b gleich 0" wahr ist, wenn ich mich nicht irre.

[breathe_easy]

Stimmt es müsste heißen a == 0 or b == 0. Trotzdem wenn ich z.B. 121 und 33 eingebe, so wird euklid zuletzt für die Zahlen a = 11 und b = 0 aufgerufen. Somit müsste ich doch 11 zurückbekommen!?!.

Beispiel:

zahl: 121
zahl: 33
Aufruf
33
22
Aufruf
22
11
Aufruf
11
0
Aufruf
None

[str1442]

Du gibst nicht die Funktion zurück, sondern ihr Ergebnis. Tust du das nicht, schmeißt du das Ergebnis weg. Du kannst ja auch nicht "a = 20" ohne das "a =" schreiben, in dem Fall wird der Wert zwar generiert, aber nicht gebunden, und folglich weggeschmissen. Bei rekursiven Funktionen das Gleiche.

[breathe_easy]

Ist mir immer noch nicht klar. Ich habe doch kein Ergebnis von dem ich wieder hochrechnen muß wie z.B. bei einer rekursiven Berechnung der Fakultät, wo von 1 bzw 0 als Anker wieder per Definition hochgerechnet wird, sondern ich habe einen Aufruf für neue Werte.
Vielleicht bin ich aber auch zu blöd es zu verstehen.
Wenn du das vielleicht nochmal anders formulierst str1442 verstehe ich es vielleicht.

[str1442]

Du machst im Grunde folgendes (hier mit zwei verschiedenen Funktionen, um zu erläutern, was ich meine):

Code: Alles auswählen

In [1]: def func1(arg, arg2):
   ...:     return "A Dummy String"
   ...: 

In [2]: def func2(arg, arg2):
   ...:     if True == False:
   ...:         func1("dummy", "dummy")
   ...:         
   ...:         return None
   ...:     else:
   ...:         # do sth other    
   ...:         pass
   ...:     
   ...:     

In [3]: print func2("dummy", "dummy")
None

Hier mit Dummy Argumenten und pseudo if's angereichert. Wird kein Wert zurückgegeben, "ergänzt" Python *immer* implizit "return None". Du machst ja nichts mit dem Wert, den du durch Aufruf von "euklid" bekommst. Genauso weiß kein Funktionsaufruf von irgendeinem anderen, selbst wenn es die gleiche Funktion ist, die aufgerufen wird. Du könntest statt "func1("dummy", "dummy")" oben auch direkt "A Dummy String." reinschreiben, der wird ja dann auch nicht zurückgegeben.

[lunar]

Rekursion musst du dir als Stapel vorstellen. Ganz oben ist der erste Aufruf, ganz unten der letzte Aufruf, der die Rekursion beendet.

Bei dir ist das der Fall, wenn die if-Abfrage wahr ist, dann wird "a" zurückgegeben. In diesem Fall bist du quasi "ganz unten" angekommen. Jetzt musst du das Ergebnis aber natürlich noch wieder "nach oben" geben, damit die allererste Funktion (die, die du selber aufgerufen hast) das Ergebnis auch sieht. Das allerdings tust du nicht. Das ganze lässt sich illustieren:

Code: Alles auswählen

 programm       Ergebnis: None
     |              ^
     v              |
euklid(4, 2)    Ergebnis: None
     |              ^
     v              |
euklid(2, 2)    Ergebnis: None
     |              ^
     v              |
euklid(2, 0) -> Ergebnis: 2

Das ist dein Programm. Vor den rekursiven Aufruf muss eine return Anweisung, damit das Ergebnis auch weitergegeben wird.

Wenn dir das nicht klar ist, solltest du nochmal ein Tutorial konsultieren und Wikipedia zum Thema Rekursion zu Rate ziehen.

[Leonidas]

Ich finde dieses Bild zur Rekursion recht gelungen um zu illustrieren wie es funktioniert. Letztendlich hast du eine Berechnung in der du die Formel wieder vorkommt und in dieser die Formel nochmal vorkommt bis du dann zu einer Formel ankommst die sich nicht mehr selbst enthält (Zeile 7 im Bild). Danach wird die recht stark aufgeblähte Formel vereinfacht und am Schluss ist das Ergebnis der Formel das Ergebnis das du haben wolltest.

In der Papierfassung sieht es auch nicht ganz so pixelig aus.

[breathe_easy]

Vielen Dank! Die Menschen hier im Forum sind echt super!