Rekursion in PHP: Das Trampolin-Pattern gegen Stack-Overflow-Fehler

1. Warum Rekursion in PHP an ihre Grenzen stößt

Rekursion ist ein zentrales Werkzeug der funktionalen Programmierung: eine Funktion löst ein Problem, indem sie sich selbst mit einer kleineren Version desselben Problems aufruft, bis ein Basisfall erreicht ist. Baumtraversierung, das Verarbeiten verschachtelter Datenstrukturen und viele mathematische Definitionen lassen sich mit Rekursion oft klarer ausdrücken als mit einer manuell geschriebenen Schleife, weil die Struktur des Codes direkt der Struktur des Problems entspricht.

Das praktische Problem in PHP: jeder rekursive Aufruf belegt einen neuen Stack-Frame im Aufrufstack des PHP-Interpreters, und dieser Stack hat eine begrenzte Größe. Bei einer Rekursionstiefe von einigen tausend bis mehreren zehntausend Aufrufen, abhängig von Systemkonfiguration und verfügbarem Speicher, bricht PHP mit einem Fatal Error wegen Stack-Overflow ab. Eine mathematisch elegante rekursive Funktion wird damit in der Praxis unbrauchbar, sobald die Eingabegröße eine bestimmte Schwelle überschreitet.

Das Trampolin-Pattern löst genau dieses Problem, indem es tief verschachtelte Rekursion in eine flache, iterative Schleife verwandelt, ohne den rekursiven Programmierstil und dessen Klarheit vollständig aufzugeben. Dieser Artikel zeigt, warum PHP keine Tail-Call-Optimierung besitzt, wie ein Trampolin konkret implementiert wird, und wo die praktischen Grenzen dieser Technik liegen.

2. Tail-Rekursion und warum PHP sie nicht optimiert

Ein rekursiver Aufruf gilt als Tail Call, wenn er die letzte Operation innerhalb einer Funktion ist und der Rückgabewert direkt vom rekursiven Aufruf übernommen wird, ohne dass danach noch etwas mit dem Ergebnis passiert. In Sprachen mit Tail-Call-Optimierung, etwa Scheme oder Erlang, erkennt der Interpreter oder Compiler dieses Muster und ersetzt den aktuellen Stack-Frame durch den neuen, statt einen zusätzlichen Frame darüber zu legen. Dadurch bleibt der Speicherverbrauch bei Tail-Rekursion konstant, unabhängig von der Rekursionstiefe.

PHP führt diese Optimierung nicht durch, weder der Zend-Interpreter noch der JIT-Compiler in PHP 8.4 erkennen und optimieren Tail Calls. Jeder rekursive Aufruf, ob Tail Call oder nicht, belegt einen eigenen Stack-Frame, der erst nach der vollständigen Rückkehr des Aufrufs wieder freigegeben wird. Diese Sprachentscheidung ist auch für zukünftige PHP-Versionen nicht angekündigt, weshalb Rekursion in PHP grundsätzlich als beschränkt in ihrer maximalen Tiefe betrachtet werden muss, unabhängig davon, wie sauber der Tail Call formuliert ist.

<?php

declare(strict_types=1);

// This looks like a tail call, but PHP does NOT optimize it away
function sumRecursive(int $n, int $accumulator = 0): int
{
    if ($n === 0) {
        return $accumulator;
    }

    // Tail position, but still consumes a new stack frame in PHP
    return sumRecursive($n - 1, $accumulator + $n);
}

echo sumRecursive(1000); // works fine

// echo sumRecursive(1_000_000);
// Fatal error: Allowed memory size exhausted / stack overflow,
// depending on system stack size configuration

3. Den Stack-Overflow praktisch provozieren und messen

Um das Verhalten konkret nachzuvollziehen, lässt sich die maximale Rekursionstiefe experimentell ermitteln, indem eine harmlose rekursive Funktion mit wachsender Tiefe aufgerufen wird, bis PHP mit einem Fehler abbricht. Diese Grenze variiert je nach Betriebssystem, PHP-Konfiguration und verfügbarem Speicher für den Prozess, liegt aber typischerweise irgendwo zwischen wenigen tausend und einigen zehntausend Aufrufen bei Standardeinstellungen.

In der Praxis trifft man auf dieses Limit vor allem bei rekursiver Verarbeitung von Baumstrukturen mit unerwartet großer Tiefe, etwa beim Parsen verschachtelter JSON-Dokumente unbekannter Herkunft, beim Traversieren einer sehr tiefen Kategoriehierarchie in einem Shopsystem, oder bei rekursiven Algorithmen auf großen, nutzergenerierten Datensätzen. Der Fehler tritt oft erst in Produktion mit echten Daten auf, während Testdaten meist zu klein sind, um die Grenze zu erreichen.

<?php

declare(strict_types=1);

function countDepth(int $depth = 0): int
{
    try {
        return countDepth($depth + 1);
    } catch (\Error $e) {
        // In practice a stack overflow crashes the process before
        // this catch is reached — this illustrates the concept only
        return $depth;
    }
}

// A safer experiment: cap the depth explicitly and observe memory
function recurseUpTo(int $target, int $current = 0): int
{
    if ($current >= $target) {
        return $current;
    }

    return recurseUpTo($target, $current + 1);
}

echo recurseUpTo(5000);   // typically fine
// echo recurseUpTo(500000); // typically crashes on default configurations

4. Die Grundidee des Trampolin-Patterns

Die Grundidee des Trampolin-Patterns ist, eine rekursive Funktion nicht direkt sich selbst aufrufen zu lassen, sondern stattdessen eine Beschreibung des nächsten Schritts als Closure zurückzugeben. Eine äußere Schleife, das eigentliche Trampolin, ruft diese Closure wiederholt auf, solange das Ergebnis eine weitere Closure ist, statt eines fertigen Werts. Erst wenn ein konkreter Wert statt einer Closure zurückkommt, ist die Berechnung abgeschlossen.

Der entscheidende Effekt: weil die rekursive Funktion selbst niemals sich selbst direkt aufruft, sondern nur eine Closure zurückgibt, kehrt jeder Aufruf sofort zurück, und der zugehörige Stack-Frame wird sofort wieder freigegeben. Die eigentliche Wiederholung findet in der äußeren Schleife statt, deren Stack-Tiefe konstant bleibt, unabhängig davon, wie viele logische Rekursionsschritte insgesamt ausgeführt werden. Das Trampolin-Pattern simuliert also Tail-Call-Optimierung auf Anwendungsebene, weil PHP sie nicht selbst durchführt.

5. Eine eigene trampoline()-Funktion bauen

Eine minimale trampoline-Funktion nimmt eine Closure entgegen, ruft sie in einer Schleife auf, und prüft nach jedem Aufruf, ob das Ergebnis wieder eine Closure ist. Ist es eine Closure, wird sie im nächsten Schleifendurchlauf erneut aufgerufen. Ist es kein Closure mehr, sondern ein konkreter Wert, endet die Schleife und der Wert wird zurückgegeben. Diese einfache Struktur reicht aus, um beliebig tiefe logische Rekursion mit konstantem Stack-Verbrauch auszuführen.

Wichtig für die Typsicherheit ist, den Rückgabetyp der trampolinierten Funktion klar zu deklarieren: entweder eine neue Closure für den nächsten Schritt, oder der finale Ergebniswert. In PHP lässt sich das mit einem Union-Type Closure|mixed oder pragmatisch mit mixed und einem instanceof Closure-Check innerhalb der Trampolin-Schleife umsetzen.

<?php

declare(strict_types=1);

/**
 * Runs a "bouncing" computation until it stops returning a Closure.
 * Keeps stack depth constant regardless of logical recursion depth.
 */
function trampoline(Closure $fn, mixed ...$args): mixed
{
    $result = $fn(...$args);

    while ($result instanceof Closure) {
        $result = $result();
    }

    return $result;
}

/**
 * Instead of calling itself directly, returns a Closure describing
 * the next step. No new stack frame accumulates across iterations.
 */
function sumTrampolined(int $n, int $accumulator = 0): Closure|int
{
    if ($n === 0) {
        return $accumulator;
    }

    return fn (): Closure|int => sumTrampolined($n - 1, $accumulator + $n);
}

echo trampoline(sumTrampolined(...), 1_000_000); // works, constant stack depth

6. Rekursive Funktionen für das Trampolin umschreiben

Um eine bestehende rekursive Funktion für das Trampolin-Pattern nutzbar zu machen, muss sie zunächst in Tail-Rekursions-Form gebracht werden, also mit einem Akkumulator-Parameter, der das bisherige Zwischenergebnis trägt, statt das Ergebnis nach dem rekursiven Aufruf noch weiterzuverarbeiten. Eine Funktion wie return n + factorial(n - 1), die nach dem rekursiven Aufruf noch eine Multiplikation ausführt, ist keine Tail-Rekursion und muss zunächst umgeschrieben werden, bevor sie fürs Trampolin geeignet ist.

Nach dieser Umformung ersetzt man den direkten rekursiven Aufruf durch eine Closure, die den nächsten Schritt beschreibt, wie im vorherigen Abschnitt gezeigt. Dieser Umbau kostet etwas Übersichtlichkeit gegenüber der ursprünglichen, direkten Rekursion, gewinnt dafür aber Sicherheit vor Stack-Overflow bei beliebig tiefen Eingaben, ein Kompromiss, der sich bei Funktionen lohnt, deren Eingabetiefe zur Entwurfszeit nicht sicher begrenzbar ist.

<?php

declare(strict_types=1);

// Not tail-recursive: multiplication happens AFTER the recursive call returns
function factorialNaive(int $n): int
{
    if ($n <= 1) {
        return 1;
    }

    return $n * factorialNaive($n - 1); // multiplication after the call
}

// Tail-recursive form: accumulator carries the running product
function factorialTrampolined(int $n, int $accumulator = 1): Closure|int
{
    if ($n <= 1) {
        return $accumulator;
    }

    // The recursive step is now the last operation, described as a Closure
    return fn (): Closure|int => factorialTrampolined($n - 1, $accumulator * $n);
}

echo trampoline(factorialTrampolined(...), 20);     // safe, small input
echo trampoline(factorialTrampolined(...), 10_000); // safe, constant stack usage

7. Gegenseitige Rekursion mit dem Trampolin auflösen

Ein weiterer starker Anwendungsfall für das Trampolin-Pattern ist gegenseitige Rekursion, bei der zwei Funktionen sich abwechselnd aufrufen, etwa eine isEven-Funktion, die sich auf isOdd beruft, und umgekehrt. Ohne Trampolin würde jeder Wechsel zwischen den beiden Funktionen einen weiteren Stack-Frame belegen, wodurch gegenseitige Rekursion tendenziell noch schneller an die Stack-Grenze stößt als einfache Selbstrekursion.

Mit dem Trampolin geben beide Funktionen statt eines direkten Aufrufs der jeweils anderen Funktion eine Closure zurück, die auf die andere Funktion verweist. Die äußere Trampolin-Schleife kümmert sich um das tatsächliche Ausführen, unabhängig davon, welche der beiden Funktionen als Nächstes an der Reihe ist. Dieses Muster funktioniert für beliebig viele sich gegenseitig aufrufende Funktionen, nicht nur für Paare.

<?php

declare(strict_types=1);

function isEvenTrampolined(int $n): Closure|bool
{
    if ($n === 0) {
        return true;
    }

    return fn (): Closure|bool => isOddTrampolined($n - 1);
}

function isOddTrampolined(int $n): Closure|bool
{
    if ($n === 0) {
        return false;
    }

    return fn (): Closure|bool => isEvenTrampolined($n - 1);
}

var_dump(trampoline(isEvenTrampolined(...), 100_000)); // true, no stack overflow

8. Grenzen: wann eine einfache Schleife die bessere Wahl ist

Das Trampolin-Pattern löst das Stack-Overflow-Problem, führt aber auch spürbaren Overhead ein: jede Iteration erzeugt eine neue Closure, die vom Garbage Collector wieder eingesammelt werden muss, und die zusätzliche Indirektion über instanceof Closure-Prüfungen kostet gegenüber einer direkten, klassischen for- oder while-Schleife messbar Laufzeit. Für einfache, klar strukturierte Iterationen wie das Summieren eines Arrays ist eine gewöhnliche Schleife fast immer die einfachere und schnellere Lösung.

Das Trampolin-Pattern lohnt sich dort, wo der rekursive Programmierstil selbst einen echten Klarheitsvorteil bringt, etwa bei komplexen Zustandsautomaten oder Parsern mit gegenseitiger Rekursion, deren direkte Umformung in eine Schleife den Code erheblich unübersichtlicher machen würde. Bei einer einfachen linearen Iteration über bekannte, begrenzte Datenmengen ist eine klassische Schleife dagegen sowohl schneller als auch leichter verständlich als ein Trampolin.

9. Rekursionsstrategien im direkten Vergleich

Die folgende Tabelle vergleicht direkte Rekursion, das Trampolin-Pattern und die klassische Schleife.

Die Grundregel: solange die maximale Rekursionstiefe zur Entwurfszeit sicher begrenzbar ist, bleibt direkte Rekursion die klarste Lösung. Sobald die Eingabetiefe von externen, nicht kontrollierten Daten abhängt, etwa bei rekursivem Parsen, ist das Trampolin-Pattern die robustere Wahl, während einfache lineare Iterationen fast immer am besten mit einer klassischen Schleife gelöst werden.

10. Zusammenfassung

PHP führt keine Tail-Call-Optimierung durch, weshalb tief rekursive Funktionen bei großen Eingaben mit einem Stack-Overflow abbrechen können, selbst wenn der rekursive Aufruf formal in Tail-Position steht. Das Trampolin-Pattern löst dieses Problem, indem eine rekursive Funktion statt eines direkten Aufrufs eine Closure für den nächsten Schritt zurückgibt, die von einer äußeren, stack-neutralen Schleife wiederholt aufgerufen wird, bis ein konkreter Wert vorliegt.

Diese Technik funktioniert auch für gegenseitige Rekursion zwischen mehreren Funktionen und hält den Stack-Verbrauch unabhängig von der logischen Rekursionstiefe konstant. Der Preis ist zusätzlicher Overhead durch Closure-Allokation und Indirektion, weshalb sich das Trampolin-Pattern gezielt für Fälle mit unklarer oder potenziell sehr großer Eingabetiefe lohnt, nicht als generischer Ersatz für einfache, klar begrenzte Schleifen.

11. FAQ: Rekursion und Trampolin-Pattern in PHP