größte Zahl aus einem Array mittels rekursive Fkt ermitteln

[dslpro]

Hallo,
ich versuche eine rekursive Funktion schreiben,
womit die größte Zahl aus einem Array bestimmt werden soll.

Jedoch habe ich irgendwie Verständnisprobleme ohne Schleifen es zu realisieren.

Mein bisheriges Code:

float max_zahl(int anzahl, float zahlen[]){

	int n=0;
	float tmp_max;

	if(zahlen[n]>zahlen[n-1])
	{
	       ?
	}

	max_zahl(n);
	return 0;
}

int main(){

	float zahlen[] = {1.1, 1.4, 2.5, 2.1, 9.5, 4.7};
	int anzahl=(sizeof(zahlen)/sizeof(int));

	max_zahl(anzahl, zahlen);

	system("PAUSE");
}

[kleinertipp]

Versuch es mal mit

float max_zahl(int n, float maximum_bisher, float zahlen[])

[SeppJ]

Prinzipiell lässt sich jede Schleife trivial rekursiv aufschreiben. Ganz abstrakt formuliert:

struct daten daten;
for (int i = 0; i < N; ++i)
  tu_was_mit(&daten);

->

void rekursive_schleife(int i, int N, struct daten *daten)
{
  if (i < N)
    {
      tu_was_mit(daten);
      rekursive_schleife(i+1, N, daten);
    }
}

Das heißt, wenn du deine Maximumssuche als Schleife formulieren kannst, dann kannst du sie auch rekursiv formulieren. Sofern du mit Funktionen umgehen kannst, denn deine Zeile 11 sieht da etwas unpassend aus. Insgesamt scheinst du dir selber nicht ganz klar zu sein, was deine Funktion, wann warum tun und zurück geben soll. Guck dir in deinem Lehrbuch vielleicht noch einmal an, wie das mit Funktionen und der Rekursion grundsätzlich geht.

Weiterhin vermute ich aber mal, dass hier nicht einfach eine Schleife genutzt werden soll, sondern Divide&Conquer benutzt werden soll. Denn sonst wäre die Benutzung von Rekursion ziemlich unnütz. Die Idee wäre, dass jeder Funktionsaufruf das Array in zwei Teile aufteilt. Diese Teilarrays werden dann wiederum ihrerseits nach dem Maximum durchsucht und dann die Ergebnisse dieser Teilsuchen verglichen und das Maximum genommen. Denn das Maximum der Maxima der Tailarrays ist logischerweise das Maximum des Gesamtarrays. Diesen Vorgang setzt man rekursiv fort, bis man beim Trivialfall von einem Teilarray mit einem Element angelangt ist (praktisch würde man wohl früher aufhören, aber in einer Hausaufgabe ziehen wir die Rekursion bis zum Ende durch). Das Maximum einer einzelnen Zahl ist sie selbst.
Diese Vorgehen hat mehrere Vorteile:
-Man hat nur triviale Fälle, einfach zu programmieren: Maximum einer Zahl oder Maximum von zwei Teilergebnissen.
-So etwas lässt sich recht einfach parallelisieren: Die Teilsuchen sind jeweils vollkommen unabhängig voneinander, können daher nebenläufig ausgeführt werden

Erst einmal solltest du natürlich überhaupt erst einmal eine Lösung erzeugen, zur Not eben mit der Methode im ersten Abschnitt. Kannst du denn das Maximum eines Arrays mittels einer normalen Schleife bestimmen?

[dslpro]

Ja mit einer normalen Schleife kann ich es:

float tmp_max;

float max_zahl(int anzahl, float zahlen[]){

	tmp_max=zahlen[0];

	for(int i=0; i < anzahl; i++){

		if (tmp_max < zahlen[i])

			tmp_max=zahlen[i];
	}
	return tmp_max;
}

int main(){

	float zahlen[] = {1.1, 10.4, 2.5, 2.1, 9.5, 4.7};
	int anzahl=(sizeof(zahlen)/sizeof(int));

	max_zahl(anzahl, zahlen);

	cout << tmp_max << endl;

	system("PAUSE");
}

obwohl ich mich in Rekursionen eingelesen habe,
habe ich hier Verständnisprobleme..

[seldon]

Ohne Threading ist es nicht sehr nützlich, das rekursiv zu machen, aber um zu verdeutlichen, was Rekursion ist, eignet sich das Beispiel durchaus. Und zwar ohne weiteren Parameter -- ähnlich, wie man eine Fakultät als

unsigned factorial(unsigned x) {
  if(x == 0) {
    return 1;
  }

  return x * factorial(x - 1);
}

schreiben kann. Ich vermute, dass das mit der Aufgabe gewollt ist.

Wo

{ 1                        wenn x = 0
factorial(x) = {
               { x * factorial(x - 1)     sonst

ist

{ a[0]                                  wenn n = 1
max_zahl(n, a) = { 
                 { max(a[0], max_zahl(n - 1, a + 1))     sonst

...den Rest soll TE aber selbst machen. Caveat: Was soll passieren, wenn anzahl = 0?

[SeppJ]

seldon schrieb:

Caveat: Was soll passieren, wenn anzahl = 0?

Das ist aber nicht speziell problematisch bei Rekursion, sondern allgemein bei Maximumssuchen. Hier bieten sich zwei Vorgehensweisen an:
-Wir definieren die Aufgabe um, dass nicht das Maximum, sondern das Supremum gesucht wird. Da hier mit floats gerechnet wird, können wir dann ganz frech -inf als Ergebnis nehmen. Dies ist so ein bisschen die faule Lösung, wo wir uns selber nicht viele Gedanken machen, Details der Aufgabenstellung ausnutzen und auf Wohlwollen des Lehrers hoffen. Bequem, aber nicht unbedingt empfehlenswert.
-Allgemeinere, bessere Lösung: Es ist eben einfach undefiniert. Programmiertechnisch müssen wir etwas zurück geben, das nicht Teil der Menge sein kann. Hier bietet sich, wie so oft, die Herangehensweise über Anfang und Ende, anstatt Anfang und Anzahl, an. Die Funktion nimmt dann einen Zeiger auf den Anfang und einen Zeiger hinter das Ende als Argument. Wir geben dann nicht den Wert des Maximums zurück, sondern einen Zeiger auf das Maximum. So ergibt sich der ungültige Wert ganz natürlich, indem wir den Zeiger hinter das Ende zurück geben, wenn die Menge leer ist.

Die Methode mit dem Anfang und dem Ende ist ohnehin sehr empfehlenswert, da sehr allgemein einsetzbar. In C mit seinen leider etwas beschränkten Möglichkeiten der typunabhängigen Programmierung trifft man eine sinnvolle Anwendung nicht all zu häufig (hier wäre eine), aber in Sprachen mit stärkeren Abstraktionsmitteln (z.B. C++) wird das sehr gerne eingesetzt. Sollte man mal gesehen haben.

[DirkB]

dslpro schrieb:

float max_zahl(int anzahl, float zahlen[]){

	int n=0;
	float tmp_max;

	if(zahlen[n]>zahlen[n-1])  // Bei n == 0 greifst du auf den Index -1 zu
	{
	       ?
	}

	max_zahl(n);               // Der Aufruf sollte schon so sein wie bei der Definition (10 Zeilen höher)
// Und was ist mit dem Rückgabewert?
	return 0; // Das Maximum wäre hier sinnvoller
}

int main(){

	
	float zahlen[] = {1.1, 1.4, 2.5, 2.1, 9.5, 4.7};
	int anzahl=(sizeof(zahlen)/sizeof(int));  // Schau dir die Zeile mal genau an. Wirklich sizeof(int) ?
// Darum schreibt man ja auch: =(sizeof(zahlen)/sizeof(*zahlen));
	
	max_zahl(anzahl, zahlen); // Die Funktion gibt einen Wert zurück. Was passiert mit dem?

}

seldon schrieb:

Was soll passieren, wenn anzahl = 0?

Die Funktion wird nur für Werte > 0 definiert.
Wenn du die Funktion mit falschen Parametern aufrufst, Pech gehabt. Garbage in, Garbage out.

[knivil]

Ohne Threading ist es nicht sehr nützlich, das rekursiv zu machen

Das Beispiel an sich ist wenig sinnvoll, selbst mit Threading.

Die Funktion wird nur für Werte > 0 definiert.

Sehe ich genauso. Wozu sonst gibt es Spezifikationen.

[DirkB]

knivil schrieb:

Ohne Threading ist es nicht sehr nützlich, das rekursiv zu machen

Das Beispiel an sich ist wenig sinnvoll, selbst mit Threading.

Das ist zum lernen da. Die Aufgabe ist nicht besonders schwierig, dennoch hat der TE Schwierigkeiten.
Wenn er die Aufgabe gelöst und verstanden hat, wird er auch schwierigere Sachen lösen können.

[knivil]

Ich habe nicht das Beispiel kritisiert sondern seldons Ausschweifung zu Threading. Den Bezug habe ich extra zitiert ...

[seldon]

Mit der Ausschweifung bezog ich mich auf SeppJs Bisektionsidee, die bei großen Arrays mit Threading durchaus Sinn macht. Wobei man in der Realität wohl auch nicht komplett rekursiv vorgehen würde.

[dslpro]

Ich habe nun folgende Lösung per Rekursion:

float tmp_max;

float max_zahl(int anzahl, float zahlen[]){

	if (anzahl > 0)
	{
		if (tmp_max < zahlen[anzahl-1])
		{
			tmp_max=zahlen[anzahl-1];
		}
		max_zahl(anzahl-1, zahlen);
	}
	else
		return tmp_max;
} 

int main(){ 

	float zahlen[] = {1.1, 1.4, 2.5, 2.1, 9.5, 4.7}; 
	int anzahl=(sizeof(zahlen)/sizeof(*zahlen)); 

	max_zahl(anzahl, zahlen);

	cout << tmp_max << endl;

	system("PAUSE"); 
}

Problem ist hierbei tmp_max (globale)Variable.
Wenn ich der Funktion definiere, darf es nur bei dem ersten Aufruf deklariert werden, wiederum kann ich dann die Variable in main() nicht aufrufen.

Habt ihr hierzu Verbesserungsvorschläge?
Hiermit ist die Rekursion erfüllt, oder?

Danke

[Bashar]

Du gibst tmp_max doch per return zurück, wieso benutzt du nicht den Rückgabewert? Außerdem fehlt in dem if-Zweig das return-Statement ... fällt dir natürlich nicht auf, aber undefiniertes Verhalten dürfte es trotzdem haben...

[SeppJ]

dslpro schrieb:

Habt ihr hierzu Verbesserungsvorschläge?

Reich die Daten weiter! Deine Funktion darf ja ruhig auch mehr Parameter haben. Zur Not machst du einen Wrapper um die eigentliche Rekursion:

float eigentliche_rekursion(float momentanes_maximum, float zahlen[], int anzahl)
{
  // Überlasse ich dir.
}

float max_zahl(int anzahl, float zahlen[])
{
  if (anzahl > 0)
  {
    return eigentliche_rekursion(zahlen + 1, anzahl - 1);
  }
  else
    // Was auch immer
}

An sich ist diese Technik aber gar nicht nötig, seldons Beitrag zeigt doch schon eine Möglichkeit, das alles in einer Funktion zu machen. Du denkst noch viel zu imperativ. Bei der Rekursion geht es nicht darum, einen Schritt nach dem anderen zu machen. Du musst nicht zwei Zahlen vergleichen, das Ergebnis irgendwohin packen, dann den nächsten Schritt aufrufen. Das ist Schleifendenken. Darum geht es ja gerade nicht. Das rekursive Programm legt erst einmal alles auf den Stack und dann, wenn es am Ende der Rekursion angekommen ist, wird alles rückwärts abgearbeitet. Dabei geben die Ebenen oben auf dem Stack ihre Ergebnisse an die unteren Ebenen weiter, nicht umgekehrt.

Schleifendenken, Maximum von 5 Zahlen:
-Setze erste Zahl als bisheriges Maximum
-Setze bisheriges Maximum als max(bisheriges Maximum, zweite Zahl)
-Setze bisheriges Maximum als max(bisheriges Maximum, dritte Zahl)
-Setze bisheriges Maximum als max(bisheriges Maximum, vierte Zahl)
-Setze bisheriges Maximum als max(bisheriges Maximum, fünfte Zahl)
-Maximum ist gleich bisherigem Maximum

Rekursiv gedacht, Maximum von 5 Zahlen:
-Maximum ist gleich max(erste Zahl, max(zweite Zahl, max(dritte Zahl, max(vierte Zahl, fünfte Zahl) ) ) )

Hiermit ist die Rekursion erfüllt, oder?

Technisch ja, aber globale Variablen würde ich dir als Lehrer um die Ohren hauen. Die Lösung ist derzeit noch zu schlecht. Außerdem noch die Fehler, die Bashar genannt hat. Und natürlich mein obiger, langer Absatz, dass du noch nicht verstanden hast, worum es überhaupt geht (was normal ist, Rekursion finden viele Leute schwer, wenn sie vorher imperative Programmierung gewöhnt sind).

[DirkB]

Du brauchst doch kein globales tmp_max.

Du nimmst in der Funktion max_zahl einen Wert aus dem Array
Dann rufst du max_zahl mit dem Rest von dem Array auf und speicherst auch diesen Wert loakal ab. Den Maximalwert von diesen beiden gibst du zurück.
Wenn das Array nur aus einem Element besteht, hast du schon mal einen Maximalwert gefunden.

float max_zahl(int anzahl, float zahlen[])
{ float max_rest, aktuell;

  if ( irgendetwas mit anzahl)
    aktuell = zahlen[0];
    max_rest = max_zahl(anzahl-1,zahlen+1);
....

}

[dslpro]

Ich habe mich heut nochmal hingesetzt und und nach hin und her eine Möglichkeit gefunden und die globale Variable abgeschafft
stattdessen static variable eingeführt.

Wenn ich die Funktion als void deklariere und per cout ausgeben, funktioniert es,
wenn ich jedoch mit Rückgabe Werten arbeite, funktioniert es nicht bzw.
erhalte als Ausgabe: -1.#IND

Wo mache ich ein Fehler?
Code:

float max_zahl(int anzahl, float zahlen[]){

	static float tmp_max = zahlen[anzahl];

	if (anzahl > 0)
	{
		if (tmp_max < zahlen[anzahl-1])
		{
			tmp_max=zahlen[anzahl-1];
		}
		max_zahl(anzahl-1, zahlen);
	}
	else
		return tmp_max;
} 

int main(){ 

	float zahlen[] = {1.1, 12.4, 2.5, 2.1, 9.5, 4.7}; 
	int anzahl=(sizeof(zahlen)/sizeof(*zahlen)); 

	float erg=max_zahl(anzahl, zahlen);

	cout << erg << endl;

	system("PAUSE"); 
}

[Nathan]

lokal-statische Variablen sind fast genauso schlimm wie globale!
Vermeide sie doch einfach ganz und gehe da ganz anderes dran, nämlich rekursiv:

SeppJ schrieb:

Rekursiv gedacht, Maximum von 5 Zahlen:
-Maximum ist gleich max(erste Zahl, max(zweite Zahl, max(dritte Zahl, max(vierte Zahl, fünfte Zahl) ) ) )

[Bashar]

dslpro schrieb:

Ich habe mich heut nochmal hingesetzt und und nach hin und her eine Möglichkeit gefunden und die globale Variable abgeschafft
stattdessen static variable eingeführt.

Toll, das ist bis auf die Sichtbarkeit mehr oder weniger das gleiche

Wenn ich die Funktion als void deklariere und per cout ausgeben, funktioniert es,
wenn ich jedoch mit Rückgabe Werten arbeite, funktioniert es nicht bzw.
erhalte als Ausgabe: -1.#IND

Ich hatte dir schon geschrieben, dass bei dir nicht in jedem Zweig ein return steht. Das erzeugt undefiniertes Verhalten, konkret in deinem Fall komische Werte. Aber ich schreib dir das gerne immer wieder.

[SeppJ]

Wenn dein Compiler cout akzeptiert, dann ist das übrigens ein C++-Compiler. Und das cout selber ist auch C++. Der Rest des Programms ist jedoch C (naja, so wirklich stark un-C++-ig ist es nicht, aber du möchtest ja anscheinen C machen). Mische nicht C mit C++! Das geht nur ganz am Anfang noch gut und wird dir schon sehr bald um die Ohren fliegen. Benutze für C auch einen C-Compiler. Die meisten C++-Compiler können auch C. Man muss sie in der Regel bloß ein bisschen anders aufrufen.