Recursion
suggest changeA recursive function is a function that calls itself until it reaches a terminating condition known as the base case. Recursion is a natural solution for problems involving nested structures, trees, mathematical sequences, and directory traversals.
Anatomy of a Recursive Function
Every recursive function requires two core components:
- Base Case: The condition where the function stops calling itself and returns a direct result.
- Recursive Step: The branch where the function calls itself with a smaller or simpler subset of the original input.
Factorial Example
function factorial(int $n): int {
// 1. Base case
if ($n <= 1) {
return 1;
}
// 2. Recursive step
return $n * factorial($n - 1);
}
echo factorial(5); // 120
[!WARNING] If a recursive function lacks a valid base case or fails to converge toward it, it will cause infinite recursion and crash with a fatal memory exhaustion or stack overflow error.
Traversing Nested Trees and Hierarchies
Recursion is particularly well-suited for processing arbitrarily nested hierarchical data, such as categories, comment threads, or JSON objects:
$categories = [
[
'name' => 'Electronics',
'children' => [
[
'name' => 'Computers',
'children' => [
['name' => 'Laptops', 'children' => []],
['name' => 'Desktops', 'children' => []]
]
],
['name' => 'Audio', 'children' => []]
]
],
['name' => 'Books', 'children' => []]
];
function printCategoryTree(array $nodes, int $depth = 0): void {
foreach ($nodes as $node) {
echo str_repeat(" ", $depth) . "- " . $node['name'] . PHP_EOL;
if (!empty($node['children'])) {
printCategoryTree($node['children'], $depth + 1);
}
}
}
printCategoryTree($categories);
Output:
- Electronics
- Computers
- Laptops
- Desktops
- Audio
- Books
Traversing the Filesystem Recursively
Using recursion to search or list all files within nested folders:
function findFilesByExtension(string $dir, string $extension): array {
$results = [];
$entries = scandir($dir);
foreach ($entries as $entry) {
if ($entry === '.' || $entry === '..') {
continue;
}
$fullPath = $dir . DIRECTORY_SEPARATOR . $entry;
if (is_dir($fullPath)) {
// Recursive call on subdirectories
$results = array_merge($results, findFilesByExtension($fullPath, $extension));
} elseif (pathinfo($fullPath, PATHINFO_EXTENSION) === $extension) {
$results[] = $fullPath;
}
}
return $results;
}
Recursion Limits and Tail Call Optimization
The Zend engine in standard PHP does not support Tail Call Optimization (TCO). Every recursive call pushes a new frame onto PHP's call stack.
If recursion exceeds memory limits or the recursion nesting limit (e.g., when Xdebug is enabled via xdebug.max_nesting_level), PHP will terminate with a fatal error.
Converting Recursion to Iteration with an Explicit Stack
For deeply nested structures or high iteration counts, you can eliminate recursion by maintaining an explicit array stack:
function flattenNestedArrayIterative(array $nested): array {
$flat = [];
$stack = array_reverse($nested);
while (!empty($stack)) {
$item = array_pop($stack);
if (is_array($item)) {
// Push items onto stack in reverse order to maintain sequence
foreach (array_reverse($item) as $child) {
$stack[] = $child;
}
} else {
$flat[] = $item;
}
}
return $flat;
}
$sample = [1, [2, [3, 4], 5], 6];
print_r(flattenNestedArrayIterative($sample)); // [1, 2, 3, 4, 5, 6]