Recursion

suggest change

A 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:

  1. Base Case: The condition where the function stops calling itself and returns a direct result.
  2. 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]

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents