: http://sit.fraunhofer.de/Lava/LavaDoc/html/RepetComputSamples.htm

: http://lavape.sourceforge.net/doc/html/RepetComputSamples.htm

ToDo

Grundlagen:

http://www.mctr.umbc.edu/~sidhu/spring97/Lectures/Recursion/recursion/node6.html

http://triton.towson.edu/~akayabas/COSC455_Spring2000/Recursion_Iteration.htm

http://lavape.sourceforge.net/doc/html/RepetComputSamples.htm

Jeder Algorithmus, der sich rekursiv darstellen lässt, lässt sich auch iterativ darstellen und umgekehrt. Bei der Implementation in einer bestimmten Programmiersprache hat man diese Wahl nicht immer.

Es gibt (gab) Programmiersprachen, in denen Rekursion unmöglich ist, weil Rücksprungadressen nicht gestapelt werden, also immer nur die letzte Rücksprungadresse aktiv ist (z.B. COBOL 74, frühe BASIC-Implementationen). In anderen Sprachen, ist Rekursion immer noch i.d.R. nicht interessant, z.B. wenn es nicht möglich ist, Argumente an Prozeduren zu übergeben (z.B. COBOL 85: SpracheCobol), oder Prozeduren nicht reentrant sind (wie z.B. in FORTRAN 77: SpracheFortran // Anmerkung: Kein Thema mehr in Fortran 90!).

Deklarative Sprachen (z.B. SpracheProlog, SpracheErlang, SpracheRefal): Iteration wie sie in den gängigen imperativen Sprachen verwendet wird, ist einfach inhärent imperativ, also nicht deklarativ und kann deshalb in deklarativen Sprachen nicht verwendet werden. (Siehe DeklarativeProgrammierung) Es gibt aber auch Möglichkeiten Iteration deklarativ darzustellen. Sie kann mit Hilfe von Funktionen höherer Ordnung auf Basis von TailRecursion implementiert werden. Einige deklarative Sprachen haben eingebaute iterative Konstrukte, wie z.B. List Comprehensions. Deklarative Iteration abstrahiert von Details der Rekursion und ist dieser deshalb dort wo sie zur Verfügung steht, wenn sie ausreicht, vorzuziehen.

In Sprachen, die sowohl einen deklarativen als auch einen imperativen Programmierstil unterstützen (z.B. SpracheScheme, CommonLisp, SpracheDylan, SpracheML), sollte man natürlich, solange man nicht zu Performance-Optimierungen gezwungen ist, einen möglichst deklarativen Programmierstil einhalten, um die Les- und Wartbarkeit zu erhöhen.

Es gibt auch eine Reihe von OO-Sprachen, die zusätzlich zu den üblichen imperativen Konstrukten über Möglichkeiten der deklarativen Iteration (siehe oben) verfügen (z.B. SpracheSmalltalk, SprachePython, SpracheRuby, SpracheSuneido). Diese sind dann, wo sie passend eingesetzt werden können, sowohl der imperativen Iteration als auch der Rekursion vorzuziehen.

In imperativen Sprachen, die sowohl Rekursion als auch Iteration unterstützen (z.B. Java, C, Pascal, Ada) sollte man einfach die natürlichere/verständlichere Lösung wählen. Welche das ist, kann von vielen Faktoren abhängen: Von der zu implementierenden Funktionalität, von der zu verwendenden Sprache, von der Qualifikation und den Gewohnheiten der Programmierer, die das Programm erstellen/lesen/bearbeiten können sollen. Die Beurteilung wird oft subjektiv sein, es gibt aber Situationen, in denen eine objektive Entscheidung möglich ist:

Wenn der Programmierer für die iterative Umsetzung explizit einen Stack verwenden müsste, während die rekursive Implementierung mit der impliziten Verwendung des Systemstacks auskommt (und die Systemresourcen ausreichen), ist die Verwendung von Rekursion offensichtlich vorteilhaft.

Wenn eine mathematische Funktion implementiert werden soll und die rekursive Implementation fast genauso aussieht wie die mathematische Definition (typisches Beispiel: Fakultät), dann macht, vorrausgesetzt Performance und Resourcenbedarf sind ok, die Umsetzung in einen iterativen Algorithmus keinen Sinn.