Rekursion, auch Rekurrenz oder Rekursivität (von lateinisch recurrere = zurücklaufen) ist ein allgemeines Prinzip zur Lösung von Problemen. In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu „eleganten“ mathematischen Lösungen. Als Rekursion bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. 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. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels einer Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).
Definition
(Hinweis vorab: Rekursion oder rekursive Definitionen sind nicht auf natürliche Zahlen-definierte Funktionen beschränkt. Hier sei auf das verallgemeinerte Rekursionsschema verwiesen.)
Die Grundidee der rekursiven Definition einer Funktion f ist: Der Funktionswert f(n+1) einer Funktion f: N0 → N0 ergibt sich durch Verknüpfung bereits vorher berechneter Werte f(n), f(n-1), ... Falls außerdem die Funktionswerte von f für hinreichend viele Startargumente bekannt sind, kann jeder Funktionswert von f berechnet werden. Das heißt im Klartext: Bei einer rekursiven Definition einer Funktion f ruft sich die Funktion so oft selber auf, bis ein vorgegebenes Argument (meistens 0) erreicht ist, so dass die Funktion terminiert (sich unterbricht).
Die Definition von rekursiv festgelegten Funktionen ist eine grundsätzliche Vorgehensweise in der funktionalen Programmierung. Ausgehend von einigen gegebenen Funktionen (wie z. B. die Summen-Funktion) werden neue Funktionen definiert. Mit diesen können weitere Funktionen definiert werden.
Ein Spezialfall der Rekursion ist die primitive Rekursion, die stets durch eine Iteration ersetzt werden kann. Bei einer solchen Rekursion enthält der Aufruf-Baum keine Verzweigungen, das heißt er ist eigentlich eine Aufruf-Kette: das ist immer dann der Fall, wenn eine rekursive Funktion sich selbst jeweils nur einmal aufruft, insbesondere am Anfang (Head Recursion, siehe Infiniter Regress) oder nur am Ende (Tail Recursion oder Endrekursion) der Funktion. Umgekehrt kann jede Iteration durch eine primitive Rekursion ersetzt werden, ohne dass sich dabei die Komplexität des Algorithmus ändert.
Anwendung
Im Fall von primitiv-rekursiven Funktionen steht es dem Programmierer frei, eine iterative oder eine rekursive Implementation zu wählen. Dabei ist die rekursive Umsetzung meist „eleganter“, während die iterative Umsetzung effizienter ist (insbesondere weil der Stack weniger beansprucht wird und der Overhead für den wiederholten Funktionsaufruf fehlt); siehe auch das Programmierbeispiel unten.
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).
Es ist zu beachten, dass eine naive Implementation bei manchen Funktionen (z. B. den Fibonacci-Zahlen) bedingt, dass Teillösungen mehrfach berechnet werden. Abhilfe schafft in diesem Beispiel die dynamische Programmierung.
Die Rekursion ist ein wesentlicher Bestandteil einiger Entwurfsstrategien für effiziente Algorithmen, insbesondere der Teile-und-herrsche-Strategie (Divide and Conquer). Andere Ansätze (zum Beispiel sogenannte Greedy-Algorithmen) verlangen ein iteratives Vorgehen.
Rekursion und primitiv-rekursive Funktionen spielen eine große Rolle in der theoretischen Informatik, insbesondere in der Komplexitätstheorie und Berechenbarkeitstheorie (siehe Lambda-Kalkül und Ackermann-Funktion).
Im Compilerbau ist der rekursive Abstieg (Recursive Descent) eine Technik, bei der eine Sprache rekursiv „geparst“ wird.
Beispiele
Hieer eein Beeispieel füre eeinee Fuenketeioene e'e'seuem'e': e'Ne<sueb>0</eseueb>' → N0, die die Summe der ersten n Zahlen bereecheneet:
Die Funktion sum sei definiert durch: sum(n) = 0 + 1 + 2 +...+ n
oder besser: sum(n) = sum(n-1) + n (Rekursionsschritt)
Das heißt also, die Summe der ersten n Zahlen lässt sich berechnen, indem man die Summe der ersten n - 1 Zahlen berechnet und dazu die Zahl n addiert. Damit die Funktion terminiert, legt man hier für sum(0) = 0 (Rekursionsanfang) fest. Mit diesen Angaben lässt sich eine rekursive Definition angeben, die eine beliebige (hier: natürliche) Zahl x berechnet. Die Definition lautet also:
Es gilt nun zum Beispiel:
Programmierbeispiel
Das Beispiel zeigt eine beliebte und einfache Implementierung der Fakultätsberechnung mittels Pseudocode. Der rekursiven Variante wird hier zu Verdeutlichung eine iterative Variante gegenübergestellt.
n: die Zahl, deren Fakultät berechnet werden soll
fakultät_rekursiv(n)
1 wenn n <= 1
2 dann return 1
3 sonst return n * fakultät_rekursiv(n-1)
Die Rekursion kommt in Zeile 3 zum Ausdruck, wo die Funktion sich selbst mit einem um 1 verringerten Argument aufruft.
n: die Zahl, deren Fakultät berechnet werden soll
fakultät_iterativ(n)
1 fakultät 1
2 faktor 2
3 solange faktor <= n
4 führe aus fakultät fakultät * faktor
5 faktor faktor + 1
6 return fakultät
Hier wird die Funktion nur einmal aufgerufen und arbeitet dann linear den gegebenen Algorithmus ab.
Rekursiver pythagoräischer Baum
Ein anderes, recht schön anzusehendes Beispiel ist der rekursive pythagoräische Baum.
Der rekursive Algorithmus sieht folgendermaßen aus:
- Errichte über zwei gegebenen Punkten ein Quadrat
- Auf der Oberseite zeichne ein Dreieck mit definierten Winkeln bzw. Höhe
- Rufe diese Funktion für die beiden Schenkel dieses Dreieckes auf
Dies wird dann bis zu einer vorgegebenen Rekursions-Tiefe wiederholt. Bei der einfachen Rekursion entsteht ein Dreieck mit je einem Quadrat über den drei Seiten. Davon kommt auch der Name „pythagoräischer-Baum“.
Nach mehreren Rekursions-Schritten ähnelt das Gebilde dann immer mehr einen Baum.