Fragen zu Rekursion und Stackpointer und Overflow

[Rekursion (Gast)]

Moin Leute,

ich beschäftige mich aktuell ein bisschen mit Rekursion.
Verstehe aber aktuell noch nicht ganz wie ich zu einem Stackpointer 
Overflow usw. komme.

Und zwar:
Ich habe eine rekursive Funktion. Bei jedem neuen rekursiven Aufruf wird 
der Stackpointer erhöht. Diese zeigen auf den vorherigen 
Funktionsaufruf.
Logischerweise ist dieser Stack irgendwann voll und es kommt zu einem 
Stackpointer Overflow.
Hoffe das ist richtig von mir verstanden. Weil nun meine Frage:

1. Passiert dieser Overflow schneller, wenn ich mehrere 
Übergabeparameter habe?

2. und passiert ein  Overflow auch schneller wenn ich mehrere lokale 
Variablen verwende? oder wird der Speicher einfach nur dann voll 
geschrieben?

[Vincent H. (vinci)]

Rekursion schrieb:
> 1. Passiert dieser Overflow schneller, wenn ich mehrere
> Übergabeparameter habe?
>
> 2. und passiert ein  Overflow auch schneller wenn ich mehrere lokale
> Variablen verwende? oder wird der Speicher einfach nur dann voll
> geschrieben?

1.) Kommt drauf an.
2.) Kommt drauf an.

Prinzipiell mal ein vorsichtiges ja. So ganz salopp kann man die Frage 
allerdings nicht beantworten weil das einerseits von der ABI abhängt wie 
ein procudure call aussieht, sprich welche Übergabewerte in welchen 
Registern landen und welche am Stack. Und andererseits von der 
Optimierung des Compilers. Wenn der Compiler alle lokalen Variablen in 
Registern verwalten kann, dann muss er den Stackpointer nicht unbedingt 
angreifen. Dann besteht rein theoretisch auch noch die Möglichkeit dass 
die Rekursion via tail call optimization komlett aufgelöst wird...

Aber trotz all diesen Punkte ja. Deine Grundüberlegungen stimmen.

[Tim T. (tim_taylor)]

1. Ja
2. Ja

[Rekursion (Gast)]

mh ok hatte ich mir aber auch fast gedacht, das es "drauf ankommt".

Ich habe mich auch ein bisschen mit Assembler beschäftigt (für den 8086) 
und Befehle gesehen wie PUSH und POP die etwas auf den Stack legen, 
sowie CALL und RET die zum aufrufen und rückkehren von Unterprogrammen 
ist, die aber halt auch auf dem Stack liegen.

Aber an sich reicht mir die Aussage, das es Compiler abhängig ist und 
der "Art" wie man die Rekursion geschrieben hat.

[x^y (Gast)]

Vincent H. schrieb:
> Wenn der Compiler alle lokalen Variablen in
> Registern verwalten kann, dann muss er den Stackpointer nicht unbedingt
> angreifen.

Kleine Ergänzung:

Prinzipiell müssen ja auch Register bei einem Funktionsaufruf gesichert 
werden. Lokale Variablen, die bereits auf dem Stack leben, müssten nicht 
extra gesichert werden. Es macht also eigentlich keinen Unterschied 
(Unterschied ggf. nur in der letzten Rekursionsebene), ob der Compiler 
sich für ein Register entscheidet und dieses für die Rekursion sichert 
oder für eine lokale Variable, die bereits auf dem Stack lebt.

Ein Unterschied würde erst entstehen, wenn die effektive Nutzungsdauer 
der Variable nicht die Rekursion (und andere Funktionsaufrufe) 
überschneidet. Dann kann der Compiler tatsächlich ein Register nutzen 
ohne dass irgendwie Stack benötigt wird.

In diesem Zusammenhang ist auch Tail Chaining als weiterführendes Topic 
interessant zu erwähnen:
https://en.wikipedia.org/wiki/Tail_call
https://de.wikipedia.org/wiki/Endrekursion

[Yalu X. (yalu) (Moderator)]

Noch eine kleine Ergänzung:

Rekursion schrieb:
> 2. und passiert ein  Overflow auch schneller wenn ich mehrere lokale
> Variablen verwende? oder wird der Speicher einfach nur dann voll
> geschrieben?

Da muss man unterscheiden: Statische lokale Variablen werden nicht auf
dem Stack abgelegt und existieren im Speicher auch bei rekursiven
Aufrufen nur einmal. Automatische Variablen hingegen liegen in Registern
oder auf dem Stack. Für sie gilt dasselbe wie für die Funktionsargumente
(s. Beitrag von x^y).

[georg (Gast)]

Kommt auch auf den Programmierstil an:

Prozedur-lokale Variablen werden i.A.* auf dem Stack verwaltet, 
Variablen die man selbst mit new oder einem Constructor alloziert 
dagegen auf dem Heap. Aber ob bei einer Rekursion nun der Stack 
überläuft oder der Heap macht keinen so grossen Unterschied, beides 
führt zu schwer zu analysierenden Fehlern.

* und natürlich ist alles compilerspezifisch.

Georg

[zitter_ned_aso (Gast)]

Hier hatte ich auch eine Rekursion.

Beitrag "Dekrementieren vs. Subtrahieren (n-- vs n-1)"

Da kannst du auch sehen, wie aus einer Rekursion  eine Endrekursion 
(tail recursion) werden kann.