Datenstrukturen und Algorithmen

Iterativ vs Rekursiv

Im vorherigen Abschnitt haben wir schon eine Reihe kleiner Algorithmen umgesetzt, damit wir mit unserer Single Linked List arbeiten konnten. Dabei haben wir uns ausschließlich auf iterative Ansätze beschränkt. Das heißt, dass wir die Liste immer nur mit hilfe von Schleifen abgelaufen sind. Als Beispiel hierzu noch einmal die Methodendefinition von “laenge”.


    public static int laenge(SingleLinkedList liste) {

        // Leere Liste erkennen und danach stoppen
        if(liste == null) {
            return 0;
        }

        // Elemente zählen
        int laenge = 1;
        while(liste.next != null) {
            liste = liste.next;
            laenge ++;
        }

        return laenge;
    }

Bei einer rekursiven Umsetzung würde eine Methode sich selbst wieder aufrufen um einen Teil des Problems darin zu lösen und diese Teillösung dann in ein Ergebnis zusammenzufügen.

Unsere Beispielfunktion könnte mit Hilfe von Rekursion wie folgt umgesetzt werden.



    public static int laenge(SingleLinkedList liste) {

        if(liste == null) {
            return 0;
        } else {
            return laenge(liste.next) + 1;
        }
    }

Es ist leicht zu sehen, dass der rekursive Ansatz bei diesem Problem mit weniger Schreibarbeit umgesetzt werden kann. Das ist nicht in jedem Fall so. Auch ist in diesem Fall die iterative Implementierung sicherlich vom Laufzeitverhalten sicherlich besser. Es gibt aber Problemstellungen, die sich in nach dem einen oder anderen Verfahren wesentlich besser umsetzen lassen.