Recursion in PHP: The Trampoline Pattern Against Stack Overflow Errors

1. Why recursion in PHP hits its limits

Recursion is a core tool of functional programming: a function solves a problem by calling itself with a smaller version of the same problem until a base case is reached. Tree traversal, processing nested data structures, and many mathematical definitions can often be expressed more clearly with recursion than with a manually written loop, because the structure of the code directly mirrors the structure of the problem.

The practical problem in PHP: every recursive call occupies a new stack frame in the PHP interpreter's call stack, and that stack has a limited size. At a recursion depth of a few thousand to several tens of thousands of calls, depending on system configuration and available memory, PHP aborts with a fatal error due to stack overflow. A mathematically elegant recursive function thus becomes unusable in practice as soon as the input size crosses a certain threshold.

The trampoline pattern solves exactly this problem by turning deeply nested recursion into a flat, iterative loop, without fully giving up the recursive programming style and its clarity. This article shows why PHP has no tail call optimization, how a trampoline is concretely implemented, and where the practical limits of this technique lie.

2. Tail recursion and why PHP does not optimize it

A recursive call counts as a tail call when it is the last operation within a function and the return value is taken directly from the recursive call, without anything further happening to the result afterward. In languages with tail call optimization, such as Scheme or Erlang, the interpreter or compiler recognizes this pattern and replaces the current stack frame with the new one, instead of stacking an additional frame on top. This keeps memory usage constant for tail recursion, regardless of recursion depth.

PHP does not perform this optimization, neither the Zend interpreter nor the JIT compiler in PHP 8.4 recognize or optimize tail calls. Every recursive call, whether a tail call or not, occupies its own stack frame, which is only released after the call fully returns. This language decision has also not been announced for future PHP versions, which is why recursion in PHP must fundamentally be considered limited in its maximum depth, regardless of how cleanly the tail call is formulated.

<?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. Provoking and measuring the stack overflow in practice

To observe this behavior concretely, the maximum recursion depth can be determined experimentally by calling a harmless recursive function with growing depth until PHP aborts with an error. This limit varies depending on operating system, PHP configuration, and memory available to the process, but typically lies somewhere between a few thousand and several tens of thousands of calls under default settings.

In practice, this limit is mostly encountered when recursively processing tree structures with unexpectedly large depth, for example parsing nested JSON documents of unknown origin, traversing a very deep category hierarchy in a shop system, or running recursive algorithms on large, user-generated datasets. The error often only surfaces in production with real data, while test data is usually too small to reach the limit.

<?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. The core idea of the trampoline pattern

The core idea of the trampoline pattern is to have a recursive function not call itself directly, but instead return a description of the next step as a closure. An outer loop, the actual trampoline, repeatedly calls this closure as long as the result is another closure, instead of a finished value. Only once a concrete value comes back instead of a closure is the computation complete.

The decisive effect: because the recursive function itself never calls itself directly, but only returns a closure, every call returns immediately, and its stack frame is released right away. The actual repetition happens in the outer loop, whose stack depth stays constant regardless of how many logical recursion steps are executed in total. The trampoline pattern thus simulates tail call optimization at the application level, because PHP does not perform it itself.

5. Building your own trampoline() function

A minimal trampoline function takes a closure, calls it in a loop, and checks after every call whether the result is a closure again. If it is a closure, it gets called again on the next loop iteration. If it is no longer a closure but a concrete value, the loop ends and the value is returned. This simple structure is enough to execute arbitrarily deep logical recursion with constant stack usage.

For type safety, it matters to clearly declare the return type of the trampolined function: either a new closure for the next step, or the final result value. In PHP this can be modeled with a union type Closure|mixed, or pragmatically with mixed and an instanceof Closure check inside the trampoline loop.

<?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. Rewriting recursive functions for the trampoline

To make an existing recursive function usable for the trampoline pattern, it must first be brought into tail recursive form, meaning it needs an accumulator parameter that carries the running intermediate result, instead of processing the result further after the recursive call returns. A function such as return n + factorial(n - 1), which still performs a multiplication after the recursive call, is not tail recursive and must first be rewritten before it is suitable for the trampoline.

After this transformation, the direct recursive call is replaced by a closure describing the next step, as shown in the previous section. This restructuring costs a bit of clarity compared to the original, direct recursion, but gains safety against stack overflow for arbitrarily deep inputs, a trade-off that pays off for functions whose input depth cannot be safely bounded at design time.

<?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. Resolving mutual recursion with the trampoline

Another strong use case for the trampoline pattern is mutual recursion, where two functions call each other alternately, for example an isEven function that relies on isOdd, and vice versa. Without a trampoline, every switch between the two functions would occupy another stack frame, causing mutual recursion to hit the stack limit even faster than simple self-recursion.

With the trampoline, both functions return a closure referring to the other function instead of calling it directly. The outer trampoline loop takes care of the actual execution, regardless of which of the two functions is up next. This pattern works for any number of mutually calling functions, not just pairs.

<?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. Limits: when a simple loop is the better choice

The trampoline pattern solves the stack overflow problem, but also introduces noticeable overhead: every iteration creates a new closure that the garbage collector must clean up again, and the additional indirection through instanceof Closure checks costs measurable runtime compared to a direct, classic for or while loop. For simple, clearly structured iterations such as summing an array, an ordinary loop is almost always the simpler and faster solution.

The trampoline pattern pays off where the recursive programming style itself brings a genuine clarity advantage, for example with complex state machines or parsers using mutual recursion, whose direct conversion into a loop would make the code considerably harder to follow. For a simple linear iteration over known, bounded amounts of data, on the other hand, a classic loop is both faster and easier to understand than a trampoline.

9. Recursion strategies in direct comparison

The following table compares direct recursion, the trampoline pattern, and the classic loop.

The rule of thumb: as long as the maximum recursion depth can be safely bounded at design time, direct recursion remains the clearest solution. Once the input depth depends on external, uncontrolled data, such as with recursive parsing, the trampoline pattern is the more robust choice, while simple linear iterations are almost always best solved with a classic loop.

10. Summary

PHP performs no tail call optimization, which is why deeply recursive functions can crash with a stack overflow on large inputs, even when the recursive call is formally in tail position. The trampoline pattern solves this problem by having a recursive function return a closure for the next step instead of a direct call, which is repeatedly invoked by an outer, stack-neutral loop until a concrete value is available.

This technique also works for mutual recursion between several functions and keeps stack usage constant regardless of logical recursion depth. The price is additional overhead from closure allocation and indirection, which is why the trampoline pattern pays off specifically for cases with unclear or potentially very large input depth, not as a generic replacement for simple, clearly bounded loops.

11. FAQ: Recursion and the Trampoline Pattern in PHP