Rekursion über int und array gibt zu wenige Werte zurück

[Jagito]

Hi,

um eine Permutation abzubilden, habe ich eine rekursive Methode geschrieben. Diese soll alle möglichen Permutationen aus z.B. drei Zahlen darstellen und zurückgeben.

  public static int[] schleife (int w, int[]data){
	 if (w>data.length-2){
		 return data;
		 
	 }
	 else{
	  	 if (data[w]!=-1){
	  		 data[w] = data[w]-1;
			 return schleife(w, data);
	  	 }
	  	 else{
	  		 data[w]=urspr_data[w];
	  		 data[w+1]=data[w+1]-1;
	  		 if(data[w+1]==0){
	  			 w=w+1;
	  		return schleife(w, data);
	  		 }
	  		return schleife(w, data);
	  	 }

	 }
  }

Weiter unten in meinem Code rufe ich dann die Methode auf, und möchte mir alle Permutationen ausgeben lassen.

int[]test = new int[3];
	test=vz.schleife(0, urspr_data);
	for (Integer zahl: test){
		System.out.println(zahl);
	}

Zu den Bezeichnungen: urspr_dataist das ursprüngliche array, das ich mir am Anfang initialisiere durch static int [] urspr_data= {23,17,11};
w ist ein Laufindex, der dafür achten soll, dass die rekursive Methode abbricht.

Meine Idee ist, dass ich mir die Zahlen wie folgt ausgeben lasse:
23 17 11
22 17 11
21 17 11
...
0 17 11
_______
23 16 11
22 16 11
...
0 16 11
_______
...
...
23 0 11
...
0 0 11
_______
23 17 10
22 17 10
usw.

Der Code bildet wahrscheinlich noch nicht alle Zahlenkombinationen ab. Dies kann ich hoffentlich noch im späteren Verlauf ändern.
Mir ist bisher unklar, warum er in der System.out.-Ausgabe lediglich -1 -1 0 schreibt und nicht alle vorhergehenden Werte.

Wo habe ich den Fehler gemacht?

 

[Tharsonius]

Dass nur eine Zeile ausgegeben wird ist in soweit logisch, da Du nur einen Aufruf der System.out.println hast. Die steht nämlich am Ende, wenn alles durch ist und gibt einmalig das Array aus.

Zur Rekursion selber, soweit ich das sehe übergibst Du immer die selbe Referenz des Arrays. Das heißt Du erstellst keine Kopie, es werden also in der Rekursion die Originaldaten verändert.

Das 1. if im Else Zweig sogt dafür, dass die Rekursion so lange aufgerufen wird, bis der erste Wert bei -1 ist, bis dahin wird data[0] stur decrementiert. Einmal bei -1 angekommen gehts immer in den nächsten else Zweig.
Hier wird zwar jedesmal data[0] auf den Wert im Originalarray gesetzt, dieser ist aber -1, weil eben keine Kopie erstellt wurde. Nun wird data[1] solange dekrementiert, bis dies 0 ist, danach wird w erst auf 1 gesetzt, was durch das erste if im else Zweig ebenfalls zu einem -1 wird. Danach wird data[2] decrementiert, bis es auf 0 ist, w auf 2 gesetzt und der nächste Aufruf beendet dann alles (durch das 1. if)

Ergo wurde in der Rekursion der Inhalt des Array auf -1 -1 0 geändert und dies wird am Ende korrekterweise ausgegeben.


Edit:
Als erstes musst Du die Ausgabe in die rekursion schieben, so dass nach jeder Manipulation ausgegeben wird, bevor der neue Aufruf erfolgt.

Als zweites musst Du vorher eine Echte Kopie der Originaldaten erstellen und diese kannst Du dann in die rekursion geben. Erst dann klappt das mit dem zurücksetzen auf die Originalwerte.

 

[Jagito]

Die Fehler in der Rekursion leuchten mir ein. Danke

Wie kann ich dann den Code verändern, so dass auch alle Zwischenschritte bei System.out.println ausgegeben werden?

Ziel von dem ganzen ist eigentlich, dass meine rekursive Methode das array data zurückgibt (mit diesem würde ich noch Berechnungen durchführen, was ich durch das System.out.println erstmal abbilde). Dann soll die rekursive Methode bis zum Abbruchkriterium wiederholt werden und jeweils das neu erstellte data-array zurückgeben.
Anscheinend jedoch gibt die Methode nur das allerletzte array zurück. Wo muss ich da die Änderung machen?

 

[Tharsonius]

Ganz nebenbei, muss es denn unbedingt eine Rekursion sein?
Einfacher geht das ganze mit 3 for Schleifen. Zumindest so lange es immer 3 Zahlen sind.

public static void schleife (int w, int[]data)  // void statt int[], da Berechnung in Rekursion erfolgt
{
  if (w > data.length-2)
  {
    return;
  }
  else
  {
    if (data[w]!=-1)
    {
      data[w] = data[w]-1;
    }
    else
    {
      data[w]=urspr_data[w];
      data[w+1]=data[w+1]-1;
      if(data[w+1]==0)
        w=w+1;
    }
    berechne(data);
    return schleife(w, data);
  }
}

Der restliche Code entsprechend:

int[]test = new int[3];
test[0]=urspr_data[0];
test[1]=urspr_data[1];
test[2]=urspr_data[2];
schleife(0, test);

Und natürlich die Berechnung:

void berechne(int[] data)
{
  for (Integer zahl: data)
  {
    System.out.println(zahl);
   }
}

 

[Jagito]

Ja, das ist die Krux an der Sache. Es sind nicht immer drei Zahlen, sondern je nach Einstellung variiert das.
Daher war für mich die Lösung eine rekursive Methode.

Deinen Code habe ich gerade ausprobiert. Danke!

Der Compiler hat mir Fehler angezeigt. Daher habe ich void berechne(int[] data)
auf static void berechne(int[] data) geändert.
Jetzt kommt noch eine Fehlermeldung zu Zeile 21 erste Code-Box:
Void methods cannot return a value

Würde ich stattdessen nur return schreiben, sind in der console wieder nur drei Zahlen zu sehen und nicht mehr.

Habe ich etwas falsch gemacht?

 

[Tharsonius]

Void methods cannot return a value

Ups, mein Fehler.

muss natürlich in zwei zeilen:
schleife(w, data);
return;

wobei das return dann natürlich überflüssig wird.