Java/Rekursion

Als Rekursion (auch Rekurrenz oder Rekursivität), von lateinisch recurrere entspr. 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). Rekursion, Wikipedia – Die freie Enzyklopädie, 21.11.2006 - Der Text ist unter der Lizenz „Creative Commons Attribution/Share Alike“ verfügbar; zusätzliche Bedingungen können anwendbar sein. Siehe die Nutzungsbedingungen für Einzelheiten. In der Wikipedia ist eine Liste der Autoren verfügbar.

Beispiel

Fakultät:
5! = 1 * 2 * 3 * 4 * 5

rekursiv

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

iterativ

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}

Listenausgabe

(Setzt Java/List o.ä. voraus)

    private void rekursiveAusgabe() {
        if (liste.isBehind()){
            System.out.println("Fertig.");
        }
        else {
            System.out.println(liste.getItem()+"\n"); 
            liste.next();
            rekursiveAusgabe();
            System.out.println("*");
        }
    }

Übung

• Vergleichen Sie die iterativen und rekursiven Fakultätsmethoden-Varianten. Übersetzen Sie den Pseudo-Code in Java.
• Analysieren Sie die oben stehende Methode rekursiveAusgabe(). Gehen Sie dabei vor allem auch auf die Bildschirmausgabe der Sternchen ein.
• Recherchieren Sie nach weiteren Beispielen.