Rekursion

Rekursion bedeutet Selbstbezüglichkeit (von lateinisch recurrere = zurücklaufen). Sie tritt immer dann auf, wenn etwas auf sich selbst verweist. Ein rekursives Element muss nicht direkt auf sich selbst verweisen, eine Rekursion kann auch über mehrere Zwischenschritte entstehen. Rekursion kann dazu führen, dass merkwürdige Schleifen entstehen. So ist z. B. der Satz "Dieser Satz ist unwahr" rekursiv, da er von sich selber spricht.

Eine etwas subtilere Form der Rekursion (indirekte Rekursion) kann auftreten, wenn zwei Dinge gegenseitig aufeinander verweisen. Ein Beispiel sind die beiden Sätze: "Der folgende Satz ist wahr" "Der vorhergehende Satz ist nicht wahr".

Die Probleme beim Verständnis von Rekursion beschreibt der Satz: "Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen".

Rekursion 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 eine 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: 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. 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 Hilfe derer weitere Funktionen definiert werden können.

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 eine bessere Performanz zeigt (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, so dass 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 tun das).

Es ist zu beachten, dass die rekursive Implementation bei manchen Funktionen (z. B. den Fibonacci-Zahlen) bedingt, dass Teillösungen mehrfach berechnet werden, was eine Verlängerung der Laufzeit bedeutet.

Die Rekursion ist ein wesentlicher Bestandteil einiger Entwurfsstrategien für effiziente Algorithmen, insbesondere der Teile und Herrsche (Devide and Conquer) Strategie. Andere Ansätze (zum Beispiel so genannte Greedy Algorithmen) verlangen ein iteratives vorgehen.

Rekursion und primitiv-rekursive Funktionen spielt eine grosse Rolle in der theoretischen Informatik, insbesondere in der Komplexitätstheorie und Berechenbarkeitstheorie. Siehe dazu auch Lambda-Kalkül und Ackermann-Funktion. Im Compilerbau ist der rekursive Abstieg (Recursive Descent) eine Technik, bei der eine Sprache rekursiv geparst wird.

Beispiel

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

Die beliebte und einfache Implementierung der Fakultätsberechnung. Hier als rekursive und iterative Variante, in der Programmiersprache Java.

public class Faculty {

  public static void main(String[] args) {

   try { System.out.println(args[0]+"! = " + facultyRec(Integer.parseInt(args[0])));}

   catch (RuntimeException t) { System.err.println("Ungültiger Parameter !"); }

  }

  /** Rekursive Methode zur Fakultätsberechnung */

  public static long facultyRec(int n) {

   return n==0?1:n*facultyRec(Math.abs(n)-1);

  }

  /** Nicht-rekursive (iterative) Methode zur Fakultätsberechnung */

  public static long facultyNonRec(int n) {

   int i = 1;

   while (Math.abs(n) > 0) {

    i *= n;

    n = Math.abs(n) - 1;

   }

   return i;

  }

 }