Rekursive Funktion, was mach ich falsch?

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.
Antworten
Nakkiel
User
Beiträge: 7
Registriert: Sonntag 2. November 2008, 21:44

Sonntag 9. November 2008, 11:36

Hi, der Versuch, den euklidischen Algorithmus in Python umzusetzen schlägt bei mir einfach nur fehl.
Die Iterative Variante habe ich gut hinbekommen, aber jetzt bekomme ich beim Ausführen Fehler und ehrlich gesagt weiß ich nicht genau wieso.

Code: Alles auswählen

def f(a, b):
	if b==0 or a==0:
		return 0
	else:
		while a != b:
			if a<b:
				f(b, a-b)
			else:
				f(a, b-a)
		return a
Habe mich an diesesTutorial gehalten.

Da es für eine uni-Aufgabe ist, sind vermutlich Tips und Hinweise besser als eine fertige Lösung. So lern ichs wenigstens=)

Bin jedenfalls für Hilfe sehr dankbar
acoolon
User
Beiträge: 27
Registriert: Samstag 2. August 2008, 20:16

Sonntag 9. November 2008, 11:50

wenn a = 2 und b = 3, dann ist a<b also f(b, a-b)

dann ist a = 3 und b =-1, also nicht a<b, sondern a>b --> f(a, b-a)

also a = 3 und b = -4 , also nicht a<b, sondern a>b --> f(a, b-a)

-->endlosschleife, den if a == 0 or b == 0 greift hier nicht
BlackJack

Sonntag 9. November 2008, 13:08

@Nakkiel: Die ``while``-Schleife dürfte da sowieso nichts zu suchen haben, denn die willst Du ja gerade durch die Rekursion ersetzen.

Ausserdem musst Du die Ergebnisse von rekursiven Aufrufen auch *zurückgeben*, sonst kommt als nächstes die hier im Forum schon tausendfach gestellte Frage "Warum liefert meine rekusrive Funktion eigentlich immer `None`?".

Bei der Problembeschreibung wäre es noch nett, wenn Du in Zukunft verrätst *was* für Fehler kommen. Das kann ja vom Programmabsturz bis zu falschen Werten alles mögliche sein. Bei einer Ausnahme am besten immer den kompletten Traceback posten. Ausser vielleicht bei rekursiven Funktionen, denn da kann der ja ziemlich lang werden. :-) Da darfst Du dann sinnvoll kürzen.

Und bei falschen Werten am besten sagen was Du erwartet hast und was Du stattdessen bekommst.
Nakkiel
User
Beiträge: 7
Registriert: Sonntag 2. November 2008, 21:44

Sonntag 9. November 2008, 14:27

Danke für die Hinweise. Was ich oben gemacht hab war ja wirklich blöd. Vor allem die while-Schleife, daran hab ich überhaupt nicht gedacht, dass die ja gerade vermieden werden soll. Muss wirklich noch viel lernen.

Code: Alles auswählen

def f(a, b):
	if b==0 or a==0:
		print 0
	elif a==b:
		print a
	elif a != b:
			if a<b:
				f(a, b-a)
			else:
				f(a-b, b)
So funktioniert es jetzt.

Danke nochmal.
BlackJack

Sonntag 9. November 2008, 15:01

Kommt auf die Definition von "funktionieren" an. Ich würde bei so einer Aufgabenstellung erwarten, dass das Ergebnis der Berechnung von der Funktion zurückgegeben wird und nicht ausgegeben. So drückst Du Dich nämlich irgendwie um einen wichtigen Aspekt bei rekursiven Aufrufen bei dem viele am Anfang etwas falsch machen.

Wichtig ist es zu verstehen, dass es zwar statisch nur eine Funktion gibt, aber beim Aufruf durch die Rekursion *viele* Inkarnationen die zur gleichen Zeit existieren und die etwas zurückgeben müssen. Und man muss sich halt klar machen an *wen* etwas bei jedem ``return`` zurückgegeben wird. Diese Fragestellung umgehst Du komplett.
Nakkiel
User
Beiträge: 7
Registriert: Sonntag 2. November 2008, 21:44

Sonntag 9. November 2008, 16:46

Dann hab ich das auch offensichtlich nicht verstanden.
Ich muss zugeben, dass ich nicht weiß, wieso es mit dem return Befehl nicht geklappt hat. Dort wo print a steht hatte ich zunächst return a

Der return Befehl return a ist doch vorhanden und ich weiß nicht wieso er das dann nicht ausführt wenn es bei einem durchlauf drauf stößt.

Ich meine, der Befehl ist ja auch da, wenn die Funktion innerhalb der Funktion durchläuft und müsste dann doch sehen "A ist B, dann gebe ich A aus"
BlackJack

Sonntag 9. November 2008, 17:30

Das ``return`` wird ja auch ausgeführt und der Wert wird an die aufrufende Funktion zurückgegeben. Die Frage ist jetzt: Welche ist das und was macht die an der Stelle damit?

Nimm Dir mal Papier und Bleistift und spiel das mit diesem Quelltext durch:

Code: Alles auswählen

def f(n):
    if n == 0:
        return 'Boom'
    else:
        f(n - 1)
    # return None

print f(1)
Das auskommentierte ``return`` steht da implizit bei jeder Funktion in Python.
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Sonntag 9. November 2008, 19:01

Wobei unnötige Rekursion in Python nicht so toll ist, weil es das nicht zu Iteration optimiert, wie manche andere Sprachen(siehe Tail recursion)

Edit: Recursion vs. Iteration ist vielleicht auch interessant
Ohloh | Mein Blog | Jabber: segfaulthunter@swissjabber.eu | asynchia – asynchrone Netzwerkbibliothek

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.
BlackJack

Sonntag 9. November 2008, 20:19

@name: Im Prinzip richtig, aber wenn die Studenten nunmal Rekursion lernen sollen…
Nakkiel
User
Beiträge: 7
Registriert: Sonntag 2. November 2008, 21:44

Sonntag 9. November 2008, 22:30

Trotzdem immer gut solche Hinweise.
Will ja nicht nur Prüfungen bestehen, sondern primär besser werden.
Antworten