Rekursion in Java

Rekursion bedeutet Selbstbezüglichkeit und kann verwendet werden um komplexe Verfahren einfach zu beschreiben. In Java wird eine Rekursion durch einen Aufruf einer Methode umgesetzt, welche sich dann selbst wieder aufruft – dies nennt man einen rekursiven Aufruf.

Beispiele für Rekursion in Java

Eine Matrjoschka ist entweder die kleinstmöglichste Puppe oder eine Puppe, die selbst wieder eine andere Matrjoschka beinhaltet.

Ein Beispiel für die Verwendung einer Rekursion in der Mathematik ist die Berechnung der Fakultät einer Zahl. Die Fakultät ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 4 ist also 4*3*2*1 = 24.

Rekursiv definiert man die Fakultät (n!) meistens so:

• Die Fakultät der Zahl 1 ist 1.
• Für alle anderen Zahlen kann n! mit n! = n * (n-1)! berechnet werden.

Phasen der Rekursion in Java

Ein rekursiv definierter Algorithmus gliedert sich in der Regel in die folgenden drei Phasen:

1. Aktiver Fluss / Rekursiver Abstieg: Das aktuelle Problem wird solange „verkleinert“ bis ein Basisfall vorliegt. Es wird zuerst die Lösung der kleineren Instanz berechnet.
2. Basisfall: Das Ende der Rekursion ist erreicht, die Lösung dieses „kleinstmöglichen“ Problems kann unmittelbar per return zurückgegeben werden.
3. Passiver Fluss / Rekursiver Aufstieg: Die Teilergebnisse der kleineren Probleme werden jeweils an die nächst größere Ebene weitergegeben und so zu einer Gesamtlösung zusammengeführt.

Fakultätsfunktion mit Rekursion in Java

public class Programm {

    public static void main(String[] args) {
        System.out.println(fakultaet(4));
    }

    public static int fakultaet (int n) {
        return n*fakultaet(n-1);
    }
}

Exception in thread "main" java.lang.StackOverflowError

Das von uns geschriebene Programm wirft eine Exception. Der StackOverflowError bedeutet, dass das Programm nicht terminiert und bis zum Abbruch weiterlaufen würde. Dies liegt daran, dass wir keine Abbruchbedingung oder einen Basisfall angegeben haben. Das Rekurisonsende ist in diesem Fall erreicht, wenn die Variable x gleich 1 oder 0 ist, denn dann ist keine weitere Berechnung notwendig.

Wir ergänzen unseren Algorithmus wie folgt:

ppublic class Programm {

    public static void main(String[] args) {
        System.out.println(fakultaet(4));
    }

    public static int fakultaet (int n) {
        if((n==0)||(n==1))
            return 1;
        else
            return n*fakultaet(n-1);
    }
}

24

Nun beim letzten Aufruf der Methode mit dem Parameter n = 1 wurde unser Basisfall erreicht und per return 1 zurückgegeben.

Fibonaccifolge in Java

Auch für die Fibonaccifolge kann mittels Rekursion ein einfacher Algorithmus angegeben werden.

• Die Fibonaccizahl von 0 oder 1 ist 1
• Wenn die Zahl nicht 0 oder 1 ist berechnet sich die Fibonaccizahl durch fib(n-1) + fib(n-2)

Die Berechnung kann gut mit einem Aufrufbaum nachvollzogen werden.

public class Programm {

    public static void main(String[] args) {
        System.out.println(fib(4));
    }

    private static int fib(int n){
        if((n==1)||(n==0))
            return 1;
        else
            return fib(n-1)+fib(n-2);
    }
}

5