Recursion
Recursion is a function calling itself to solve a smaller instance of the same problem, until it reaches a case simple enough to answer directly. That directly-answerable case is called the base case, and it is not optional — without one, a recursive function keeps calling itself forever (or until PHP runs out of stack space and crashes). Recursion is a natural fit for problems that are already defined in terms of themselves, like factorials, tree traversal, and Fibonacci numbers, but PHP's execution model makes it worth understanding the costs before reaching for it by default.
The classic example: factorial
The factorial of n (written n!) is n * (n-1) * (n-2) * ... * 1, with the special case that 0! = 1. That special case is exactly the base case a recursive implementation needs.
Recursive factorial
<?php
function factorial(int $n): int {
if ($n <= 1) {
return 1; // base case
}
return $n * factorial($n - 1); // recursive case
}
echo factorial(5), "\n";
echo factorial(0), "\n";120 1
Tracing factorial(5): it calls factorial(4), which calls factorial(3), and so on down to factorial(1), which returns 1 without recursing further. Each frame then multiplies its own $n by the result handed back from the level below, unwinding back up to 5 * 4 * 3 * 2 * 1 = 120.
Fibonacci and the cost of naive recursion
The Fibonacci sequence defines each number as the sum of the two before it, with fib(0) = 0 and fib(1) = 1 as base cases. A direct recursive translation of that definition is short and reads beautifully, but it hides a serious performance trap.
Naive recursive Fibonacci
<?php
function fib(int $n): int {
if ($n < 2) {
return $n; // base cases: fib(0) = 0, fib(1) = 1
}
return fib($n - 1) + fib($n - 2);
}
echo fib(10);55
fib(10) looks harmless, but each call to fib($n) makes two more calls, which each make two more, and so on. The same sub-problems — fib(5), fib(4), fib(3) — get recomputed from scratch over and over across different branches of that call tree. The number of calls grows exponentially with $n: fib(30) already takes over a million function calls, and fib(40) is noticeably slow even though the final answer is just one integer.
Fixing the blowup with memoization
Memoization means caching the result of each unique input the first time it is computed, so later calls with the same input return instantly instead of recomputing the whole subtree.
Memoized Fibonacci using a static cache
<?php
function fibMemo(int $n, array &$cache = []): int {
if ($n < 2) {
return $n;
}
if (isset($cache[$n])) {
return $cache[$n];
}
$cache[$n] = fibMemo($n - 1, $cache) + fibMemo($n - 2, $cache);
return $cache[$n];
}
echo fibMemo(40);102334155
With memoization, fib(40) finishes instantly instead of taking a noticeable pause, because each distinct value of $n is computed exactly once no matter how many times it would otherwise be requested.
Stack depth limits
Every recursive call adds a new frame to PHP's call stack, and that stack has a finite size. Recursing too deeply — commonly from a missing or incorrect base case — eventually exhausts it. In ordinary production PHP without Xdebug installed, this usually surfaces as a C-level stack overflow that can crash the PHP process outright. When Xdebug is enabled for local debugging, PHP is more polite about it: Xdebug enforces its own configurable ceiling via the xdebug.max_nesting_level ini setting (historically defaulting to 256), raising a catchable fatal error before the real stack is exhausted.
What Xdebug reports when nesting goes too deep
Fatal error: Maximum function nesting level of '256' reached, aborting! Xdebug is trying to protect your script from an infinite loop. If you have a legitimate need for more nesting levels, increase 'xdebug.max_nesting_level' using ini_set() or in your ini file.
A broken base case (do not run this)
<?php
function countDown(int $n) {
echo $n, "\n";
// BUG: no base case, and $n never changes
countDown($n);
}
// countDown(5); // never stops on its ownWhy iteration is often preferable in PHP
Some languages — particularly certain functional languages — implement tail-call optimization, which lets a compiler reuse the current stack frame for a recursive call that is the very last thing a function does, effectively turning tail recursion into a loop under the hood at essentially no memory cost. PHP does not do this. Every recursive call in PHP, tail-position or not, consumes a real stack frame that stays allocated until that call returns. For deep recursion — thousands of levels — that is a genuine memory and performance concern, whereas the equivalent iterative loop uses a constant, small amount of memory regardless of how many times it runs.
The same factorial, written iteratively
<?php
function factorialIterative(int $n): int {
$result = 1;
for ($i = 2; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
echo factorialIterative(5);120
For problems like factorial or summing a list, an iterative loop does the same job with a single stack frame and no risk of hitting a nesting limit, no matter how large $n gets (aside from PHP's native integer size limits). Recursion still earns its keep for problems that are naturally tree-shaped or nested — walking a filesystem, parsing nested JSON, traversing a DOM — where an iterative equivalent would need to manage its own explicit stack anyway.
Every recursive function needs at least one base case that terminates without recursing further.
Naive recursive Fibonacci recomputes the same sub-problems repeatedly, giving it exponential time complexity.
Memoization caches results by input, turning an exponential recursive algorithm into a linear one.
Xdebug's
xdebug.max_nesting_levelsetting raises a fatal error before real stack exhaustion, but only when Xdebug is active.PHP has no tail-call optimization, so deep recursion always costs real stack memory — prefer iteration for simple accumulation and deep or unbounded depth.