Seite 1 von 1
Rekursive Funktion iterativ implementieren
Verfasst: Donnerstag 21. April 2022, 23:08
von Marco98
Hey, ich habe hier eine rekursive Funktion aus einem Programm für Suchbäume und müsste diese iterativ implementieren, bzw. umändern:
def elem(v, t):
....if is_empty(t):
........return False
....elif v < value(t):
........return elem(v, left(t))
....elif v > value(t):
........return elem(v, right(t))
....else:
........return True
Wäre sehr dankbar, wenn mir jmd. dabei helfen könnte!
(Punkte sollen hier die Einrückungen darstellen)
Re: Rekursive Funktion iterativ implementieren
Verfasst: Freitag 22. April 2022, 09:29
von Sirius3
Zuerst wird nicht mit Punkten eingerückt, sondern hier im Forum gibt es code-Tags, das ist der </>-Knopf im Vollständigen Editor.
Variablen sollten aussagekräftig sein, Funktionen nach Tätigkeiten benannt werden. Ich rate mal, dass `t` ein `tree` ist, `v` ein `value`.
Ich weiß nicht, warum hier der Zugriff auf Attribute als Funktionen implementiert ist.
Am schwierigsten war es, herauszufinden, was die Funktion eigentlich macht. Es ist wie bei diesen mathematischen Rätseln, wo Symbole durch Zahlen ersetzt werden sollen, damit die Gleichung stimmt. Programmieren ist aber an sich schon herausfordernd genug, da braucht es nicht noch zusätzliche Rätselspiele.
Der decodierte Code sieht also so aus:
Code: Alles auswählen
def is_value_in_tree(value, tree):
if is_tree_empty(tree):
return False
elif value < tree.value:
return is_value_in_tree(value, tree.left)
elif value > tree.value:
return is_value_in_tree(value, tree.right)
else:
return True
Rekursion bedeutet ja, dass die Funktion nochmal aufgerufen wird, also wieder von vorne losläuft. Wenn Du also die Rekursion "simulieren" willst, brauchst Du eine Schleife, die auch wieder an den Anfang springt, Du mußt aber davor dafür sorgen, dass die Parameter richtig gesetzt werden.
Re: Rekursive Funktion iterativ implementieren
Verfasst: Sonntag 24. April 2022, 22:01
von Marco98
Sorry für die ungenaue Schreibweise meinerseits.
Genau t ist ein tree und v ein value!
Aber wie sieht diese Funktion dann iterativ aus???
wäre super, wenn mir das jemand kurz aufzeigen könnte, bitte.
Vielen Dank!
Re: Rekursive Funktion iterativ implementieren
Verfasst: Montag 25. April 2022, 09:29
von __blackjack__
@Marco98: Wo ist denn Dein konkretes Problem bei der (Haus)Aufgabe? *Du* sollst das ja schreiben und nicht Dir schreiben lassen.
Iterativ heisst hier mit einer Schleife statt rekursiven Aufrufen. Und da die Funktion endrekursiv ist, ist das eigentlich auch recht trivial, weil man sich nicht mal den Aufrufstack selbst basteln muss, weil man dieses ansonsten implizite ”Gedächtnis” bei rekursiven Aufrufen nicht braucht.
Du könntest auch einfach die bisherige Implementierung gar nicht beachten, sondern den Funktionskörper einfach löschen und einfach neu programmieren. Halt ganz normal prozedural. Mal Dir einen Suchbaum auf Papier auf, und überlege welche Schritte Du manuell machen musst um die Aufgabe der Funktion zu lösen und setz das dann in Quelltext um.