Rekursion für Array

[BaldrianForte]

Hallo allerseits,

das untenstehende Programm hat die Aufgabe, in einem Array von Zahlen, das größte Element zu finden und auszugeben. Das Problem wird auf zwei Weisen gelöst, eine iterativ, die andere rekursiv.
Die iterative habe ich aus Platzgründen aus dem Code entfernt.

Bei der rekursiven Lösung habe ich ein Problem, das ich nicht verstehe. Die Frage steht im Quelltext.

public class MaxArray {
  public static void main(String[] args) {
	int[] a = new int[5];
	a[0] = 7; a[1] = 22; a[2] = 399; a[3] = 29; a[4] = 21;
	System.out.println("Groesster Wert ist = " + rekursiv(a));
  }
  public static int rekursiv(int[] array) {	
    //Solange das Array mehr als einen Wert hat, wird die Schleife ausgeführt
    if(array.length > 1) {	
	//Es werden zwei zusätzliche Arrays geschaffen, das erste mit einer
	//Größe des halben übergebenen Arrays (modulo 2)
	int[] speicher1 = new int[array.length / 2];
	//das andere mit der Differenz zw. neugeschaffenem und übergebenem
	int[] speicher2 = new int[array.length - speicher1.length];
	//Dann wird das geteilte Array in die neuen Arrays kopiert
	for (int i = 0; i < speicher1.length; i++) 
	  speicher1[i] = array[i];
	for (int i = 0; i < array.length - speicher1.length; i++)
	  speicher2[i] = array[i + speicher1.length];
    //Was wird hier (siehe unten) größer gleich vergleichen? Welchen int-Wert 
    //repräsentiert rekursiv(speicher1) oder rekursiv(speicher2)? Das Maximum?
    //Wo kommt es her?
	if (rekursiv(speicher1) > rekursiv(speicher2))
	  return rekursiv(speicher1);
	else
	  return rekursiv(speicher2);
    }
    else 
      //hat das Array nur einen Wert, ist dieser auch automatisch der Größte 
      return array[0];
  }
}

 

[SlaterB]

> Das Maximum?
> //Wo kommt es her?

durch Rekursion,
Rekursion kann alles, außer Hochdeutsch,

die Liste hat erst 4 Elemente, 9, 12, 22, 7, davon die erste Hälfte ist 9, 12,
rekursiver Aufruf mit 9, 12, davon die erste Hälfte ist 9,
rekursiver Aufruf mit 9, nur ein Element -> 9 zurückgeben, bei der 12 wird auch die 12 zurückgegeben

nun wieder bei Liste 9, 12 Zeile
> if (rekursiv(speicher1) > rekursiv(speicher2))
das eine liefert 9, das andere 12. davon das größere wählen und zurückgeben, so funktioniert es mit 2, 4 oder auch 2 Mio. Zahlen

es ist übrigens recht aufwendig, fürs return dann nochmal die evtl. tausendfach verschachtelte Rekursion auszufühen,
besser
a = rekursiv(speicher1);
b = rekursiv(speicher2);
if (a > b) { return a; } else { return b; }

 

[BaldrianForte]

Hm, danke!

Könnte mir das noch Mal jemand für Doofe erklären?

Nachtrag.
Okay, habs kapiert! Muss mir das aber noch ein paar Stunden angucken, damit sich meine Synapsen entsprechend neu vernetzen können. In Fleisch und Blut ist es noch nicht übergegangen, aber das wird schon.

Dein Verbesserungsvorschlag probiere ich gerne (!) aus.

Wir haben die Zahlen
a[0] = 7;
a[1] = 22;
a[2] = 399;
a[3] = 29;
a[4] = 21;

Schirtt 1:
speicher1 enthalt 7, 22 speicher2 enthält 399, 29, 21

i_1)
für speicher1:
speicher1' enthält 7 speicher2' enthält 22
ist 7<?22 => 22 zurückgeben (Max für speicher1 ist nun bestimmt)

Es fehlt noch das Max aus speicher2=(399, 29, 21)
i_2)
für speicher2:
speicher1'' enthält 399 speicher2'' enthält 29, 21

ii)
für speicher2 von i_2)
speicher1''' enthält 29 speicher2''' enthält 21
ist 29 <? 21 => 29 zurückgeben

zurück zu i_2)
ist 399 <? 29 => 399 zurückgeben

zurück zum ersten Schritt
ist 22 <? 399 => 399 zurückgeben

 

[BaldrianForte]

int xa = rekursiv(speicher1);
int xb = rekursiv(speicher2);
if (xa > xb) { return xa; } else { return xb; }

Funitioniert. Hab zwar etwas gebraucht, zu verstehen, aber es funktioniert.

Klar, dadurch sparrt man sich Mehrfachwiederholungen der gleichen Rekursion.

Prima! Danke!