Was ist Rekursion?

Unter Rekursion versteht man in der Programmierung ein Verfahren, bei dem sich eine Methode selbst aufruft, sodass, ähnlich einer Endlosschleife, ein potentiell unendlicher Programmablauf entsteht.

void m() {
    m();
}

Setzt man die Abbruchbedingung korrekt, so kann durch Rekursion ein und der selbe Algorithmus auf oft recht elegant Weise mehrfach wiederholt werden. Das folgende Codebeispiel zeigt die Berechnung der Fakultät, bei der, beginnend bei einem oberen Grenzwert, dieser so lange mit dem um 1 verminderten Betrag multipliziert wird, bis der Multiplikand 1 erreicht hat.

5! = 5*4*3*2*1 = 120

Eine rekursive Berechnung von 5! kann durch das folgende kleine Programm erfolgen:

public class Fakultaet {
    public static void main(String[] args) {
        System.out.println(fakultaet(5));
    }
    private static int fakultaet(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return fakultaet(n - 1) * n;
        }
    }
}

Die Methode fakultaet() wird hier initial mit dem Parameter 5 aufgerufen, sodass die Ausgabe nach Abschluss der Berechnung 120 ergibt. Das Ergebnis wird schließlich in main() auf die Konsole ausgegeben. Was geschieht hier beim Programmablauf genau?

Der initial übergebene Parameter 5 ist größer als 1. Somit tritt der else-Fall der Verzweigung ein. Hier wird eine Rückgabe durch return eingeleitet, jedoch noch nicht sofort ausgeführt, da zunächst der rechts davon stehende Ausdruck ausgewertet werden muss. Hier, also bevor die Rückgabe erfolgt, wird eine Multiplikation durchgeführt, bei der der Multiplikand der Methodenparameter 5 ist, der Multiplikator jedoch aus einem neuerlichen Methodenaufruf mit dem um 1 verminderten Parameter 4 besteht. Dieser muss natürlich zunächst berechnet werden, bevor die Multiplikation mit 5 stattfinden kann. Bevor also irgendetwas zurückgegeben wird, muss somit zunächst folgende Berechnung stattfinden

4! * 5

wobei 4! wiederum natürlich erst ermittelt werden muss. Bei der Berechnung von fakultaet(4) wird n mit 4 belegt, sodass, nach dem obigen Ablauf, aus diesem isolierten Berechnungsschritt

3! * 4

resultiert. Achtung: die vorhergehende Berechung mit dem Multiplikanden 5 ist jedoch immer noch nicht abgeschlossen, da deren Multiplikator ja z.Zt. noch berechnet wird, sodass sich schließlich bis hierher

3! * 4 * 5

ergibt. Dieses Verfahren läuft so lange ab, bis n-1 den Wert 1 erreicht hat. Die Methode wird mit 1 als Parameter aufgerufen, die Rekursion wird durch die Verzweigung terminiert und durch die Rückgabe von 1 resultiert schließlich die Berechnung von

1 * 2 * 3 * 4 * 5

deren Ergebnis final zurückgegeben und schließlich in main() ausgegeben wird.

Iterativ oder rekursiv?

Die o.a. Berechnung der Fakultät kann auch iterativ gelöst werden:

public class Fakultaet {
    public static void main(String[] args) {
        System.out.println(fakultaet(5));
    }
    private static int fakultaet(int n) {
        int i = 1;
        int result = 1;
        while(i<n) {
            result *= (++i);
        }
        return result;
    }
}

Es stellt sich die Frage, ob geeignete Lösungen eher iterativ oder rekursiv angestrebt werden sollten. Die Antwort ist nicht leicht zu geben und kann streng genommen nur von Fall zu Fall entschieden werden. Beide Verfahren haben ihre spezifischen Eigenheiten, die jeweils als Vor- oder Nachteil gewertet werden können:

Bei komplexen Berechnungen sind Rekursionen i.A. eleganter, leichter lesbar und liefern oft den kompakteren Code, wöhrend iterative Lösungen aufgrund des geringeren Overheads effizienter und oft leichter verständlich sind.

Weitere Rekursionsbeispiele

Wenn Ihnen javabeginners.de gefällt, freue ich mich über eine Spende an diese gemeinnützigen Organisationen.