Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben

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 sehr gut 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; 
}

Suche in einem Array

Ein häufiges Problem ist die Suche nach einem speziellen Element.

Suche in einem unsortieren Array

Das einfachste Beispiel ist die Suche der Position einer Zahl in einem Array.

public class Zahlenarray{
   int[] zahlen; 
   public Zahlenarray(){
      zahlen = int[10]; 
      for(int i = 0; i<zahlen.length;i++){
         zahlen[i] = (int)(Math.random()*10);
      }
   }
}

Arbeitsauftrag

Eine kleine Beschreibung

1	Ein Satz
2	wort
3	Text	Lücke

Fügen Sie die Methode ***public int gibPosition(int z)***, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll -1 als Position zurückgegeben werden.

1	public_int_gibPosition(int_z){
2	int pos = -1;
3	for(int i=0; i < zahlen.length; i++){
4	if(zahlen[i]==z){
5	pos = i;
6	}
7	}
8	return pos;
9	}

Suche in einem unsortierten Kartenhaufen

Sucht man in einem heruntergefallenen Kartenstapel nach einer speziellen Karte, so muss man sich alle Karten ansehen, da sie in keiner speziellen Ordnung herunterfallen, sondern völlig durcheinander sind.

public class Karte{
   private String farbe; 
   private String wert; 
 
   public Karte(){
      String[] farben = {"Kreuz", "Pik", "Herz", "Karo"};
      String[] werte = {"5","6","7","8","9","10","Bube","Dame","König","Ass"};
      farbe = farben[(int)(Math.random()*farben.length())]; 
      wert= werte[(int)(Math.random()*wert.length())]; 
   }

   public boolean istGleich(String pFarbe, String pWert){
      return farbe.equals(pFarbe) && wert.equals(pWert);
   }
}

In Java können die Karten in einem Array verwaltet werden:

public class Kartenhaufen{
  private Karte[] haufen; 
  public Kartenhaufen(){
    haufen = new Karte[32];
    for (int i= 0; i<haufen.length;i++){
      haufen[i] = new Karte(); // Erzeugt eine zufällige Karte
    }
  }

  public Karte sucheKarte(String farbe, String wert){
    for (int i=0; i< haufen.length;i++){   
      Karte k = haufen[i];                          
      if(k.istGleich(farbe,wert)){        
         return k;                                    
      }                                    
    }
  }

Erläuterungen:

  public Karte sucheKarte(String farbe, String wert){
    for (int i=0; i< haufen.length;i++){   //Der ganze Array soll durchlaufen werden.
      Karte k = haufen[i];                 //Die aktuelle Karte wird aus dem Array 
                                           //geholt und eine Referenz k auf das Element wird erstellt.
      if(k.getFarbe().equals(farbe) &&     //Die Daten der aktuellen Karte k 
         k.getWert().equals(wert)){        //werden mit der Farbe und dem Wert verglichen
         return k;                         //Falls die Werte übereinstimmen, 
                                           //wird eine Referenz auf die aktuelle Karte k zurückgegeben.
      }                                    //Die Methode wird dann sofort beendet.
    }
  }

Z.B. die Telefonnummer in einem Telefonbuch. Das Telefonbuch ist nur deshalb praktikabel, weil es die Namen der Personen geordnet angibt. In einem geordneten Array kann man also schneller suchen, als in