Stack & Tail Calls
Jeder Aufruf legt einen Stackframe an — Parameter, lokale Variablen, Rücksprungadresse. 1000 verschachtelte Aufrufe = 1000 Frames. Bei zu tiefer Rekursion → Stack Overflow.
Tail Call:
Wenn der rekursive Aufruf das letzte ist, was passiert (kein * n mehr danach), kann der Compiler den aktuellen Frame wiederverwenden. Aus Rekursion wird Schleife. Effizient bezeichnet als „Tail Call Optimization" (TCO).
// Nicht tail‑rekursiv:
function fact(n) {
if (n <= 1) return 1;
return n * fact(n - 1); // mult. nach Rückkehr
}
// Tail‑rekursiv:
function fact(n, acc = 1) {
if (n <= 1) return acc;
return fact(n - 1, n * acc); // letzter Schritt
}TCO‑Unterstützung:
- Scheme, Scala, Haskell, Erlang: ja, immer.
- Python, Java: nein — wegen Stack‑Traces & Debugging.
- JavaScript: vorgesehen, aber nicht in V8/Node.
- Rust: nur partiell (LLVM darf, muss nicht).
Zurück zu Informatik