Stack-Overflow-Fehler verstehen und verhindern

Stack-Overflow-Fehler treten auf, wenn der Aufrufstapel eines Programms seine maximale Größe überschreitet. Dies geschieht typischerweise bei rekursiven Funktionen ohne ordnungsgemäße Basisfälle oder beim Umgang mit tief verschachtelten Funktionsaufrufen.

Häufige Ursachen

1. Unendliche Rekursion

// Problem: Fehlender Basisfall
function countDown(n) {
  console.log(n);
  countDown(n - 1);  // Stoppt nie
}

// Lösung: Basisfall hinzufügen
function countDownFixed(n) {
  console.log(n);
  if (n <= 0) return;  // Basisfall
  countDownFixed(n - 1);
}

2. Gegenseitige Rekursion

// Problem: Funktionen rufen sich gegenseitig unendlich auf
function istGerade(n) {
  if (n === 0) return true;
  return istUngerade(n - 1);
}

function istUngerade(n) {
  if (n === 0) return false;
  return istGerade(n - 1);
}

// Lösung: Ordnungsgemäße Basisfälle und Grenzprüfung hinzufügen
function istGeradeFixed(n) {
  if (n < 0) return istGeradeFixed(-n);
  if (n === 0) return true;
  if (n === 1) return false;
  return istUngeradeFixed(n - 1);
}

function istUngeradeFixed(n) {
  if (n < 0) return istUngeradeFixed(-n);
  if (n === 0) return false;
  if (n === 1) return true;
  return istGeradeFixed(n - 1);
}

3. Tiefe Objektdurchquerung

// Problem: Unbegrenzte Rekursion bei verschachtelten Objekten
function tiefKlonen(obj) {
  const klon = {};
  for (const key in obj) {
    if (typeof obj[key] === 'object') {
      klon[key] = tiefKlonen(obj[key]);  // Kann bei tiefer Verschachtelung überlaufen
    } else {
      klon[key] = obj[key];
    }
  }
  return klon;
}

// Lösung: Tiefenlimit und Zykluserkennung hinzufügen
function tiefKlonenFixed(obj, maxTiefe = 100, gesehen = new WeakMap()) {
  if (maxTiefe < 0) {
    throw new Error('Maximale Tiefe überschritten');
  }
  
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  if (gesehen.has(obj)) {
    return gesehen.get(obj);
  }
  
  const klon = Array.isArray(obj) ? [] : {};
  gesehen.set(obj, klon);
  
  for (const key in obj) {
    klon[key] = tiefKlonenFixed(obj[key], maxTiefe - 1, gesehen);
  }
  
  return klon;
}

Präventionsstrategien

1. Endrekursionsoptimierung

// Problem: Jeder rekursive Aufruf wird zum Stack hinzugefügt
function fakultaet(n) {
  if (n <= 1) return 1;
  return n * fakultaet(n - 1);
}

// Lösung: Endrekursionsoptimierung verwenden
function fakultaetTCO(n, akkumulator = 1) {
  if (n <= 1) return akkumulator;
  return fakultaetTCO(n - 1, n * akkumulator);
}

// Noch besser: Iteration verwenden
function fakultaetIterativ(n) {
  let ergebnis = 1;
  for (let i = 2; i <= n; i++) {
    ergebnis *= i;
  }
  return ergebnis;
}

2. Trampolin-Muster

function trampolin(fn) {
  return function trampoliniert(...args) {
    let ergebnis = fn(...args);
    
    while (typeof ergebnis === 'function') {
      ergebnis = ergebnis();
    }
    
    return ergebnis;
  };
}

// Verwendung
const summeTCO = trampolin(function summe(n, acc = 0) {
  if (n <= 0) return acc;
  return () => summe(n - 1, acc + n);
});

// Jetzt sicher für große Zahlen
console.log(summeTCO(1000000));

3. Iterative Alternativen

// Problem: Rekursive Baumdurchquerung
function durchlaufeBaum(knoten) {
  if (!knoten) return;
  console.log(knoten.wert);
  durchlaufeBaum(knoten.links);
  durchlaufeBaum(knoten.rechts);
}

// Lösung: Iterative Durchquerung mit Stack
function durchlaufeBaumIterativ(wurzel) {
  const stack = [wurzel];
  
  while (stack.length > 0) {
    const knoten = stack.pop();
    if (!knoten) continue;
    
    console.log(knoten.wert);
    stack.push(knoten.rechts);
    stack.push(knoten.links);
  }
}

Debug-Werkzeuge

1. Stack-Trace-Analyzer

class StackTracer {
  constructor(maxTiefe = 50) {
    this.maxTiefe = maxTiefe;
    this.aktuelleTiefe = 0;
  }
  
  trace(fn) {
    return (...args) => {
      this.aktuelleTiefe++;
      
      if (this.aktuelleTiefe > this.maxTiefe) {
        this.aktuelleTiefe--;
        throw new Error('Maximale Aufruftiefe überschritten');
      }
      
      try {
        const ergebnis = fn(...args);
        this.aktuelleTiefe--;
        return ergebnis;
      } catch (fehler) {
        this.aktuelleTiefe--;
        throw fehler;
      }
    };
  }
}

// Verwendung
const tracer = new StackTracer();
const sichereFn = tracer.trace(riskanteRekursiveFunktion);

2. Speichernutzungs-Monitor

class SpeicherMonitor {
  static pruefen() {
    const verwendet = process.memoryUsage();
    console.log({
      heapVerwendet: `${Math.round(verwendet.heapUsed / 1024 / 1024)} MB`,
      stackGroesse: new Error().stack.split('\n').length
    });
  }
}

// Verwendung in rekursiver Funktion
function rekursiveFunktion(tiefe = 0) {
  if (tiefe % 100 === 0) {
    SpeicherMonitor.pruefen();
  }
  // ... Rest der Funktion
}

3. Aufrufgraph-Generator

class AufrufgraphGenerator {
  constructor() {
    this.aufrufe = new Map();
  }
  
  umhuellen(fn, name) {
    return (...args) => {
      const aufrufer = new Error().stack.split('\n')[2].trim();
      
      if (!this.aufrufe.has(name)) {
        this.aufrufe.set(name, new Set());
      }
      this.aufrufe.get(name).add(aufrufer);
      
      return fn(...args);
    };
  }
  
  graphAusgeben() {
    for (const [fn, aufrufer] of this.aufrufe) {
      console.log(`${fn} aufgerufen von:`);
      for (const aufrufer of aufrufer) {
        console.log(`  ${aufrufer}`);
      }
    }
  }
}

Teststrategien

1. Tiefentests

describe('Rekursionstiefentests', () => {
  it('sollte maximale sichere Tiefe verarbeiten', () => {
    const maxTiefe = 1000;
    expect(() => {
      rekursiveFunktion(maxTiefe);
    }).not.toThrow();
  });
  
  it('sollte bei übermäßiger Tiefe einen Fehler werfen', () => {
    const uebermassigeTiefe = 1000000;
    expect(() => {
      rekursiveFunktion(uebermassigeTiefe);
    }).toThrow('Maximale Aufruftiefe überschritten');
  });
});

2. Speichernutzungstests

describe('Speichernutzungstests', () => {
  it('sollte stabile Speichernutzung beibehalten', () => {
    const anfangsSpeicher = process.memoryUsage().heapUsed;
    
    for (let i = 0; i < 1000; i++) {
      rekursiveFunktion(100);
    }
    
    const endSpeicher = process.memoryUsage().heapUsed;
    const zunahme = endSpeicher - anfangsSpeicher;
    
    expect(zunahme).toBeLessThan(1024 * 1024); // Weniger als 1MB Wachstum
  });
});

3. Leistungsvergleichstests

describe('Implementierungsvergleichstests', () => {
  it('sollte rekursive vs. iterative Leistung vergleichen', () => {
    const eingabe = 1000;
    
    console.time('rekursiv');
    const rekursivesErgebnis = rekursiveFunktion(eingabe);
    console.timeEnd('rekursiv');
    
    console.time('iterativ');
    const iterativesErgebnis = iterativeFunktion(eingabe);
    console.timeEnd('iterativ');
    
    expect(rekursivesErgebnis).toEqual(iterativesErgebnis);
  });
});

Best Practices

1. Iteration wenn möglich verwenden

   // Statt Rekursion für einfache Operationen
   function summe(n) {
     let gesamt = 0;
     for (let i = 1; i <= n; i++) {
       gesamt += i;
     }
     return gesamt;
   }

2. Tiefenlimits implementieren

   function rekursiveFunktion(daten, tiefe = 0, maxTiefe = 100) {
     if (tiefe >= maxTiefe) {
       throw new Error('Maximale Tiefe überschritten');
     }
     
     // Aktuelle Ebene verarbeiten
     return verarbeiteKinder(daten, tiefe + 1, maxTiefe);
   }

3. Generatoren für große Sequenzen verwenden

   function* fibonacciGenerator() {
     let vorher = 0, aktuell = 1;
     
     while (true) {
       yield aktuell;
       [vorher, aktuell] = [aktuell, vorher + aktuell];
     }
   }
   
   // Verwendung
   const fib = fibonacciGenerator();
   const erste10 = Array.from({ length: 10 }, () => fib.next().value);