Rekursive Methoden entwerfen

Die Quersumme von 4072 ist \(4 + 0 + 7 + 2 = 13\). Statt alle Ziffern auf einmal zu betrachten, fragst du: Wenn jemand die Quersumme von 407 schon kennt — was bleibt dann noch zu tun?

• 1 · Festlegen:genau beschreiben, was die Methode für eine Eingabe liefert: quersumme(n) = Summe der Ziffern von \(n \ge 0\).
• 2 · Zerlegen:das Problem durch ein kleineres derselben Art ausdrücken: quersumme(4072) = 2 + quersumme(407).
• 3 · Einfachster Fall:für welche Eingabe ist die Antwort sofort klar? Eine einstellige Zahl ist ihre eigene Quersumme.
• 4 · Rekursionsschritt:dem Teilergebnis vertrauen und es verknüpfen: letzte Ziffer n % 10 plus quersumme(n / 10).
• 5 · Prüfen:Terminierung begründen (n / 10 hat eine Ziffer weniger) und mit dem kleinsten Fall sowie einem größeren Beispiel testen.

static int quersumme(int n) {
    if (n < 10) {
        return n;                          // einstellig
    }
    return n % 10 + quersumme(n / 10);     // letzte Ziffer + Rest
}

Baue drei Methoden aus Bausteinen: Wähle für Abbruchbedingung, Rückgabe im einfachsten Fall und Rekursionsschritt je einen Baustein und starte mit ▶ die Tests. Manche Aufgaben haben mehr als eine richtige Lösung. Die Bausteine erreichst du auch mit Tab und den Pfeiltasten.

Halte fest: Eine rekursive Methode ist erst richtig, wenn Abbruchbedingung, Rückgabe im einfachsten Fall und Rekursionsschritt zusammenpassen — ein einziger falscher Baustein führt zu falschen Werten oder zu einer Rekursion, die nie endet.

Das Maximum einer Reihung: Die Reihung selbst wird nicht kürzer. Stattdessen beschreibt ein zusätzlicher Parameter, wie groß das Restproblem ist.

• Teilproblem:„Maximum ab Index i“ — der Hilfsparameter i gibt an, welcher Teil der Reihung noch zu betrachten ist.
• Einfachster Fall:i == a.length - 1: nur ein Element übrig, es ist selbst das Maximum.
• Rekursionsschritt:das größere von a[i] und dem Maximum ab i + 1.
• Startmethode:maximum(a) ruft maximum(a, 0) auf — wer die Methode benutzt, muss den Hilfsparameter nicht kennen (zwei Methoden gleichen Namens, Überladen).
• Voraussetzung:die Reihung ist nicht leer, sonst gibt es kein Maximum.
• Andere Zerlegungen:statt das erste Element abzutrennen, kann man die Reihung auch in der Mitte teilen — das führt zur binären Suche (3.2.3) und zu Teile und herrsche (3.3).

static int maximum(int[] a) {
    return maximum(a, 0);                  // Startaufruf
}

static int maximum(int[] a, int i) {
    if (i == a.length - 1) {
        return a[i];                       // nur noch ein Element
    }
    return Math.max(a[i], maximum(a, i + 1));
}

maximum(new int[]{14, 3, 29, 8}) liefert 29.