Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben

Rekursion bei Schachproblemen

Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der Definition implementiert werden.

Hast du die drei Bestandteile noch vor Augen?

Kästchen auf einem Gitter

Auf einem Schachbrett kann man entlang der Kanten Quadrate zeichnen. Wie viele Quadrate aller Längen passen denn auf ein Schachbrett bzw. Gitter?

Um dieses Problem zu lösen, solltest du zunächst das Problem für kleine Gitter lösen, um dann ein allgemeines Muster für große Gitter zu bestimmen.

Arbeitsauftrag

Bestimme die Anzahl der Kästchen in einem

• 2x2-Gitter,
• 3x3-Gitter,
• 4x4-Gitter.

Lösung 2x2 und 3x3

• 2x2-Gitter: vier 1x1 Kästchen und ein 2x2 Kästchen .
• 3x3-Gitter: neun 1x1 Kästchen und vier 2x2 Kästchen und ein 3x3 Kästchen.

Die Zahlen 1, 4, 9, 16, usw. werden als Quadratzahlen bezeichnet.

Lösung 4x4

Für das 4x4-Gitter gibt es sechzehn 1x1 Kästchen, neun 2x2 Kästchen, vier 3x3 Kästchen und ein 4x4 Kästchen. Insgesamt also [math]\displaystyle{ 1+4+9+16 = 30 }[/math].

Natürlich lässt sich auch eine Methode für die Anzahl der Kästchen programmieren. Die Beobachtungen aus den Beispielen für ein 2x2, 3x3 und 4x4-Gitter können bei der Formulierung einer rekursiven Formel helfen. Aber dieses Problem lässt sich auch ohne Weiteres iterativ lösen.

Arbeitsauftrag

Implementiere eine rekursive und eine iterative Lösung für das Kästchen-Problem.

Rekursive Lösung

public int k_rek(int n) {
	if(n > 1) {
		return n*n+k_rek(n-1);
	} else {
		return 1; 
	}
}

Iterative Lösung

public int k_it(n) {
	int sum = 0;
	for(int i = 1; i<n+1 ;i++) {
		sum = sum + i*i; 
	}
	return sum; 
}

Binäre Suche rekursiv

Die Möglichkeiten zur Suche in einem Array ist dir schon bekannt. Sind die Daten nicht vorsortiert, dann muss die lineare Suche angewandt werden, liegen die Daten sortiert vor, dann kann die Suche mit der binären Suche beschleunigt werden.

Die binäre Suche lässt sich rekursiv umsetzen: Der Algorithmus zerlegt das Problem in zwei (in etwa) gleich große Teilprobleme. Das eine kann sofort entschieden werden: Es enthält das gesuchte Element auf keinen Fall. Auf den anderen Teil wird derselbe Algorithmus wieder angewandt. Solange, bis das Element gefunden wurde, oder bis das aktuelle Teilproblem leer ist.

Arbeitsauftrag

Implementiere die rekursive binäre Suche in einer Methode mit der Signatur

public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis )

Die Methode soll als Ergebnis die Position des Elements im Array zurückgeben, oder -1, wenn es nicht vorhanden ist.

Überlege zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen.

Lösung

public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) {
    if( von > bis ) { // Abbruchbedingung
        return -1; // Abbruch der Rekursion
    } else {
        // (int) "schneidet" die Nachkommastellen ab
        int mitte = (int)((von+bis)/2);
        if( suchzahl < sucharray[mitte] ) {
            // Rekursionsaufruf und Reduktion auf die linke Hälfte
            return binaereSucheRekursiv(suchzahl, sucharray, von, mitte-1);
        } else if( sucharray[mitte] < suchzahl ) {
            // Rekursionsaufruf und Reduktion auf die rechte Hälfte
            return binaereSucheRekursiv(suchzahl, sucharray, mitte+1, bis);
        } else {
            // Element gefunden
            return mitte;
        }
    }
}

In der Regel werden nicht einfach nur Zahlen sortiert, sondern Objekte mit Eigenschaften, die verglichen werden. Die Sortierung kann dann nach verschiedenen Kriterien erfolgen.

Spielkarten werden zum Beispiel zuerst nach der Farbe und dann nach dem Kartenwert sortiert.

public class Karte {
    private String farbe;
    private int wert;
    
    public Karte( String pFarbe, int pWert ) {
           farbe = pFarbe;
           wert = pWert;
    }

    public String getFarbe() {
        return farbe;
    }
    
    public int getWert() {
        return wert;
    }
}

Arbeitsauftrag

Implementiere eine binäre Suche für Karten-Objekte der Klasse Karte oben.