Wie ist das mit der Rekursion und dem Stack?

[Matze]

Hi!

Ich habe nochmal eine Frage zur Rekursion


Wenn ich größere Rechenschritte nicht iterativ, sondern rekursiv löse, dann kommt es manchmal zum Stacküberlauf.

Wie groß ist dwer Speicher, der dem Stack zugewiesen ist?

Mein Lehrer hat gesagt, man muss sich das wie übereinander gestapelte Teller vorstellen.
Nur kann ich das nicht so richtig


Kann mir jemand erklären, was genau ein Stack ist und wieso es da zum Überlauf kommen kann?

[Jens Schumann]

Hallo,
der Stack ist ein Speicherbereich in dem lokale Variablen und (jetzt kommt es) die Rücksprungadressen zu Prozeduren oder Funktionen, die ihrerseits ein Unterprogramm (Prozeduren oder Funktionen) aufrufen gespeichert.

Dasraus folgt: Da der Arbeitsspeicher in einem Computer leider endlich ist und wenn das Programm immer mehr Rücksprungadressen auf den Stack legen muss wird der Speicher irgendwann nicht mehr ausreichen.

Behauptung: Wenn es bei einer Rekursion zu einen Stackoverflow kommt ist die Abbruchbedingnung der Rekursion fehlerhaft.

[Matze]

Danke, aber die Behauptung muss falsch sein

Mein lehrer hat gemeint, aus dem Grund ist die Rekursion nur für "kleinere", wie soll ich sagen, "Schleifen" geeignet.

[Matze]

Aber, wenn das so wäre, dann wäre Quicksort ja echt doof!
Das ist ja auch rekursiv.

[jbg]

QuickSort kann man auch iterativ schreiben. Nur macht das kaum jemand, da es viel zu umständlich ist.

Und wenn ich mich nicht täusche, braucht Quicksort ca. n*log(n) rekursive Schritte (log = 2er-Logarithmus)

[Matze]

Aha, danke!

[Phoenix]

Zitat von Jens Schumann:

Behauptung: Wenn es bei einer Rekursion zu einen Stackoverflow kommt ist die Abbruchbedingnung der Rekursion fehlerhaft.

Ich behaupte einfach mal, die Behauptung ist falsch

Zum einen wird bei einem Funktionsaufruf nicht nur die Rücksprungadresse auf den Stack gelegt, sondern auch die lokalen variablen wie bereits erklärt - sowie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Man kann nun hergehen und den Aufruf so optimieren, daß nur das allernötigste auf dem Stack liegt. - Das geht natürlich zu Lasten der Geschwindigkeit, aber der Stack kann somit mehr Aufrufe - also einen höheren Stapel an Tellern - fassen.

An der Stelle wie man die Funktion optimiert bin ich aber (leider) noch überfragt. Ich könnte wetten, daß Hagen bzw. Assarbad hier gute Hinweise liefern können.

Zum anderen gibt es eine Funktion (wurde hier im Forum auch ein paar mal gepostet, ich weiss den Namen nur nicht mehr), die mehr oder weniger garantiert zu einem Stack overflow führt. Zumindest bei mir und bei einigen anderen

(Edit Der Name ist gefunden
Es handelt sich um die Berechnung von Fibonacci - Zahlen. Die Anzahl der Aufrufe steigt die exponentiell mit der Anzahl der zu berechnenden Summanden an - was nicht an einer falschen Abbruchbedingung sondern einfach an der hohen Anzahl der zu berechnenden Werte liegt. In irgendeinen Thread steht was von maximal 96 als Startzahl, alles was darüber hinaus geht scheint für normale 32bit - Rechner etwas zu schwierig zu sein (/edit)

[neolithos]

Zitat von Phoenix:

...wie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Kleine Bereichtigung:

Die Übergabe der Parameter hängt erstmal von den Worten stdcall, register, pascal, cdecl ab.

Was Delphi meinst nimmt ist register, und das bedeutet das die ersten 3 Parameter via Register eax, edx, ecx übergeben werden und der Rest auf dem Stack liegt. Desweiteren wird bei den anderen nur der Stack verwendet (Heap wäre sinnlos da die gefahr besteht das er zu stark fragmentiert).

[neolithos]

Zur Optimierung:

1. Vermeide große statische Parameter.

Schlechtes Bsp. BinSearch(afData : array [0..1023] of Integer; aiLo, aiHi : Integer) Hier würde mit jeder Rekursion 1032 Byte verbraucht.

Besseres Bsp.

Delphi-Quellcode:

PIntegerArray = ^TIntegerArray;
TIntegerArray = array [0..1023] of Integer;

BinSearch(apData : PIntegerArray; aiLo, aiHi : Integer)

d.h. heißt auch nur sinnvolle Sachen Übergeben, z.B. habe ich mal zu DOS-Zeiten (wo der Stack noch kleiner war) alle in der Rekursion fixen Variablen in ein Record gepackt und eine Referenz darauf übergeben.

Bsp. function BinSeach(var pParams : TBinSearchParams; apData : PIntegerArray; aiLo, aiHi : Integer) : integer; 2. Genau so ähnlich läuft es bei den statische lokale Variablen

Immer lieber Dynamische Variablen verwenden wenn es um große Sache geht.

Delphi-Quellcode:

var s : ShortString // verbrauch 256 Byte
    s : String; // verbrauch 4 Byte

3. Überlege dir das Nutzen <-> Aufwand verhältnis

Wie oft schachtelt sich die Rekursion, brauch ich dann überhaupt den Aufwand treiben.

4. Windows hat ausreichend Stack

So DOS-Zeiten hate man max. 64 kB Stack-Speicher. Heute geht die Geschichte rein Theoretisch in die Giga Byte (max. 2 GB).

Im Dialogfeld Optionen -> Linker -> Speichergrößen kann man den Stack beeinflussen.


Sei Vorsichtig mit den Lehrern: Ich habe mal einen von der Sorte rundgemacht wegen falschen Aussagen. Ergebnis: Strafplatz und für immer Mundhalten!
Und nur der kleinste Fehler wurde bestraft.
Ich hate mal ein Minus mit Plus vertauscht, schon gab es nur noch eine Zwei! Beschwehren hilft da auch nix!
Trotzdem noch auf Eins am Ende geschafft!

[choose]

Zitat von Phoenix:

Zum einen wird bei einem Funktionsaufruf nicht nur die Rücksprungadresse auf den Stack gelegt, sondern auch die lokalen variablen wie bereits erklärt - sowie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Hallo Phoenix,
die Parameterübergabe in Delphi entspricht (per Default) nicht ganz Deinen Darstellungen: Zum einen wird beim Aufruf einer Funktion/Methode unbedingt eine Rücksprungadresse abgelegt (4Bytes), sofern man nicht mit dem Inline-ASM einen Fake-Call via jmp verwendet und die "eigene" Rücksprungadresse wiederverwendet, was insbesondere bei einer endrekursion Sinn machen könnte.
Dann wird bei (Klasse-)Methoden eine nicht in der DL sichtbare Referenz auf die Klasse/das Exemplar übergeben (4Bytes), um das Schlüsselwort Self auch bei nicht-statischen Methoden mit Referenzen auf Exemplarvariablen bzw Delegationen auf nicht-statische Methoden verwenden zu können.
Sofern möglich, werden die ersten drei Parameter über die Register EAX, EDX und ECX, also ohne Verwendung des Stacks übergeben. Zu beachten ist an dieser Stelle, dass der zuvor erwähnte "unsichtbare Parameter" ebenfalls zu diesen drei zu zählen ist, also bei Methoden im besten Fall nur die ersten beiden Parameter auf diese Weise übergeben werden können.
Im Fall von komplexeren Parametern (Daten, die nicht unmittelbar in ein Register passen) als Integer, Chars, Referenzen etc. werden stattdessen Referenzen auf die Daten übergeben. In wenigen Fällen (zB ad-hoc erstellte Array-Parameter) muss hierzu zunächst eine "unsichtbare lokale Variable" erzeugt werden, um diese Referenz erzeugen zu können. Sollte ein solcher Parameter mit dem Attribute const, var oder out versehen sein, bleibt es dabei. Andernfalls kann es sein, dass der Compiler innerhalb des Codes der aufgerufenen Routine zusätzlich eine lokale Kopie des Parametes auf dem Stack anlegt, um das "call by value"-Prinzip bei Schreibzugriffen nicht zu verletzen. Dies kann insbesondere bei komplexen Records oder großen statischen Arrays die Größe des verwendeten Stacks gravierend beeinflussen.
Objekte, Dynamische Arrays und Strings bilden in diesem Konzept eine Ausnehme, ihre Daten werden generell auf dem Heap abgelegt, bei der Übergabe wird allerdings das Prinzip der "Übergabe der Referenz" verfolgt. Während "lokale" Kopien des dynamischen Arrays wiederum auf dem Heap angelegt werden, um eine spätere Größenänderung zuzulassen, wird bei den Strings das Komzept des copy on write verfolgt.
Fließkommazahlen scheinen (außer bei den Compiler-Magic Funktion) ihre Daten immer über den Stack zu erwarten (hat hier jmd genauere Infos?)

Zusätzlich zu diesen Parametern liegen die lokalen Variablen (im Falle von Strings, dynamischen Arrays und anderen Objekten zumindest Referenzen auf sie) auf dem Stack, sofern der Compiler nicht in der Lage ist, sie über Register abzubilden.

Sollte es sich bei der Routine um eine Funktion handeln, deren Ergebnis gem obiger Darstellung nicht über EAX bzw bei Floats über ST(0) übergeben werden können, reserviert die aufrufende Routine zunächst einen Speicherbereich auf dem Stack (bzw verwendet den Platz einer lokalen Variablen), un übergibt eine Referenz als Parameter auf den mit dem Ergebnis zu füllenden Bereich.


Die von mir dargestellte Aufrufkonvention entspricht mit der Delphi-Default-Variante (register) jedoch nur einer der Möglichkeiten. So werden zB die Werte bei cdecl wesentlich stacklastiger übergeben, genaueres in der OH.

Zitat von Phoenix:

Man kann nun hergehen und den Aufruf [..] optimieren[..]. Das geht natürlich zu Lasten der Geschwindigkeit[..]

Optimierungen dieser Art sind im Gegenteil häufig auch von Vorteil hinsichtlich der Geschwindigkeit geprägt.

Zitat von Phoenix:

[..]aber der Stack kann somit mehr Aufrufe - also einen höheren Stapel an Tellern - fassen.

Anschaulicher wäre wohl: "eine größere Anzahl von dünneren Tellern fassen." Schließlich bleibt die höhe des Stapels (größe des Stacks) konstant (idR ).

Zitat von Phoenix:

Ich könnte wetten, daß Hagen bzw. Assarbad hier gute Hinweise liefern können.

Das wette ich auch Vor kurzem hat Luckie auch einmal im Zusammenhang mit der Erstellung eines Guides zur Erstellung "besseren Codes" nachgefragt, wie das mit diesen "komischen Parametern" war, vielleicht hilft dieser Thread weiter...