Rekurrente

Rekursion, auch Rekurrenz oder Rekursivität (von lateinischrecurrere = zurücklaufen) ist ein allgemeines Prinzipzur Lösung von Problemen. In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu ?eleganten? mathematischenLösungen. Als Rekursion bezeichnet man den Aufruf oder die Definition einer Funktiondurch sich selbst. Ohne geeignete Abbruchbedingunggeraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress(umgangssprachlich Endlosschleife).

Zur Vermeidung von infinitem Regress insbesondere in Computerprogrammenbedient man sich der semantischenVerifikationvon rekursiven Funktionen. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels einer Schleifeninvariantegefü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 Rekursionsschemaverwiesen.)

Das Grundprinzip der rekursiven Definitioneiner Funktion f ist: Der Funktionswert f(n+1) einer Funktion f: N₀ ? N₀ ergibt sich durch Verknüpfungbereits 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 Iterationersetzt 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ätdes Algorithmus ändert.

Anwendung

Im Fall von primitiv-rekursiven Funktionen steht es dem Programmierer frei, eine iterative oder eine rekursive Implementationzu wählen. Dabei ist die rekursive Umsetzung meist ?eleganter?, während die iterative Umsetzung effizienterist (insbesondere weil der Stackweniger beansprucht wird und der Overheadfü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 Optimierungprimitive Rekursionen intern als Iterationen um (insbesondere einige Interpreter für Lispund Schemeverfahren 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 effizienteAlgorithmen, 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 Funktionenspielen eine große Rolle in der theoretischen Informatik, insbesondere in der Komplexitätstheorieund Berechenbarkeitstheorie(siehe Lambda-Kalkülund Ackermann-Funktion).

Im Compilerbauist der rekursive Abstieg(Recursive Descent) eine Technik, bei der eine Spracherekursiv ?geparst? wird.

Beispiele

Hier ein Beispiel für eine Funktion sum: N₀ ? N₀, die die Summe der ersten n Zahlen berechnet:

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ätsberechnungmittels Pseudocode. Der rekursiven Variante wird hier zu Verdeutlichung eine iterativeVariante 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 Argumentaufruft.

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

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 einem Baum.

Siehe auch

• µ-Rekursion
• Euklidischer Algorithmus
• Funktion (Programmierung)
• Kellerautomat
• Master Theoremzur Berechnung der Laufzeit
• Rekursionsgleichung
• Rekursionssatz
• Rekursives Akronym
• Stackbg:????????

ca:Recursivitat cs:Rekurze da:Rekursiv en:Recursion es:Recursión fr:Récursivité he:??????? id:Rekursi io:Rekurso it:Ricorsione lt:Rekursija nl:Recursie pl:Rekursja ru:???????? sl:Rekurzija sv:Rekursion zh:??

Dieser Artikel basiert auf dem Artikel aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation.
In der Wikipedia ist eine Liste der Autoren verfügbar.