Finden des kleinsten Elements in einem Array (rekursiv und ohne Schleifen)

Rekursionen sind am Anfang ein bisserl schwer zu verstehen, aber im Prinzip ist es ganz einfach:

Du unterteilst in jedem Aufruf deiner Methode das Array in 2 Teile - das hast du ja schon.
Und sinnvollerweise machst du jetzt etwas mit diesen 2 Arrays. Nämlich was? Richtig! Weiter unterteilen. Und wie unterteilen wir ein Array - Ach ja - hast du ja schon geschrieben

Wenn jetzt immer weiter unterteilt wird, kommt irgendwann der Punkt an dem nicht mehr weiter unterteilt werden kann.
Sprich: Bei genau einem Element kann nicht mehr weiter unterteilt werden. Und gleichzeitig ist das minimale Element in einem Array mit nur einem Element genau dieses eine Element.

Interessant wird es aber bei einem Array mit 2 oder mehr Elementen:
- Was man mit einem Array mit N Elementen machen muss, wissen wir bereits. Unterteilen...
- Die spannende Frage ist aber was man mit den Ergebnissen der rekursiven Aufrufe macht - Denk mal drüber nach und bei Fragen meld dich wieder.

Zitat

Ich bitte um Tipps

Wenn int start, int ende in der Angabe steht, dann will dein Lehrer, dass du keinen Speicherplatz verschwendest. Folgendes muss weg:

int[] hilf1;
int[] hilf2;
new int[ ... ];
System.arraycopy( ... );

Stattdessen will er, dass du nur start und ende veränderst. Modulo brauchst du auch nicht. Und weil es rekursiv sein soll, muss die Methode sich selbst wieder aufrufen (Hypertipp: in deinem Beispiel exakt zwei mal).

du kannst dir auch den ersten teil von mergesort und die visualisierungen ansehen, das hilft wohl auch. dein problem ist sehr nahe dran, und auf die schnelle die einzige argumentation warum die ursprüngliche aufgabenstellung ueberhaupt sinn ergeben kann. sonst ist es eher ein "wir lernen rekursion anhand eines praxisuntauglichen beispiels".

Die linke Rekursion ist ok, jedoch liefert dir die rechte eine Endlosrekursion.

Kurzes Beispiel:
Du hast 5 Elemente in deinem Array und rufst jetzt deine getSmallestElement-Methode auf (getSmallestElement(array, 0, 4) )
Die linke Rekursion ruft nun getSmallestElement(array, 0, 2) auf und die rechte Rekursion ruft getSmallestElement(array, 2, 4) auf.
Ich ignorier jetzt mal die linke Rekursion und geh weiter auf die rechte ein:
Diese wird erneut getSmallestElement(array, 2, 4) aufrufen (Da sich ende/2 zu 2 auswertet).
Usw..

Du darfst hier also nicht annehmen, dass der Start immer 0 ist.

Wir scheinen wohl an der gleichen Uni zu sein

Ich hatte den Code auch erst wie am Anfang, hatte es dann mit dem letzten Code von Roflkopf etwas anders versucht, aber da bekam ich StackOverflow. Und wenn ich das gleiche if verwende kommt bei mir ArrayIndexOutOfBoundsException. Bist du sicher, dass der Code richtig ist?

StackOverflow laesst auf eine Endlosrekursion schliessen. Bist du sicher, dass du den Code richtig uebernommen hast?
Bei einer ArrayIndexOutOfBoundsException wuerde ich vermuten, dass dein initialer Aufruf nicht korrekt ist.. Uebergibst du vielleicht array.length als ende?

Also zum IndexOutOfBounds sieht der Code bei mir so aus:

public int getSmallestElement(int[] array, int start, int ende) {


       if (start == ende) {
            return array[start];
       }

       else { 
       int mid = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mid), getSmallestElement(array, mid+1, ende)); 
       }
    }

Also im Vergleich zu Roflkopf hab ich nur mittel zu mid geändert.
Und beim StackOverflow hatte ich

public int getSmallestElement(int[] array, int start, int ende) {


       if (array.length == 1) {
            return array[0];
       }

       else { 
       int mid = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mid), getSmallestElement(array, mid+1, ende)); 
       }
    }

bzw. zuerst array.length<=1, aber da kam das gleiche.

@IndexOutOfBounds: Ich meinte den Aufruf in der main-Methode, der die Rekursion beginnt

stackoverflow: Das Array-Objekt ist in jedem rekursiven Aufruf das gleiche, das heisst seine Laenge veraendert sich nie. Es kann daher auch nie die Laenge 1 erreichen.

Zitat von Bradon

@IndexOutOfBounds: Ich meinte den Aufruf in der main-Methode, der die Rekursion beginnt

Äh... Das ist die einzige Methode dazu.

Zitat

stackoverflow: Das Array-Objekt ist in jedem rekursiven Aufruf das gleiche, das heisst seine Laenge veraendert sich nie. Es kann daher auch nie die Laenge 1 erreichen.

Ja, dass das nicht stimmt wurde mir auch schon gesagt, deswegen hab ich das geändert.

Edit: Ich hab das darüber getestet, dass ich ein neues Objekt erzeuge und da die Methode ausführ. Hab da 7 Elemente eingegeben für das array, start = 0 und ende = 7, weil in der Aufgabe steht, das Intervall soll [start;ende) sein, also exklusive ende. Hab jetzt mal statt 7 6 eingegeben für ende und es ging.

Zitat von Ycul

Edit: Ich hab das darüber getestet, dass ich ein neues Objekt erzeuge und da die Methode ausführ. Hab da 7 Elemente eingegeben für das array, start = 0 und ende = 7, weil in der Aufgabe steht, das Intervall soll [start;ende) sein, also exklusive ende. Hab jetzt mal statt 7 6 eingegeben für ende und es ging.

Richtig, ein Array mit 7 Elementen hat die Indices 0-6, der Zugriff auf array[7] fuehrt zu einer ArrayIndexOutOfBoundsException. Daher muss der ende-Parameter 6 sein.

Zitat von Bradon

Richtig, ein Array mit 7 Elementen hat die Indices 0-6, der Zugriff auf array[7] fuehrt zu einer ArrayIndexOutOfBoundsException. Daher muss der ende-Parameter 6 sein.

In der Aufgabenstellung steht eben [start;ende), demnach müsste ende ja eigentlich eins höher als der letzte Index sein.