4. Rekursiv Maximalwert aus Integerfeld auslesen

Rekursiv Maximalwert aus Integerfeld auslesen

  • P

    ich hab' deinen (ungetesteten) code mal rauskopiert und die anzahl der 'tiefergehungen' zählen lassen:
    (links: feldgrösse, rechts: rekursionen)

    1 0
2 0
4 1
8 2
16 6
32 14
64 30
128 62
256 126
512 254

    sieht doch nach mehr aus 😉

    0
  • L

    Oder man lässt es sich vom Compiler wegoptimieren 😃

    int maximum(int* feld, size_t anz, int max = 0)
{
	return anz == 0 ? max : maximum(feld + 1, anz - 1, std::max(*feld, max));
}

    Mit VC++8 im Release-Modus mit einer "Rekursionstiefe" von 100 Mio. getestet.

    0
  • C

    @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).

    0
  • P

    CStoll schrieb:

    @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).

    wieso das? für jeden aufruf muss mindestens die rücksprungadresse auf dem stack gespichert werden.

    btw, wenn man einen algo hat, der immer halbiert und dann sich selbst wieder aufruft bekommt man bei einem startwert von 32 etwa sowas:

    32-16-8-4-2
16-8-4-2
8-4-2
4-2
2

    das sind dann 15 aufrufe (einer zuerst, 14 als rekursion)
    das deckt sich auch mit meinem 'messergebnis'
    🙂

    0
  • C

    pale dog schrieb:

    CStoll schrieb:

    @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).

    wieso das? für jeden aufruf muss mindestens die rücksprungadresse auf dem stack gespichert werden.

    Aber nur bis zur Rückkehr des Aufrufes. D.h. beim zweiten rekursiven Aufruf innerhalb der Funktion kann der Stack-Bereich wiederverwendet werden, den du beim ersten Aufruf genutzt hast.

    btw, wenn man einen algo hat, der immer halbiert und dann sich selbst wieder aufruft bekommt man bei einem startwert von 32 etwa sowas:

    32-16-8-4-2
16-8-4-2
8-4-2
4-2
2

    das sind dann 15 aufrufe (einer zuerst, 14 als rekursion)
    das deckt sich auch mit meinem 'messergebnis'
    🙂

    Ja, insegesamt hast du 15 Aufrufe, aber von denen sind maximal 5 zur selben Zeit "aktiv" und belegen kostbaren Stack-Speicher.
    (für die Laufzeit des Programms mag die Gesamtzahl der rekursiven Aufrufe möglicherweise ausschlaggebend sein, für den Speicherbedarf (des Stacks) zählt die Rekursionstiefe)

    0
  • L

    Es sind zwar 15 Aufrufe, aber die Tiefe ist trotzdem nur 5. Denn bevor die zweite Hälfte eines jeden Feldes betrachtet wird ist der rekursive Aufruf zur Betrachtung der ersten Hälfte längst zurückgekehrt.

    0
  • P

    alles klar. 👍
    entschuldigt meine blödheit 😉

    0
  • ?

    pale dog schrieb:

    alles klar. 👍
    entschuldigt meine blödheit 😉

    Ich bin gestern auch drüber gestolpert 😉

    0
  • C

    Finde aber generell, dass man eher eine iterative Struktur wählen sollte, da dann die Stacks wegfallen -> schneller.

    0
  • N

    Hey,
    Ich möchte mich bei euch bedanken, meine Frage ist definitiv beantwortet!

    Die rekursive Programmierung war nur eine Hausaufgabe, ich habe nur mit einem Freund wetten wollen, dass mein Programm schneller ist als seins. Um die Zeit messen zu können brauchte ich halt ein paar Zahlen mehr und schwups war der Stack voll wie ich jetzt so schön ausführlich berichtet bekommen habe.

    Vielen Dank

    F.Saxen

    0
Anmelden zum Antworten