advanced php language
Recursion and Stack Limits
Recursion is when a function calls itself to solve a smaller version of the same problem. It is useful for tree-shaped data such as menus, categories, comments, filesystems, nested arrays, and dependency graphs.
Every recursive function needs a base case. The base case stops the recursion. Without it, the function keeps calling itself until the program fails.
A Small Recursive Function
<?php
declare(strict_types=1);
function factorial(int $number): int
{
if ($number < 0) {
throw new InvalidArgumentException('Number cannot be negative.');
}
if ($number <= 1) {
return 1;
}
return $number * factorial($number - 1);
}
echo factorial(5) . PHP_EOL;
// Prints:
// 120
The base case is $number <= 1. Each call moves closer to that base case by passing $number - 1.
Recursing Through Nested Data
Recursion is often more useful for nested structures than for maths examples.
<?php
declare(strict_types=1);
/**
* @param array{name: string, children?: list<array{name: string, children?: array}>} $node
* @return list<string>
*/
function categoryNames(array $node): array
{
$names = [$node['name']];
foreach ($node['children'] ?? [] as $child) {
array_push($names, ...categoryNames($child));
}
return $names;
}
$tree = [
'name' => 'Products',
'children' => [
['name' => 'Books'],
['name' => 'Software'],
],
];
echo implode(', ', categoryNames($tree)) . PHP_EOL;
// Prints:
// Products, Books, Software
The function handles one node, then asks itself to handle each child node.
Stack Limits And Deep Data
Each recursive call uses stack space. Very deep recursion can exhaust the stack or memory.
PHP does not optimise tail recursion away for you. A recursive function that works for 20 levels may be unsafe for 20,000 levels.
When data can be very deep, consider an iterative approach with your own stack.
<?php
declare(strict_types=1);
/**
* @param array{name: string, children?: list<array{name: string, children?: array}>} $root
* @return list<string>
*/
function categoryNamesIterative(array $root): array
{
$names = [];
$stack = [$root];
while ($stack !== []) {
$node = array_pop($stack);
$names[] = $node['name'];
foreach (array_reverse($node['children'] ?? []) as $child) {
$stack[] = $child;
}
}
return $names;
}
$tree = [
'name' => 'Products',
'children' => [
['name' => 'Books'],
['name' => 'Software'],
],
];
echo implode(', ', categoryNamesIterative($tree)) . PHP_EOL;
// Prints:
// Products, Books, Software
This uses a PHP array as an explicit stack instead of relying on the call stack.
Depth Limits
For user-provided nested data, add a depth limit. This prevents accidental or malicious input from creating huge recursive chains.
<?php
declare(strict_types=1);
/**
* @param array{name: string, children?: list<array{name: string, children?: array}>} $node
*/
function countNodes(array $node, int $depth = 0, int $maxDepth = 10): int
{
if ($depth > $maxDepth) {
throw new RuntimeException('Maximum nesting depth exceeded.');
}
$count = 1;
foreach ($node['children'] ?? [] as $child) {
$count += countNodes($child, $depth + 1, $maxDepth);
}
return $count;
}
echo countNodes(['name' => 'Root', 'children' => [['name' => 'Child']]]) . PHP_EOL;
// Prints:
// 2
Depth limits are common in parsers, importers, tree walkers, and JSON-like data processing.
Cycles
Trees do not contain cycles. Graphs can. If A points to B and B points back to A, naive recursion can loop forever.
When traversing graph-like data, track visited nodes.
<?php
declare(strict_types=1);
/**
* @param array<string, list<string>> $graph
* @param array<string, bool> $visited
*/
function visit(string $node, array $graph, array &$visited): void
{
if (isset($visited[$node])) {
return;
}
$visited[$node] = true;
echo $node . PHP_EOL;
foreach ($graph[$node] ?? [] as $next) {
visit($next, $graph, $visited);
}
}
$graph = [
'A' => ['B'],
'B' => ['A', 'C'],
'C' => [],
];
$visited = [];
visit('A', $graph, $visited);
// Prints:
// A
// B
// C
The $visited array prevents revisiting the same node forever.
When To Use Recursion
Use recursion when the data shape is naturally recursive and the maximum depth is controlled. Menus, comment threads, category trees, and AST-like structures are good examples.
Prefer iteration when the data can be extremely deep, when performance is sensitive, or when a loop is easier to understand.
What You Should Be Able To Do
After this lesson, you should be able to write a recursive function with a base case, traverse nested data, add a depth limit, protect against cycles, and choose iteration when stack depth is a risk.
For junior work, this matters because recursive bugs can be severe: infinite loops, memory exhaustion, slow imports, and production crashes from unexpectedly deep data.
Practice
Practice: Traverse A Category Tree
Create a small recursive PHP example for a category tree.
Task
Build a categoryNames() function that:
- accepts a nested category array
- returns all category names
- handles categories with no children
- enforces a maximum depth
Use strict types. Keep the expected output in the PHP code block as printed lines or comments.
Check Your Work
Run cases for:
- a root category with two children
- a category with no children
- data that exceeds the maximum depth
Afterward, explain what the base case is and why a depth limit matters.
Show solution
This solution handles one category, then recursively handles each child category.
<?php
declare(strict_types=1);
/**
* @param array{name: string, children?: list<array{name: string, children?: array}>} $category
* @return list<string>
*/
function categoryNames(array $category, int $depth = 0, int $maxDepth = 5): array
{
if ($depth > $maxDepth) {
throw new RuntimeException('Maximum category depth exceeded.');
}
$names = [$category['name']];
foreach ($category['children'] ?? [] as $child) {
array_push($names, ...categoryNames($child, $depth + 1, $maxDepth));
}
return $names;
}
$tree = [
'name' => 'Products',
'children' => [
['name' => 'Books'],
['name' => 'Software'],
],
];
echo implode(', ', categoryNames($tree)) . PHP_EOL;
echo implode(', ', categoryNames(['name' => 'Standalone'])) . PHP_EOL;
try {
categoryNames([
'name' => 'A',
'children' => [[
'name' => 'B',
'children' => [['name' => 'C']],
]],
], maxDepth: 1);
} catch (RuntimeException $exception) {
echo $exception->getMessage() . PHP_EOL;
}
// Prints:
// Products, Books, Software
// Standalone
// Maximum category depth exceeded.
The base case is a category with no children: the function returns that category's name without making another recursive call. The depth limit protects the application from unexpectedly deep input.