verstehe rekursion nicht

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
Kranioklast
User
Beiträge: 14
Registriert: Dienstag 9. November 2004, 20:56
Wohnort: Berlin

Ich verstehe dieses kleine Progrämmchen nicht, jedenfalls das nicht,
was passiert, wenn "wert" < 2 ist. Warum geht "wert" wieder
hoch bis zum Ausgangswert? Wäre dankbar, wenn mir das jemand
mit einfachen Worten erklären könnte. Danke!!!

Code: Alles auswählen

def rechne(wert):
	if wert<2:
		return
	print wert
	rechne(wert/2)
	print wert

	
>>> rechne(50)
50
25.0
12.5
6.25
3.125
3.125
6.25
12.5
25.0
50
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Hallo!

Der Wert geht wieder zurück, weil du NACH dem rekursiven Aufruf von "rechne" den aktuellen Wert ausgibst.

d.h. wenn du die Rekursion mit Wert 10 aufrust, gibst Du nachher wieder den Wert der aktuellen Rekursionsstufe aus.

Gib das letzte Print weg, dann geht der Wert nur nach unten[/code][/quote]
Kranioklast
User
Beiträge: 14
Registriert: Dienstag 9. November 2004, 20:56
Wohnort: Berlin

Vielen Dank für deine Antwort. Ist mir trotzdem nicht ganz klar.
Nachdem der Wert kleiner als 2 wird, ist der Rekursionsaufruf
beendet und das Programm geht zur letzten print-Anweisung.
Der aktuelle Wert liegt bei 3.125, daher wird 3.125 auch
zweimal ausgegeben. Bis dahin ist alles klar. Aber warum werden auch die "alten" aktuellen Werte noch einmal ausgegeben?
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Kranioklast hat geschrieben:Aber warum werden auch die "alten" aktuellen Werte noch einmal ausgegeben?
Weil dort zweimal Print drinsteht? Nachdem die rekursion zu ende ist, wird jede funktion in der Rekursiven Schleife noch zu Ende laufen, also noch einmal print machen und sich dann erst beenden. Lass einfach das etzte print weg und schon siehst du's.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Ich probier das mal "grafisch" darzustellen:

Wenn Du eine Rekursion hast, wird jede "Instanz" der aufgerufenen Funktion separat im Speicher gehalten. (Für Sprach-Puristen gilt die Formulierung vermutlich nicht)

D.h. wenn die Abbruchbedingung (wert < 2) erreicht ist, wird die zuletzt aufgerufene Funktion beendet. Das Verlassen der Funktion geht aber dorthin, von wo Du sie aufgerufen hast, und das ist die Funktion mit dem Wert, der doppelt so groß war.

Als Beispiele fange ich mit dem Wert 8 an. Dieses Beispiel soll die Verschachtelungen der Funktionen verdeutlichen und wurden der Übersicht halber mit eigenen Namen versehen:

Code: Alles auswählen

rechne_8:
  print 8     # in Fkt. "rechne_8"
  rechne_4:
    print 4   # in Fkt. "rechne_4"
    rechne_2:
      print 2  # in Fkt. "rechne_2"
      rechne_1:
        return   # von rechne_1 nach rechne_2
      print 2   # und schliesse Fkt "rechne_2", gehe nach "rechne_4"


(soweit alles klar. Jetzt springt der Programmfluss dorthin zurück, von wo rechne_2 aufgerufen wurde, und das ist rechne_4, und dort steht als nächste Anweisung, dass der aktuelle Wert ausgegeben werden soll, und der ist 4.

Also geht es folgendermassen weiter:

Code: Alles auswählen

    print 4   # und schliesse Fkt "rechne_4", gehe nach "rechne_8"
  print 8   # in Fkt. "rechne_2 und schliesse Fkt "rechne_2"
Ich hoffe ich konnte das gut verständlich darstellen. Meiner Meinung nach, ist es wichtig, sich bei Rekursionen zu verdeutlichen, dass "jede" Funktion für sich allein im Speicher steht und natrülich auf die lokalen Variablen mit ihr. Deshalb sind Rekursionen aus ziemlich speicherfressend, aber für ähnliche Strukturen einfach genial. (Bäume etc.)

Wenn Du gar zuviel Zeit hast, empfehle ich Dir dazu das Buch "Gödel, Escher, Bach" von Douglas Hofstatter. Er hat es leider grad ein paar Jahre vor der "Entdeckung" der Mandelmenge geschrieben, aber obwohl es jettz schon 25 Jahre alt ist, ist es nach wie vor ein Hammer...
Kranioklast
User
Beiträge: 14
Registriert: Dienstag 9. November 2004, 20:56
Wohnort: Berlin

Vielen Dank, das ist die Sprache, die ein Schüler (9.Klasse)
versteht. Du kannst Lehrer werden :D

Mir war nicht klar, dass der Wert jeder Rekursionsschleife
gespeichert bleibt.
Dass mit dem Weglassen des zweiten print der "Rücklauf"
nicht mehr angezeigt wird, war mir selbst klar, darum
ging es mir ja auch gar nicht.

Vielen Dank noch mal für diese Antwort!
Danke auch Leonidas! Du hast es ja auch schon angedeutet.
Antworten