• Artikel
• Bearbeiten
• Historie
• Druckansicht

Rekursion

Als Rekursion bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu "eleganten" mathematischen Lösungen.

Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress (umgangssprachlich Endlosschleife?). Zur Vermeidung von infinitem Regress insbesondere in Computerprogrammen bedient man sich der semantischen Verifikation von rekursiven Funktionen.

Anwendung

Manche Programmiersprachen (insbesondere in der Funktionalen Programmierung) erlauben keine Iteration, sodass immer die rekursive Umsetzung gewählt werden muss. Solche Sprachen setzen häufig zur Optimierung primitive Rekursionen intern als Iterationen um (insbesondere einige Interpreter für Lisp und Scheme verfahren so).

Doch betrachtet Rekursion nicht als Notlösung. Rekursion ist meist schön und sauber und spart eine Menge Zeit. Als Fazit: Rekursion ist fast immer vorzuziehen.