Rekursion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Als Rekursion, von lateinisch recurrere = zurücklaufen, bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. Die gegenseitige Rekursion bildet sich durch den gegenseitigen Verweis zweier oder mehrerer Funktionen auf einander.

In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu „eleganten“ mathematischen Lösungen. In der Regel sind rekursive Programme (als Darstellung eines rekursiven Problems) zwar wesentlich kompakter (also kürzer) als die iterativen Varianten, dafür sind sie etwas langsamer und der Speicheraufwand ist höher.

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).

Inhaltsverzeichnis

1 Definition
2 Anwendung
3 Beispiele
- 3.1 Programmierbeispiel
- 3.2 Rekursiver pythagoreischer Baum
4 Lösen von Rekursion
5 Siehe auch
6 Weblinks

[Bearbeiten] Definition

(Hinweis vorab: Rekursion oder rekursive Definitionen sind nicht auf natürliche Zahlen-definierte Funktionen beschränkt. Hier sei auf das verallgemeinerte Rekursionsschema verwiesen.)

Das Grundprinzip der rekursiven Definition einer Funktion f ist: Der Funktionswert f(n+1) einer Funktion f: N₀ → N₀ 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. Bei einer rekursiven Definition einer Funktion f ruft sich somit die Funktion so oft selbst auf, bis ein vorgegebenes Argument (meistens 0) erreicht ist.

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.

[Bearbeiten] Anwendung

Im Fall von primitiv-rekursiven Funktionen steht es dem Programmierer frei, eine iterative oder eine rekursive Implementierung 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 auf der Wiederverwendung bereits berechneter Zwischenlösungen beruht. 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.

[Bearbeiten] Beispiele

Die Funktion $\operatorname{sum}(n)$ soll die Summe der ersten $n$ Zahlen berechnen. Sie ist folgendermaßen definiert:

$\operatorname{sum}(n) = 0 + 1 + 2 +...+ n$

Um eine gleichwertige rekursive Definition der Summenfunktion zu erhalten benötigen wir zuerst eine Vorschrift, die die Summe einer Zahl $n$ aus der Summe einer kleineren Zahl berechnet. Diese Funktion heißt Rekursionsschritt. Beispielsweise lässt sich die Summe der ersten $n$ Zahlen berechnen, indem man die Summe der ersten $n - 1$ Zahlen berechnet und dazu die Zahl $n$ addiert:

$\operatorname{sum}(n) = \operatorname{sum}(n - 1) + n$

Damit die Funktion terminiert, muss noch der Rekursionsanfang (der Funktionswert für $0$ ) festgelegt werden:

$\operatorname{sum}(0) = 0$

Mit diesen Angaben lässt sich eine rekursive Definition der Summenfunktion angeben:

$\operatorname{sum}(n) = \left\{\begin{matrix} 0 && \mbox{falls } n = 0 && \mbox{(Rekursionsanfang)} \\ \operatorname{sum}(n-1)+n && \mbox{falls } n \ge 1 && \mbox{(Rekursionsschritt)} \end{matrix}\right.$

Die Summe der Zahlen von $0$ bis $3$ berechnet sich dann wie folgt:

$\begin{matrix} \operatorname{sum}(3) & = & \operatorname{sum}(2)+3 & \mbox{(Rekursionsschritt)} \\ & = & \operatorname{sum}(1)+2+3 & \mbox{(Rekursionsschritt)} \\ & = & \operatorname{sum}(0)+1+2+3 & \mbox{(Rekursionsschritt)} \\ & = & 0+1+2+3 & \mbox{(Rekursionsanfang)} \\ & = & 6 \end{matrix}$

[Bearbeiten] 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. Dabei ist n die Zahl, deren Fakultät berechnet werden soll.

 1 fakultät_rekursiv(n)
 2 {
 3   wenn n <= 1
 4       dann return 1
 5       sonst return ( n * fakultät_rekursiv(n-1) )
 6 }

Die Rekursion kommt in Zeile 5 zum Ausdruck, wo die Funktion sich selbst mit einem um 1 verringerten Argument aufruft. Hier wird die Funktion nur einmal aufgerufen und arbeitet dann linear den gegebenen Algorithmus ab:

 1 fakultät_iterativ(n)
 2 {
 3     fakultät = 1
 4     faktor = 2
 5     solange faktor <= n
 6     {
 7         fakultät = fakultät * faktor
 8         faktor = faktor + 1
 9     }
10     return fakultät
11 }

[Bearbeiten] Rekursiver pythagoreischer Baum

Pythagoras-Baum

Ein anderes, recht schön anzusehendes Beispiel ist der rekursive Pythagoras-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 Rekursionstiefe wiederholt. Bei der einfachen Rekursion entsteht ein Dreieck mit je einem Quadrat über den drei Seiten. Davon kommt auch der Name „pythagoreischer-Baum“. Nach mehreren Rekursions-Schritten ähnelt das Gebilde dann immer mehr einem Baum.

[Bearbeiten] Lösen von Rekursion

Beim Lösen einer Rekursion sucht man zum einen den Laufzeitaufwand, zum anderen die explizite Form der Rekursion.

Der Aufwand kann als asymptotische Θ- bzw. Ο-Schranke mittels Mastertheorem bzw. Substitutionsmethode bestimmt werden. Auch das „geschickte Raten“ mit anschließender Induktion bietet eine Möglichkeit, eine Oberschranke der Laufzeit zu ermitteln.

Die explizite Form (oder auch geschlossene Form genannt) der Rekursionsgleichung lässt sich beispielsweise durch die Erzeugende-Funktion finden. Eine zweite Möglichkeit bietet das „Ableiten“ durch Differenzenbildung aufeinanderfolgender Funktionswerte der Rekurrenz.