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

verstehe rekursion nicht

Beitragvon Kranioklast » Montag 14. März 2005, 13:11

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
Benutzeravatar
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Beitragvon leoel » Montag 14. März 2005, 13:19

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

Beitragvon Kranioklast » Montag 14. März 2005, 17:03

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

Beitragvon Leonidas » Montag 14. März 2005, 17:09

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 Modvoice
Benutzeravatar
leoel
User
Beiträge: 36
Registriert: Dienstag 25. Mai 2004, 08:54
Wohnort: Graz

Beitragvon leoel » Dienstag 15. März 2005, 09:17

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

Beitragvon Kranioklast » Dienstag 15. März 2005, 16:34

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.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]