Recursion, tail-call and stack depth limits in PHP
Concept
Recursion is when a function calls itself. It's elegant for problems that have a natural recursive structure — tree traversal, parsing nested structures, divide-and-conquer algorithms. But PHP has critical constraints that make recursion less practical than in functional languages.
Stack depth limit: PHP uses the native call stack. The default recursion limit before a stack overflow depends on the system stack size and the size of each stack frame (local variables, parameters). A typical PHP installation allows 100–1000 levels of recursion before crashing. The limit is not configurable in PHP itself — it's an OS/system setting (ulimit -s). Deeply recursive algorithms on large data must be converted to iteration with an explicit stack.
Tail-call optimization: PHP has no TCO (Tail Call Optimization). Even if your recursion is tail-recursive (the recursive call is the last operation), PHP still pushes a new stack frame for each call. In languages with TCO (Scheme, Haskell, Elixir), tail recursion is as efficient as a loop. In PHP, it's not — deep tail recursion will still stack overflow.
Memoization: Recursive algorithms like Fibonacci have exponential time complexity without caching. static local variables or an external array can cache results between recursive calls (memoization). PHP's static variables persist for the lifetime of the request (not the call), making them useful for simple single-request memoization.
Code Example
<?php
declare(strict_types=1);
// Fibonacci — naive recursive (exponential time, stack depth risk)
function fib_naive(int $n): int
{
if ($n <= 1) return $n;
return fib_naive($n - 1) + fib_naive($n - 2); // recomputes everything
}
// Fibonacci — memoized recursion
function fib_memo(int $n, array &$cache = []): int
{
if ($n <= 1) return $n;
if (isset($cache[$n])) return $cache[$n];
return $cache[$n] = fib_memo($n - 1, $cache) + fib_memo($n - 2, $cache);
}
echo fib_memo(40); // fast — each value computed once
// Fibonacci — iterative (no stack risk, O(n) time, O(1) space)
function fib_iter(int $n): int
{
if ($n <= 1) return $n;
[$prev, $curr] = [0, 1];
for ($i = 2; $i <= $n; $i++) {
[$prev, $curr] = [$curr, $prev + $curr];
}
return $curr;
}
// Tree traversal — recursion is natural here
function sumTree(array $node): int
{
$sum = $node['value'];
foreach ($node['children'] ?? [] as $child) {
$sum += sumTree($child); // stack depth = tree depth
}
return $sum;
}
// Iterative tree traversal — explicit stack, no recursion depth limit
function sumTreeIter(array $root): int
{
$sum = 0;
$stack = [$root];
while (!empty($stack)) {
$node = array_pop($stack);
$sum += $node['value'];
foreach ($node['children'] ?? [] as $child) {
$stack[] = $child;
}
}
return $sum;
}
// Stack depth demonstration
function depth(int $n): int
{
if ($n === 0) return 0;
return 1 + depth($n - 1);
}
// depth(1000) may crash depending on PHP configuration
// depth(100) is safe on virtually all systems