Fortgeschrittenes Java Tag 4: Erweiterte Rekursion & Backtracking

Ziel dieses Tages

Heute lernst du:

• Rekursive Algorithmen für Permutationen und Kombinationen
• Grundlagen von Backtracking (Beispiele: Sudoku, Labyrinth-Lösen)
• Optimierung von Rekursion mit Memoization und Einführung in dynamische Programmierung

Am Ende wirst du komplexe rekursive Lösungen schreiben und Backtracking-Techniken effizient anwenden können.

Schritt 1: Einfache Rekursion

Eine einfache rekursive Methode, die Zahlen von 1 bis n ausgibt:

public static void printNumbers(int n) {
    if(n == 0) return;
    printNumbers(n - 1);
    System.out.println(n);
}

Schritt 2: Rekursive Algorithmen – Permutationen & Kombinationen

Rekursion wird häufig verwendet, um Permutationen oder Kombinationen einer Menge zu erzeugen.

// Beispiel: Permutationen eines Strings
public static void permute(String str, String prefix) {
    if(str.length() == 0) {
        System.out.println(prefix);
    } else {
        for(int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permute(rem, prefix + str.charAt(i));
        }
    }
}

Schritt 3: Grundlagen von Backtracking

Backtracking ist eine Technik, um alle möglichen Lösungen zu erkunden und Entscheidungen wieder zurückzunehmen, wenn sie nicht funktionieren.

Beispiele:

• Sudoku-Löser
• Labyrinth-Lösen
• N-Damen-Problem

Schritt 4: Rekursion optimieren

Memoization speichert Zwischenergebnisse, um wiederholte Berechnungen zu vermeiden.

Map<Integer, Integer> memo = new HashMap<>();

public static int fibonacci(int n) {
    if(n <= 1) return n;
    if(memo.containsKey(n)) return memo.get(n);

    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result);
    return result;
}

Übung

public static void printNumbers(int n){
    if(n == 0) return;
    printNumbers(n - 1);
    System.out.println(n);
}

Aufgabe

Schreibe ein rekursives Programm, das alle Teilmengen einer Menge erzeugt.

Schritte:

• Definiere eine rekursive Funktion mit aktuellem Index und aktueller Teilmenge
• Bei jedem Schritt: Element einschließen oder ausschließen
• Gib die Teilmenge aus, wenn das Ende erreicht ist

Beispiel:

import java.util.*;

public class Subsets {
    public static void generateSubsets(int[] arr, List<Integer> subset, int index) {
        if(index == arr.length) {
            System.out.println(subset);
            return;
        }

        // aktuelles Element einschließen
        subset.add(arr[index]);
        generateSubsets(arr, subset, index + 1);

        // aktuelles Element ausschließen
        subset.remove(subset.size() - 1);
        generateSubsets(arr, subset, index + 1);
    }

    public static void main(String[] args) {
        int[] set = {1, 2, 3};
        generateSubsets(set, new ArrayList<>(), 0);
    }
}