Frage von ZeroclawX, 74

Sind Rekursionen in einem Programm wirklich gefährlich und wie verhindere ich einen Stack Overflow (C++)?

Ich habe ein Programm geschrieben, welches sich durch Rekursion und der Zustimmung des Benutzers immer wieder wiederholt. Das Programm ist nicht wirklich groß, aber ich habe bemerkt dass das Programm nicht sehr schnell abkratzt obwohl der Compiler keine Fehlermeldung zurückgegeben hat. Daher hab ich den Debugger angeschmissen und wollte den fiesen Bug finden. Da war aber keiner...deshalb hab ich nach langem überlegen daran gedacht dass womöglich ein Stack Overflow aufgetreten ist und ich irgendwo einen Fehler gemacht habe. In meiner Lektüre steht auch noch dass Rekursion sehr gefährlich sein kann usw. Wie genau soll ich das Programm dann in einer Endlosschleife laufen lassen? Mit einem Whileloop?

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von NeoExacun, 55

Das ist kein Stackoverflow, dir geht schlicht der Speicher aus. So ist das mit endlos tiefer Rekursion.

Wenn du eine Endlosschleife haben willst, dann musst du das auch machen - Schleife, nicht Rekursion.

Kommentar von ZeroclawX ,

Ok. Habe ich mir schon irgendwie gedacht...naja einen Expertenratschlag sollte man nie ablehnen. Velen Dank für die schnelle Antwort!

Kommentar von NeoExacun ,

Was willst du denn mit dem Programm bezwecken?

Kommentar von ZeroclawX ,

Ich will eine "Luftballonverpackungsmaschine" simulieren. Eine zufällige Menge von 1 - 10 Luftballons wird in jeweils eines der zehn virtuellen Speicherfächer gepackt. Ein Algorithmus soll dann aus den Fächern die Fächer finden die mit ihrer Menge an Luftballons 20 ergeben, um die 20 Ballons dann zu "verpacken". Die geleerten Fächer werden wieder gefüllt usw. Das alles soll dann noch mit ASCII-art Schritt für Schritt in der Konsole gezeigt werden.

Kommentar von NeoExacun ,

Und wie intelligent soll dieser Algorithmus sein? Der naivste Ansatz besitzt eine Laufzeit von O(n!). Die tiefste Rekursion ist maximal 10, du bist nicht auf Endlosschleifen oder Endlosrekursion angewiesen.

Kommentar von ZeroclawX ,

Der Algorithmus hat damit eigentlich nichts zutun. Ich habe einfach den Fehler gemacht das Programm nicht durch eine Schleife sondern durch erneuter Rekursion zu wiederholen.

Kommentar von ZeroclawX ,

:D VIELEN DANK FÜR DEN KOMMENTAR! Ich habe endlich den Algorithmus gefunden den ich gebraucht habe um alle Additionsmöglichkeiten der Speicherfächer zu untersuchen, bis ich endlich die Summe 20 erhalte!!! Heute war so ein schlechter Tag und ich konnte mich kaum konzentrieren...vielen Dank!

Ich stehe in ihrer Schuld. XD

Alles Gute!

Kommentar von NeoExacun ,

Das entspricht übrigens recht genau dem Rucksackproblem:
https://de.wikipedia.org/wiki/Rucksackproblem

Antwort
von Ifm001, 29

Eine Schleife ist einer Rekursion vorzuziehen, da sie einen gleichbleibenden Speicherbedarf für die Verwaltung hat, während er bei der Rekursion ansteigt. Auch fordert der Ausstieg aus der Rekursion etwas mehr Gehirnschmalz.

Erst wenn die Schleife zu komplex wird und es ein klar definierbares Ende der Rekursion gibt, würde ich darauf zurückgreifen.

Keine passende Antwort gefunden?

Fragen Sie die Community