Rekursive Funktion, was mach ich falsch?

[Nakkiel]

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]

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]

@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]

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]

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]

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]

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.

[name]

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

[BlackJack]

@name: Im Prinzip richtig, aber wenn die Studenten nunmal Rekursion lernen sollen…

[Nakkiel]

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