Jetzt anmelden...

Login
Passwort
Registrieren
25.02.22 859 Views Kommentare [0] 0 0

credit: Brian/ adobe

Java Tutorial #13

Rekursive Methoden in Java

Die Rekursion ist eine Technik nicht nur für Feinschmecker der Programmierung. Mit ihr kann man so einiges Praktisches anstellen und logische Probleme mit elegantem Code lösen.

Falconbyte unterstüzen

Betrieb und Pflege von Falconbyte brauchen viel Zeit und Geld. Um dir auch weiterhin hochwertigen Content anbieten zu können, kannst du uns sehr gerne mit einem kleinen "Trinkgeld" unterstützen.

Thema in Kurzform

  • Unter rekursiver Programmiererung versteht man eine Methode, die sich selbst aufruft.
  • Wichtiger Bestandteil der Rekursion ist die Abruchbedingung innerhalb der Methode, ohne die das Programm zum Absturz kommt.

    Inhaltsverzeichnis

  1. Unterschied iterativ und rekursiv
  2. Rekursion mit Parameter und Rückgabetyp
  3. Lineare vs. verzweigte Rekursion

Unterschied iterativ und rekursiv

Wenn wir ein bestimmtes Problem durch einen Algorithmus lösen wollen, stehen uns zwei Vorgehensweisen zur Wiederholung zur Verfügung:

  • iterativ: Wir führen eine Aktion mithilfe von Schleifen wiederholt durch.
  • rekursiv: Die Wiederholung der Aktion erfolgt dadurch, dass sich eine Methode selbst (mehrmals) aufruft.

Sehen wir uns kurz noch ein Beispiel für den bekannten iterativen Ansatz mit einer while-Schleife an:

int i = 0;
while(i < 10){
    System.out.print(++i + " ");
}            

Output: 1 2 3 4 5 6 7 8 9 10

Und jetzt rekursiv!

Um diese Lösung rekursiv umzusetzen, brauchen wir eine Methode, die sich selbst aufruft. Wir nennen eine solche Methode dann rekursive Methode.

Eine rekursive Methode mit passender Klasse sieht dann so aus:

public class Rekursiv {

    public static int i = 0;

    public static void rekursiveMethode() {
        i++;
        System.out.print(i + " ");
        if (i < 10) {
            rekursiveMethode(); // Rekursion!
        }
    }

    public static void main(String[] args) {
        rekursiveMethode();
    }

}            

Jeder rekursive Methodenaufruf packt ein neues Element zum Abarbeiten auf den Stack der JVM.

Deshalb ist eine zentrale Bedingung für das ordentliche Funktionieren einer rekursiven Methode das Vorhandensein einer Abbruchbedingung (hier i < 10). Ohne diese "explodiert" der Stack und unser unser Code wird unweigerlich einen java.lang.StackOverflowError erzeugen und krepieren.

Rekursion mit Parameter und Rückgabetyp

Im Beispiel oben, haben wir eine sehr einfache rekursive Methode programmiert. Oftmals ist es aber nicht ganz so simpel und wir brauchen "vollwertige" Methoden mit Parametern und Rückgabetyp.

Das nächste Beispiel zeigt eine solche Methode. Wir nennen sie sum() und verwenden sie, um alle Zahlen zwischen 1 und 6 zu summieren:

public class Rekursiv {

    public static void main(String[] args) {
        int result = sum(6);
        System.out.println(result);
    }
    public static int sum(int n) {
        if (n > 0) {
            return n + sum(n - 1); // Rekursion
        } else {
            return 0;
        }
    }
}

Das Ergebnis der Rekursion lautet 21.

Doch wie kommt es dazu? Schauen wir uns Schritt für Schritt an, was die Methode macht:

Die Methode sum() hat einen Parameter n für eine Ganzzahl. Beim ersten Initial-Aufruf in der Main-Methode ist das konkret der Wert 6. Bei den folgenden rekursiven Aufrufen wird n - 1 als Argument übergeben und zwar solange, wie n größer ist als 0 (= Abbruchbedingung). Der letzte rekursive Aufruf lautet damit sum(0).

Jeder Methodenaufruf liefert auch einen entsprechenden Wert zurück, der auf n summiert wird.

Die Rekursion stoppt, wenn n den Wert 0 hat. Dann wird 0 zurückgeliefert und es folgt kein weiterer Aufruf. Die Rekursion ist beendet und die Summe von 21 ist gebildet.

In der Gesamtheit absolviert die Rekursion folgende Einzelschritte:

6 + sum(5)
6 + ( 5 + sum(4) )
6 + ( 5 + ( 4 + sum(3) ) )
6 + ( 5 + ( 4 + ( 3 + sum(2) ) ) )
6 + ( 5 + ( 4 + ( 3 + ( 2 + sum(1) ) ) ) )

Genauer betrachtet: der Stack

Bei der Rekursionsfolge werden die einzelnen Methodenaufrufe im Stack (= "Stapelspeicher") aufgetürmt. Die Abarbeitung des Stacks erfolgt dabei nach dem "Last-In-First-Out"-Prinzip. Das bedeutet, dass die Methoden umgekehrt ihrer Aufruf-Reihenfolge abgearbeitet werden: Die erste aufgerufene Methode wird als letztes ausgeführt und die letzte wird als erstes aufgerufen.

Hier eine Infografik, die dir das Prinzip für das Beispiel der rekursiven Funktion sum() zeigt:

Java Mail API

Lineare vs. verzweigte Rekursion

Es gibt schließlich noch einen Unterschied zwischen der linearen und der verzweigten Rekursion:

  • Lineare Rekursion: Bei der linearen Rekursion löst ein rekursiver Aufruf höchstens einen einzigen weiteren Aufruf aus.
  • Verzweigte Rekursion: Die verzweigte Rekursion führt zu zwei oder mehr weiteren Aufrufen. Das hat zur Folge, dass die Anzahl der rekursiven Aufrufe exponentiell ansteigt.

Die lineare Rekursion haben wir mit den beiden rekursiven Methoden von oben ja bereits kennengelernt. Sehen wir uns jetzt ein Beispiel für die verzweigte Rekursion an.

Dazu wollen wir ein kleines Programm schreiben, dass den Wert einer bestimmten Position innerhalb der Fibonacci-Folge ermittelt.

Die Fibonacci-Folge ist eine Reihe von Zahlen, in der jede Zahl außer der ersten und der zweiten die Summe ihrer beiden Vorgänger ist:

0, 1, 1, 2, 3, 5, 8, 13, ...

Die allgemeine Formel dazu lautet:

fib(n) = fib(n-1) + fib (n-2)

Um die Fibonacci-Zahl an einer bestimmten Position n zu erhalten, bauen wir diese verzweigte rekursive Funktion zusammen:

public class RecursiveFibonacciSequence {

public static void main(String[] args) {
    int fibonacciNumber = getFibonacciNumberAt(6);
    System.out.println(fibonacciNumber); // 8
}

public static int getFibonacciNumberAt(int n) {
    if (n < 2) {
        return n;
    } else
        return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
}
}                

Konkret wollen wir hier mit dem Aufruf getFibonacciNumberAt(6) die sechste Fibonacci-Zahl und erhalten korrekt den Wert 8 zurückgeliefert..

Falconbyte unterstützen

Kommentar schreiben

Alle Kommentare

Es gibt bislang noch keine Kommentare zu diesem Thema.

Java Variablen erklärt

Wie werden Variablen eingesetzt? Was bedeutet Deklarieren und Initialisieren?

Arrays in Java

Arrays ermöglichen das Speichern von Daten in einer übergeordneten Datenstruktur

Initializer

Eher selten aber praktisch!

FALCONBYTE.NET

Handmade with 🖤️

© 2018-2021 Stefan E. Heller

Impressum | Datenschutz

Falconbyte GitHub facebook programmieren lernen twitter programmieren lernen discord programmieren lernen