Wie ist das mit der Rekursion und dem Stack?

[negaH]

Zitat:

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.

Das ist insofern richtig, für den realen Stackverbrauch ist dies aber leider NICHT relevant. Denn selbst wenn die Parameter über Register und NICHT dem Stack übergeben werden, so sind die meisten rekursiven Funktionen denoch komplexer Natur. Somit werden diese Register-Parameter nach dem Eintritt in die rekursive Funktion wiederum auf dem Stack gesichert, oder aber in den Registern ESI,EDI,EBX gesichert NACHDEM jeweils EDI,ESI,EBX auf dem Stack gesichert wurden. Somit verbraucht eine rekursive Funktion die EAX,EDX,ECX als Register-Parameter benutzt denoch 3 Integer Stack Variablen intern. Es macht also fast keinen Unterschied im Stackverbrauch.

Zitat:

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

Dies ist richtig für die durchschnittliche Anzahl an rekursiven Aufrufen dergleichen QuickSort Funktion, definiert aber NICHT die maximale Rekursionstiefe. Die maximale Verschachtelungsanzahl beträgt dann nämlich nur Ln2(n) = Log(N) wenn Log() der 2er Logarithmus ist. D.h. bei N = 1024 wird die max. Tiefe nur 10 betragen, da 2^10 = 1024. Nur diese Rekursionstiefe bestimmt den Stackverbrauch und würde bei N = 2^32 eben nur maximal 32 sein. Mit N=2^32 stösst man aber schon an die Speichergrenzen heutiger Rechner. QuickSort() ist somit in Punkto Stackverbrauch absolut unkritisch.

Auf dem Stack speichern die Programme ihre Temporären Lokalen Variablen was somit vergleichbar zum normalen Borland Speicher Manager funktioniert. Der Stack arbeitet also für diese lokalen Variablen wie ein sehr schneller Speichermanager. Den Unterschied zwischen solchen Lokalen Variablen und Borland Speichermanager Variablen bezeichnet man auch öffters als den Unterschied zwischen Dynamischen und Statischen Variablen.

Desweiteren wird ganz transparent der Programmfluß der Anwendung suf dem Stack gespeichert. D.h. bei jedem Funktionsaufruf wird der Programpointer an dem das Programm NACH der aufgerufenen Funktion fortsetzen soll auf dem Stack gespeichert. Ausgehend vom Stack könnte man also in Erfahrung bringen auf welchem WEG die derzeitige Funktion aufgerufen wurde. Zu dieser "Programmflußsteuerung" des Stack kann man auch die geschützten Codebereiche zählen. Dies sind also alle lokalen Variablen die das Programm benötigt um die try finally end. und try except end. Konstrukte umzusetzen.

Gruß Hagen