Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben

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

Arbeitsauftrag

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

1. 2x2-Gitter.
2. 3x3-Gitter.
3. 4x4-Gitter.

Lösung für 2x2 und 3x3:

1. Für das 2x2-Gitter gibt es: vier 1x1 Kästchen und ein 2x2 Kästchen .
2. Für das 3x3-Gitter gibt es: 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 für 4x4:

Für das 4x4-Gitter gibt es:sechzehn 1x1 Kästchen und neun 2x2 Kästchen und vier 3x3 Kästchen und ein 4x4 Kästchen und.

Arbeitsauftrag

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.

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	EinSatz
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