Stacküberlauf im Praktikum: rekursiv gezählt, iterativ gerettet
Im Informatik-Grundkurs der Jahrgangsstufe 12 wird ein Langzeitexperiment aus dem Physikunterricht ausgewertet: Ein Sensor hat über vier Wochen 1.000.000 Messwerte in ein int-Array geschrieben. Ayla implementiert in Java die rekursive Methode int anzahlUeber(int[] werte, int index), die ab Index 0 zählt, wie viele Werte über einem Grenzwert liegen. Mit 8.000 Werten läuft sie fehlerfrei, mit dem vollständigen Array bricht das Programm nach knapp zwei Sekunden mit einem StackOverflowError ab. Ayla schlägt vor, die JVM mit -Xss64m zu starten – „dann passt das schon“. Timo hat dieselbe Funktion iterativ geschrieben; sie liefert in allen Testfällen dasselbe Ergebnis und braucht für 1.000.000 Werte 4 ms. Die Abgabe ist für Freitag angekündigt, und die Fachlehrerin verlangt eine begründete Entscheidung statt eines Schnellschusses. Gleichzeitig soll der Kurs klären, wann Rekursion trotzdem das Mittel der Wahl bleibt, damit das Projekt nicht in ein pauschales „Rekursion ist schlecht“ kippt.
1. Erklären Sie den StackOverflowError mit einer überschlägigen Rechnung und beurteilen Sie Aylas Vorschlag `-Xss64m` (drei Argumente).
Read the worked answer
Rechnung: Jeder rekursive Aufruf belegt einen Stack-Frame mit Parametern, Rücksprungadresse und lokalen Variablen. Ein solcher Frame kostet grob 60–100 Byte. Der Main-Thread hat je nach Plattform etwa 512 kB bis 1 MB Stack. Bei 1 MB und 80 Byte pro Frame sind das rund 13.000 Aufrufe – dazu passt, dass 8.000 Werte noch laufen, 1.000.000 aber nicht. Für 1.000.000 Aufrufe wären etwa 80 MB Stack nötig; die Rekursionstiefe wächst hier linear mit der Eingabegröße, nicht logarithmisch.
Bewertung von -Xss64m:
- Selbst bei wohlwollender Schätzung reichen 64 MB nicht (ca. 80 MB Bedarf). Der Fehler würde also nur später oder gar nicht verschwinden – ein Experiment mit ungewissem Ausgang.
- Der Wert gilt pro Thread. Bei mehreren Threads vervielfacht sich der Speicher, im Extremfall endet das Programm mit
OutOfMemoryError: unable to create native thread. Auf Schulserver oder in Containern sind solche Limits oft zusätzlich gedeckelt. - Die JVM führt keine Tail-Call-Optimierung durch; auch eine „endrekursive“ Schreibweise belegt pro Element einen Frame. Das Problem ist also strukturell, nicht durch Konfiguration lösbar.
Fazit: -Xss64m ist ein Symptom-Pflaster. Wenn die Rekursionstiefe von der Datenmenge abhängt, ist die iterative Lösung die belastbare Wahl – hier zusätzlich schneller und speicherneutral.
2. Geben Sie eine iterative Fassung der Methode an und vergleichen Sie beide Fassungen hinsichtlich Laufzeit, Speicher und Fehleranfälligkeit.
Read the worked answer
int anzahlUeber(int[] werte, int grenze) {
int anzahl = 0;
for (int i = 0; i < werte.length; i++) {
if (werte[i] > grenze) anzahl++;
}
return anzahl;
}
Laufzeit: Beide Varianten sind O(n): jedes Element wird genau einmal betrachtet. Die iterative Fassung hat einen kleineren konstanten Faktor, weil pro Element kein Frame aufgebaut und abgebaut wird – das erklärt den Unterschied zwischen 4 ms und dem rekursiven Lauf.
Speicher: Die rekursive Fassung braucht O(n) Stack (rund 80 Byte pro Element, also ca. 80 MB bei 1.000.000 Werten), die iterative O(1) zusätzlich. Stack ist ein besonders knappes Betriebsmittel: Er ist pro Thread fest reserviert und lässt sich nicht nachträglich vergrößern, während Heap-Speicher dynamisch verwaltet wird.
Fehleranfälligkeit: Die rekursive Variante hat eine harte, unsichtbare Grenze (Abbruch bei ca. 13.000 Elementen), die von der Eingabegröße abhängt – der Fehler tritt erst mit echten Daten auf, nicht in kleinen Tests. Außerdem muss index korrekt mitgeführt werden (Off-by-one). Die iterative Fassung hat nur eine Abbruchbedingung, die direkt aus der Array-Länge folgt.
Nebenbefund: In der ursprünglichen Signatur fehlt der Grenzwert als Parameter; er muss global oder als Feld vorliegen, was die Methode schlechter testbar macht. Beide Fassungen sollten ihn explizit übergeben bekommen.
3. Nennen Sie eine Stelle im selben Projekt, an der Rekursion die bessere Wahl bleibt, und leiten Sie daraus ein allgemeines Entscheidungskriterium ab.
Read the worked answer
Beispiel: Die Auswertung soll aus den Messwerten einen balancierten Suchbaum oder einen Entscheidungsbaum aufbauen, dessen Tiefe bei ca. 20 Ebenen liegt (log₂ von einer Million). Ein durchlaufe(Knoten k) für In-Order-Ausgabe ist dort klar besser: Der Code entspricht der Struktur (jeder Knoten behandelt seine beiden Kinder gleich), er ist kurz, gut lesbar und leicht zu testen. Eine iterative Fassung bräuchte einen expliziten Stack und damit mehr Code und mehr Fehlerquellen – der Speicherbedarf wäre derselbe, nur selbst verwaltet.
Entscheidungskriterium: Maßgeblich ist, wie die Rekursionstiefe mit der Eingabe wächst, nicht die Rekursion an sich.
- Tiefe ∝ n (lineare Liste, Array-Durchlauf, „zähle von 0 bis Ende“): iterativ lösen, sonst droht Stacküberlauf bei großen Daten.
- Tiefe ∝ log n oder durch die Datenstruktur begrenzt (Baumtiefe, Divide-and-Conquer wie Mergesort): Rekursion ist angemessen, weil die Tiefe auch bei großen Eingaben klein bleibt.
- Zusätzlich prüfen: Ist die rekursive Lösung endrekursiv und würde in einer Sprache mit Tail-Call-Optimierung laufen? In Java hilft das nicht, in Scheme schon – die Sprache gehört zur Begründung.
Für die Abgabe heißt das: Aylas Zählfunktion wird iterativ umgesetzt, Timos Variante ersetzt sie; die Baumdurchläufe im Auswertungsteil bleiben rekursiv, mit einem Kommentar zur begrenzten Tiefe.