Hauptmenü öffnen

Rekursion

zentraler Begriff der Mathematik und der Linguistik
(Weitergeleitet von Rekursiv)
Ein Beispiel von Rekursion: Rückkopplung im VLC media player bei anzeigen des eigenen Bildschirms.

Als Rekursion (lateinisch recurrere ‚zurücklaufen‘) bezeichnet man den abstrakten Vorgang, dass Regeln auf ein Produkt, das sie hervorgebracht haben, von neuem angewandt werden. Hierdurch entstehen potenziell unendliche Schleifen. Regeln bzw. Regelsysteme heißen rekursiv, wenn sie die Eigenschaft haben, Rekursion im Prinzip zuzulassen.

Rekursion ist ein zentraler Begriff in Mathematik, Logik und Informatik und hat vielfältige Anwendungen darüber hinaus; diese reichen bis in die Kunst, wo das Phänomen auch als mise en abyme bezeichnet worden ist.

Rekursion ist auch eine Problemlösungsstrategie. Komplexe Sachverhalte können oft mit rekursiv formulierten Regeln sehr elegant erfasst werden. Das Grundprinzip ist dabei dann das Zurückführen einer allgemeinen Aufgabe auf eine einfachere Aufgabe derselben Klasse. Beispielsweise ist die rekursive Programmierung Bestandteil vieler Programmiersprachen. Prozeduren oder Funktionen können sich dabei selbst aufrufen. Rekursion und Iteration sind im Wesentlichen gleichmächtige Sprachmittel.

In Mathematik, Logik und Informatik erscheint Rekursion spezieller in der Form, dass eine Funktion in ihrer Definition selbst nochmals aufgerufen wird (rekursive Definition). Wenn man mehrere Funktionen durch wechselseitige Verwendung voneinander definiert, spricht man von wechselseitiger Rekursion. Nicht jede rekursive Definition ist eine Definition im eigentlichen Sinn, denn die zu definierende Funktion braucht nicht wohldefiniert zu sein. Jeder Aufruf der rekursiven Funktion muss sich durch Entfalten der rekursiven Definition in endlich vielen Schritten auflösen lassen. Ist dies nicht erfüllt, so spricht man von einem infiniten Regress (in der Informatik auch als Endlosschleife bezeichnet).

Inhaltsverzeichnis

Anwendungsbereiche und Beispiele für RekursionBearbeiten

Rekursive GrafikenBearbeiten

 
„Sprießender“ Pythagoras-Baum

Unter anderem können auch Punktmengen rekursiv definiert werden (dies ergibt die sogenannten Fraktale). Deren graphische Darstellung liefert ästhetisch ansprechende, natürlich aussehende Gebilde. Ein Beispiel ist der Pythagoras-Baum. Der dazugehörige Algorithmus sieht folgendermaßen aus; der dritte Teil enthält die Rekursion:

  • Errichte über zwei gegebenen Punkten ein Quadrat.
  • Auf der Oberseite zeichne ein Dreieck mit vorgegebenen Winkeln bzw. Höhe.
  • Wende die beiden obigen Schritte jeweils erneut auf die beiden Schenkel des neuentstandenen Dreieckes an.

Der Algorithmus wird dann bis zu einer vorgegebenen Rekursionstiefe entfaltet. Bei Rekursionstiefe eins entsteht ein Dreieck mit je einem Quadrat über den drei Seiten. Das sieht wie die Illustration zum Satz des Pythagoras aus – daher der Name. Je höher die Rekursionstiefe, desto mehr ähnelt das Gebilde einem Baum.

Rekursion in der GrammatikBearbeiten

Die Grammatik natürlicher Sprachen wird in der Linguistik u. a. mit Hilfe von sogenannten Phrasenstrukturregeln beschrieben.[1] Nach Ansicht der meisten Linguisten zeigen dabei alle menschlichen Sprachen[2] die Eigenschaft, rekursiv aufgebaut zu sein (im Gegensatz zu Signalsystemen im Tierreich). Dies ergibt sich, weil in der Zerlegung einer grammatischen Einheit, die mit einer Kategorie etikettiert wird, dieselbe Kategorie erneut auftauchen kann. Ein Beispiel ist das Phänomen der Nebensätze, das hier mit folgender stark vereinfachter Produktionsregel beschrieben ist:

  1. S → NP VP (ein Satz besteht aus einer Nominalphrase (als Subjekt) und einer Verbalphrase)
  2. VP → V NP* (eine Verbalphrase besteht aus einem Verb und null bis vielen Nominalphrasen als Objekten des Verbs)
  3. VP → V S (eine Verbalphrase besteht aus einem Verb und einem Nebensatz als Objekt des Verbs)

Diese Grammatik lässt die Wahl, ob die Ausbuchstabierung von „VP“ mit Regel 2 oder 3 erfolgen soll. Für den Fall, dass die Schritte 1 und dann 3 aufgerufen werden, ergibt sich eine Rekursion: Als Produkt von Regel 3 erscheint das Symbol S, das wiederum den Start für Regel 1 darstellt.

Rekursion in der MathematikBearbeiten

FakultätBearbeiten

Die Funktion Fakultät einer Zahl n > 1 ist definiert als das Produkt der Zahlen 1 bis n:

 

Beispiele

 

Soll diese Liste fortgesetzt werden, ergibt sich die Rekursivität nahezu von selbst. Für die Berechnung von 5! wird man nicht von vorn beginnen, sondern kann auf vorherige Ergebnisse zurückgreifen, also

 

Verallgemeinert lässt sich die Funktion somit rekursiv definieren:

 

Die Fibonacci-FolgeBearbeiten

Ein klassisches Beispiel für eine rekursive Funktion ist die Fibonacci-Folge, bei der jedes weitere Folgenglied die Summe der beiden vorhergehenden ist:

 

Im Gegensatz zur Fakultätsfunktion gibt es hier keine triviale geschlossene Darstellung. Die einfachste Beschreibung ist die rekursive Definition:

 

Diese rekursive Definition ist kaskadenförmig. Die dritte Fibonacci-Zahl wird anhand dieser Definition folgendermaßen berechnet:

 

Die Berechnung für   wird hier mehrfach durchgeführt. Das deutet an, dass es Potential für Optimierungen gibt.

Rekursive Definition einer Funktion und Untertypen von RekursionBearbeiten

Mathematische DefinitionBearbeiten

(Hinweis vorab: Rekursionsverfahren und rekursive Definitionen sind nicht auf Funktionen natürlicher Zahlen 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 : N0N0 ergibt sich durch Verknüpfung bereits berechneter Werte f(n), f(n-1), … Falls 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 die Funktion so oft selbst auf, bis eine durch den Aufruf der Funktion veränderte Variable einen vorgegebenen Zielwert erreicht oder Grenzwert überschritten hat (Terminierung, Abbruchbedingung).

Die Definition von rekursiv festgelegten Funktionen ist eine grundsätzliche Vorgehensweise in der funktionalen Programmierung. Ausgehend von einigen gegebenen Funktionen (wie z. B. der Summenfunktion) 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 Aufrufbaum keine Verzweigungen, das heißt, er ist eine Aufrufkette: das ist immer dann der Fall, wenn eine rekursive Funktion sich selbst jeweils nur einmal aufruft. Der Aufruf kann dabei am Anfang (Head Recursion, siehe Infiniter Regress) oder am Ende (Tail Recursion oder Endrekursion) der Funktion erfolgen. Umgekehrt kann jede Iteration durch eine primitive Rekursion ersetzt werden, ohne dass sich dabei die Komplexität des Algorithmus ändert.

Formen der RekursionBearbeiten

Die häufigste Rekursionsform ist die lineare Rekursion, bei der in jedem Fall der rekursiven Definition höchstens ein rekursiver Aufruf vorkommen darf. Die Berechnung verläuft dann entlang einer Kette von Aufrufen.

Die primitive Rekursion ist ein Spezialfall der linearen Rekursion. Hier definiert man Funktionen auf den natürlichen Zahlen, wobei in jedem rekursiven Aufruf dessen erster Parameter um Eins ab- oder zunimmt. Jede primitiv-rekursive Definition kann unter Zuhilfenahme eines Stapels durch eine Schleife (Programmierung) (z. B. For-Schleife oder While-Schleife) ersetzt werden.

Die endständige oder repetitive Rekursion (Tail Recursion oder Endrekursion) bezeichnet den Spezialfall der linearen Rekursion, bei der jeder rekursive Aufruf die letzte Aktion des rekursiven Aufrufs ist. Endrekursionen lassen sich unmittelbar durch While-Schleifen ersetzen und umgekehrt.

Unter verschachtelter Rekursion versteht man eine Rekursion, bei welcher rekursive Aufrufe in Parameterausdrücken rekursiver Aufrufe vorkommen. Diese Rekursionsform gilt als außerordentlich schwer zu durchschauen.

Kaskadenförmige Rekursion bezeichnet den Fall, in dem mehrere rekursive Aufrufe nebeneinander stehen. Die rekursiven Aufrufe bilden dann einen Baum. Kaskadenförmige Rekursion gilt als elegant, kann aber ohne weitere Maßnahmen einen exponentiellen Berechnungsaufwand nach sich ziehen. Sie wird gerne als Ausgangspunkt für die Ableitung einer anderen effizienteren Formulierung gebraucht.

Die wechselseitige Rekursion bezeichnet die Definition mehrerer Funktionen durch wechselseitige Verwendung voneinander. Sie lässt sich auf die gewöhnliche Rekursion einer tupelwertigen Funktion zurückführen.

Weitere Anwendungen: Rekursion in der ProgrammierungBearbeiten

Höhere Programmiersprachen die mit Funktionen arbeiten, erlauben üblicherweise auch die Rekursion. Zumeist lassen sich Lösungen rekursiv oder iterativ lösen, siehe Rekursive Programmierung und Iterative Programmierung.

Häufig ist der Quelltext einer rekursiven Programmierung eleganter als die iterative Umsetzung, da keine Hilfsvariablen und Schleifenzähler definiert werden müssen. In der Abarbeitung sind iterative Verfahren meist effizienter und benötigen weniger Speicherplatz. Grund ist das Ablegen der wiederholten Funktionsaufrufe mit allen zwischengespeicherten Werten auf dem Stapelspeicher (Stack). Insbesondere kann die Rekursion auch einen Pufferüberlauf (Stack Overflow) verursachen. Bei der Programmierung von Echtzeitsystemen auf Mikrocontrollern wird daher häufig auf Rekursion verzichtet.

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

Es ist zu beachten, dass eine naive Implementierung bei manchen Funktionen (z. B. den Fibonacci-Zahlen) bedingt, dass Teillösungen mehrfach berechnet werden. Abhilfe schafft in diesem Beispiel die Memoisation, 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 auch Lambda-Kalkül und Ackermannfunktion).

Im Compilerbau ist der rekursive Abstieg (Recursive Descent) eine Technik, bei der eine Sprache rekursiv geparst wird.

ProgrammierbeispieleBearbeiten

Das folgende Beispiel zeigt eine einfache und beliebte Implementierung der Fakultätsfunktion in der Programmiersprache Python. Der rekursiven Variante wird hier zur Verdeutlichung eine iterative Variante gegenübergestellt. Die Rekursion kommt dadurch zum Ausdruck, dass die Funktion sich selbst mit einem um 1 verringerten Argument aufruft. Beide Implementierungen führen den Algorithmus mit linearer Laufzeitkomplexität in Abhängigkeit zum Eingabeparameter aus. Während die Platzkomplexität bei der iterativen Variante konstant bleibt, wächst der Speicherbedarf bei der rekursiven Variante linear an, da bei jedem rekursiven Funktionsaufruf ein neuer Speicherbereich für die lokalen Variablen und die Rücksprungadresse reserviert werden muss. Bei der funktionalen Programmierung wird die dynamische Speicherverwaltung durch einen Aufrufstapel realisiert.

Iterative Programmierung Rekursive Programmierung
def factorial(number):
    result = 1
    
    while number > 1:
        result *= number
        number -= 1
    
    return result
def factorial(number):
    if number <= 1:
        return 1
    
    return number * factorial(number - 1)

Das nächste Beispiel implementiert die Fibonacci-Folge in der Programmiersprache C. Bei der rekursiven Variante handelt es sich um eine Mehrfachrekursion, die zu einer exponentiellen Laufzeit- und Platzkomplexität führt. Die rekursiven Funktionsaufrufe verzweigen sich zu einem Binärbaum, bei dem identische Teilergebnisse mehrfach berechnet werden. Am häufigsten werden die Fibonaccizahlen an den Stellen 0 und 1 berechnet, welche die Abbruchbedingung in der Rekursion definieren. Bei der iterativen Variante ist die Laufzeitkomplexität linear und die Platzkomplexität konstant.

Iterative Programmierung Rekursive Programmierung
int fibonacci(int number) {
    int result = 0, next = 1;
    
    for (int count = 0; count < number; ++count) {
        int swap = result;
        result = next;
        next += swap;
    }
    
    return result;
}
int fibonacci(int number) {
    if (number <= 0)
        return 0;
    
    if (number == 1)
        return 1;
    
    return fibonacci(number - 1) + fibonacci(number - 2);
}

Lösen von RekursionenBearbeiten

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.

Siehe auchBearbeiten

WeblinksBearbeiten

  Wiktionary: Rekursion – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
  Wiktionary: rekursiv – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise und AnmerkungenBearbeiten

  1. Siehe z. B. Andrew Carnie: Constituent Structure. Second edition. Oxford University Press, 2010. Zum Thema Rekursivität v. a. S. 84ff.
  2. Lediglich für die Sprache Pirahã ist die These vorgebracht worden, dass sie keine Rekursion in der Grammatik kennen würde, da es keine Nebensätze gebe. Diese Analyse ist umstritten, für Details siehe den verlinkten Artikel.