elundril - Mi 25.03.09 11:02
Titel: Rekursion vs. Iteration

---

Hallo,

heute während einer Vorlesung hab ich mich gefragt welches Verfahren besser ist, Rekursion oder Iteration? Draufgekommen bin ich als mein Professor gesagt hat das die binäre Suche auch Rekursion darstellbar wäre. Jedoch frag ich mich warum ich für abzählbare Mengen eine Rekursion verwenden soll? Es ist ja schließlich so, dass bei einer Rekursion immer wieder was auf den Stack geworfen wird, bei einer Iteration jedoch nicht. Stimmt meine Annahme das bei abzählbaren Mengen eine Iteration von Vorteil ist?

lg elundril

jaenicke - Mi 25.03.09 11:21

---

Nur, wenn du dadurch nicht zu viel Overhead produzierst. Jede Rekursion lässt sich auch als Iteration umsetzen, aber sinnvoll ist es nur, wenn dies auch sinnvoll möglich ist.

Kha - Mi 25.03.09 12:52

---

elundril hat folgendes geschrieben :

Es ist ja schließlich so, dass bei einer Rekursion immer wieder was auf den Stack geworfen wird, bei einer Iteration jedoch nicht.

Nicht unbedingt. Manche Sprachen (natürlich gerade die funktionalen) können Endrekursion mit Tail Calls [http://en.wikipedia.org/wiki/Tail_call] umsetzen, wodurch der Stackverbrauch wie bei der Iteration konstant bleibt. Oder sie setzen intern einfache rekursive Funktionen gleich als Schleifen um.

Wenn die Sprache so etwas bietet, gibt es gerade beim Beispiel der Binären Suche keinen Grund, auf die mathematisch-prägnante Formulierung als Rekursion zu verzichten. Und funktionale Sprachen machen mit Features wie Type Inference und Pattern Matching rekursive Ansätze noch attraktiver. In anderen Sprachen ist es mal wieder das bekannte Abwägen zwischen Eleganz und Performance - und da bitte immer daran denken, was Donald Knuth von Premature Optimization hält ;) .