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?
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.
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.
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
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).
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
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.