Tutorien für Algorithmen und Datenstrukturen 2

Aufgabe 3-4

(Übungsblatt 3)

Begründen Sie, warum die rekursive Lösung eines Problems besser oder schlechter als die iterative Lösung sein könnte.

Lösungsvorschlag

Vorteile einer Rekursion:

• viele Probleme lassen sich auf sich selbst zurückführen; Computer-implementiert ergibt das automatisch eine Rekursion
• Algorithmus ist folglich bei manchen Problemen sehr einfach zu formulieren
• Algorithmus ist häufig kurz, elegant und damit leicht verständlich
• Code ist daher häufig leicht wartbar
• einige komplexere Probleme lassen sich nicht ohne weiteres in eine Iteration umformulieren

Nachteile einer Rekursion:

• Kontextwechsel beim Methodenaufruf benötigt Rechenzeit
• bei jedem Rekursionsschritt wird ein zusätzlicher Methoden-Kontext auf den Stack gelegt; aufgrund der begrenzten Stackgröße der gängigen Laufzeitumgebungen (Java: Stapel-Größe 2¹⁰) kommt es bei tieferer Rekursion schnell zum Stapelüberlauf (Java: StackOverflowError) mit Programmabsturz
• Laufzeitverhalten weniger leicht zu bestimmen als bei Iteration

Als Folge empfiehlt sich eine Rekursion in Java vor allem dann, wenn bekannt ist, dass die Rekursionstiefe nicht sehr groß ist. Dies ist bei allen Divide-and-Conquer–Algorithmen gegeben (logarithmische Baumtiefe!). Auch bei einigen anderen mathematischen Problemen ist dies der Fall, etwa bei Taylor-Entwicklungen.

Auch in den Geowissenschaften gibt es Beispiele: Der Geodät Egon Dorrer zeigt eine Möglichkeit, die Länge eines Ellipsoid-Bogens mit Hilfe einer rekursiven Implementierung der Descending Landen Transformation zu ermitteln [cf. Grafarend et al. 2003, Geodesy – the challenge of the 3rd millennium, pp. 293–298].