rekursionsproblem

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
breathe_easy
User
Beiträge: 58
Registriert: Sonntag 29. Juli 2007, 18:34

rekursionsproblem

Beitragvon breathe_easy » Freitag 5. Dezember 2008, 21:41

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
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Freitag 5. Dezember 2008, 21:51

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
User
Beiträge: 58
Registriert: Sonntag 29. Juli 2007, 18:34

Beitragvon breathe_easy » Freitag 5. Dezember 2008, 21:59

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
User
Beiträge: 11
Registriert: Freitag 28. November 2008, 18:47

Beitragvon Tiefflieger » Freitag 5. Dezember 2008, 22:21

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
User
Beiträge: 58
Registriert: Sonntag 29. Juli 2007, 18:34

Beitragvon breathe_easy » Freitag 5. Dezember 2008, 22:36

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
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Beitragvon str1442 » Freitag 5. Dezember 2008, 22:36

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
User
Beiträge: 58
Registriert: Sonntag 29. Juli 2007, 18:34

Beitragvon breathe_easy » Freitag 5. Dezember 2008, 22:45

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.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Beitragvon str1442 » Freitag 5. Dezember 2008, 23:00

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

Beitragvon lunar » Freitag 5. Dezember 2008, 23:08

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.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Samstag 6. Dezember 2008, 01:15

Ich finde [url=http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1]dieses Bild zur Rekursion[/url] 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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
breathe_easy
User
Beiträge: 58
Registriert: Sonntag 29. Juli 2007, 18:34

Beitragvon breathe_easy » Samstag 6. Dezember 2008, 12:12

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

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder