Literatur

Iteration und Rekursion

Methoden können sowohl iterativ als auch rekursiv verwendet werden. Unter einer Iteration (lat. Wiederholung) versteht man die mehrfache Ausführung einer oder mehrerer Anweisungen. Die Iteration realisiert man durch Schleifen (for, while..). Mittels einer Abbruchbedingung wird die Schleife beendet.

Von Rekursion (von lateinisch recurrere = zurücklaufen) spricht man, wenn eine Methode sich selbst immer wieder aufruft bis eine Abbruchbedingung erfüllt ist. Jede Rekursion lässt sich auch in eine iterative Lösung umwandeln und umgekehrt.

Iterationen haben den Vorteil, dass sie performanter sind. Eine Rekursion kommt jedoch meistens mit weniger Quellcode aus und ist übersichtlicher, jedoch dafür speicherintensiver. Rekursionen werden allerdings oft  von Programmieranfängern schwerer verstanden.

In den nun folgenden Beispielen berechnen wir die Fakultät einer ganzen positiven Zahl (als mathematisches Symbol ein "!" hinter der Zahl) einmal iterativ und einmal rekursiv. Schon die Definition ist rekursiv: 0! = 1, 1!= 1, (n>1)! = n * (n-1)!

Hier die iterative Lösung:

class IterativFakultaet
{
    // Methode zur Berechnung der Fakultät
    static long berechneFakultaet(int n)
    {
        long faku =1;
        // Iterative Berechnung
        for(int i = 1; i<=n; i++)
        {
            faku *= i;
        }
        return faku;
    }
 
    public static void main(String[ ] args)
    {
        long faku = berechneFakultaet(5);
        System.out.println("5! = "+faku);
    }
}


Schauen wir uns nun die Berechnung einer Fakultät mit Hilfe einer Rekursion an.

class RekursivFakultaet
{
    static long berechneFakultaet(int n)
    {
        System.out.println("Aufruf mit "+n);
        if(n>=1)
        {
              // rekursiver Aufruf (ruft sich selbst auf)
              return n*berechneFakultaet(n-1);
        }
        else
        {
              // Abbruchbedingung der Rekursion
              return 1;
        }
    }
 
    public static void main(String[ ] args)
    {
        long faku = berechneFakultaet(5);
        System.out.println("5! = "+faku);
    }
}

Zur Verdeutlichung der Rekursion schauen wir uns nun einmal im Detail an, was passiert.

if(n>=1)
       return n*berechneFakultaet(n-1);
   else
       return 1;

1. Aufruf mit 5:        5* berechneFakultaet(5-1)   
2. Aufruf mit 4:        5* 4* berechneFakultaet(4-1)    
3. Aufruf mit 3:        5* 4* 3* berechneFakultaet(3-1)    
4. Aufruf mit 2:        5* 4* 3* 2* berechneFakultaet(2-1)    
5. Aufruf mit 1:        5* 4* 3* 2* 1* berechneFakultaet(1-1)    
6. Aufruf mit 0:        5* 4* 3* 2* 1* 1

Erst mit dem sechsten Aufruf ist die Rekursion beendet und gibt dann den errechneten Wert zurück.

Es soll nicht unerwähnt bleiben, dass das Beispiel der Fakultät keines ist, das man in der Praxis unbedingt rekursiv lösen würde. In diesem Fall ist die Schleife nicht nur leichter zu lesen, sondern auch speichereffizienter (jeder Aufruf belegt Ressourcen!) und auch im Laufzeitverhalten wesentlich besser.

Scheinbar spricht also alles gegen Rekursionen. Allerdings gibt es auch Problemstellungen, die man mit Schleifen nur sehr schwer (aber niemals gar nicht!) lösen kann.

Hier zwei Beispiele dazu:

1.)
Eine Methode listFiles(String folder, String substring) soll in dem Ordnerbaum im und unter dem durch den Parameter "folder" angegebenen Ordner alle Dateien finden, deren Namen die im Parameter "substring"  angegebene Zeichenkette enthalten.

Das Problem lässt sich aufteilen:
i. Liste die entsprechenden Dateien im angegebenen Ordner
ii. rufe listFiles(String folder, String substring) für jeden Ordner im angegebenen Order auf.

Durch Schritt ii entsteht die Rekursion, die in diesem Fall viel besser zu lesen ist, als es jeder Versuch wäre, das Problem mit Schleifen zu lösen.

2.)  Das bekannte Spiel "Türme von Hanoi", bei dem ein Stapel aus n von unten nach oben kleiner werdenden Scheiben (darstellbar z.B. mit einem Array s[], der Datentyp soll uns hier nicht interessieren) von einem Turm (z.B. a, b, c) auf einen anderen verbracht werden muss, wobei a) immer nur eine Scheibe bewegt werden darf, die b) niemals auf eine kleinere Scheibe abgelegt werden darf.

Das Problem: Die unterste Scheibe s[0] soll von Turm a auf Turm b gebracht werden. Wieder lässt sich das Problem aufteilen:
i. "Parke" den Scheibenturm über s[0] (also s[1]..s[n-1]) auf  Turm c (dieser Schritt bildet die Rekursion)
ii. lege s[0] auf Turm b
iii. "Parke" den Turm auf und inklusive der in i. geparkten Scheibe von c auf b (dadurch wird der geparkte Turm "geholt"; auch dieser Schritt ist rekursiv)

In beiden Fällen ist es wichtig, sich Gedanken darüber zu machen, ob die Rekursion zu einem Ende finden wird. Im zweiten Beispiel ist das gegeben, weil jeder Turm nur eine begrenzte Anzahl an Scheiben hat. Im ersten, da Ordnerbäume nicht unendlich tief sein können. Aber Achtung: Beispielsweise können in Unix-artigen  Betriebssystemen mit so genannten "hard
links" oder "symbolic links" sehr wohl scheinbare Endlosstrukturen geschaffen werden! Damit wollen wir nur verdeutlichen, dass der Teufel oft im Detail steckt, und Rekursionen sorgfältig durchdacht und geplant sein wollen.