Recursion in PHP

Recursion lets a PHP function call itself with a smaller version of the same problem until a base case returns without another call. It fits category trees, nested comments, directory structures, and other data that repeats its own shape.

Picture each unfinished call as a tray placed on a stack. PHP adds trays while the function moves deeper, then removes them in reverse order after the base case returns. A missing base case keeps adding trays, and deeply nested input can consume the available stack and memory.

Use recursion for naturally nested data with known depth. Use iteration with an explicit stack or queue when depth can be large or unbounded.

Guide Path

Read this after PHP OOP for beginners if your data has nested categories, replies, menus, or trees. It also pairs well with PHP and MySQL dynamic sites because most real recursion in PHP applications starts with rows that point back to the same table.

Reserve recursion for data that already contains smaller versions of itself.

Start with the Base Case

Write the stopping condition before the recursive call. This countdown returns as soon as the number reaches zero or below, so every later call has a visible destination.

<?php

function countDown(int $number): void
{
    if ($number <= 0) {
        return;
    }

    echo $number . PHP_EOL;
    countDown($number - 1);
}

countDown(3);

The call prints the countdown before the base case returns:

3
2
1

The recursive step subtracts one, which moves the input toward the base case. Replacing that subtraction with addition would move away from the stop condition and keep adding trays to the call stack.

The Three-part Pattern

A recursive function needs these three pieces:

1. A base case.
2. A smaller version of the same problem.
3. A return path that combines the answer.

The usual beginner example is the factorial function.

<?php

function factorial(int $number): int
{
    if ($number < 0) {
        throw new InvalidArgumentException("Factorial needs a non-negative number.");
    }

    if ($number === 0 || $number === 1) {
        return 1;
    }

    return $number * factorial($number - 1);
}

That example is clean because the smaller problem is obvious: factorial(5) depends on factorial(4). It is not the best reason to use recursion in application code, though. A loop is usually clearer for plain counting.

Picture a stack of unfinished work instead of a single function call. PHP cannot return factorial(5) until it knows factorial(4), and it cannot return factorial(4) until it knows factorial(3). The call stack grows until the base case returns 1, then the stack unwinds through the multiplication steps. If the smaller problem never moves toward the base case, the stack keeps growing until PHP runs out of room.

That is why the base case and the smaller input belong in the same mental check. A base case on its own does not protect anything if the recursive call moves away from it.

Where Recursion Earns Its Place

Recursion is more useful when the data is recursive too: categories with child categories, comments with replies, menus with nested sections, or file trees. Database rows often represent that shape with a parent_id pointing back to the same table.

<?php

$menu = [
    [
        "label" => "Programming",
        "children" => [
            ["label" => "PHP", "children" => []],
            ["label" => "SQL", "children" => []],
        ],
    ],
    [
        "label" => "AI Coding Tools",
        "children" => [],
    ],
];

function flattenMenu(array $items, int $depth = 0): array
{
    $rows = [];

    foreach ($items as $item) {
        $rows[] = [
            "label" => $item["label"],
            "depth" => $depth,
        ];

        if (($item["children"] ?? []) !== []) {
            $rows = [
                ...$rows,
                ...flattenMenu($item["children"], $depth + 1),
            ];
        }
    }

    return $rows;
}

$flatMenu = flattenMenu($menu);

The sample produces this label and depth sequence:

Programming: 0
PHP: 1
SQL: 1
AI Coding Tools: 0

The function follows the same shape as the data. Each menu item can have children, and each child can have children of the same shape. Recursion keeps the code close to that structure.

PHP arrays make this example convenient because an array can represent a list, a map, a stack, a queue, or a nested structure. That flexibility is useful, but it also hides mistakes. A missing children key, a string where an array should be, or a row that points to itself can turn a clean traversal into a fragile one.

Tree Building

Most database-backed PHP apps do not receive a perfect nested array from MySQL or PostgreSQL. In practice, they receive flat rows and leave you to rebuild the hierarchy.

<?php

$rows = [
    ["id" => 1, "parent_id" => null, "title" => "Programming"],
    ["id" => 2, "parent_id" => 1, "title" => "PHP"],
    ["id" => 3, "parent_id" => 1, "title" => "SQL"],
    ["id" => 4, "parent_id" => 2, "title" => "PDO"],
];

function groupByParent(array $rows): array
{
    $childrenByParent = [];

    foreach ($rows as $row) {
        $parentKey = $row["parent_id"] ?? 0;
        $childrenByParent[$parentKey][] = $row;
    }

    return $childrenByParent;
}

That grouping step keeps database work out of the recursive function. Fetch the rows once, index them by parent, then let the recursion walk the in-memory shape.

<?php

function buildTree(array $childrenByParent, ?int $parentId = null, int $depth = 0): array
{
    if ($depth > 20) {
        throw new RuntimeException("Category nesting is too deep.");
    }

    $branch = [];
    $parentKey = $parentId ?? 0;

    foreach ($childrenByParent[$parentKey] ?? [] as $row) {
        $branch[] = [
            "id" => $row["id"],
            "title" => $row["title"],
            "children" => buildTree($childrenByParent, $row["id"], $depth + 1),
        ];
    }

    return $branch;
}

$tree = buildTree(groupByParent($rows));

The sample produces one Programming root, with PHP and SQL as children and PDO nested under PHP:

Programming
├── PHP
│   └── PDO
└── SQL

This version keeps the query layer separate from the traversal layer, and the traversal has a visible depth rule. If the business says a category can only nest five levels deep, set the limit to five and let the exception report when the data has drifted.

Keep the SQL shape honest while you are there. A parent_id column should usually reference the same table, and deletes need a policy before the first production import. If deleting a parent deletes every child, write that down. If deleting a parent leaves children orphaned, the traversal code has to know what an orphan means. Recursion exposes those data-model decisions quickly because every bad relationship eventually becomes a bad path through the tree.

One old LAMP-era mistake is to query for children inside the recursive function. The first version looks tidy because each call asks the database for its immediate children. On a real tree it becomes the familiar N+1 pattern: one query for the root, then another for each branch and nested branch.

Fetch all relevant rows once and group them in PHP for small and medium trees. For very large trees, make the database work explicit with pagination, materialized paths, closure tables, or a recursive query, then let PHP render the result it received.

Render Nested Output Carefully

Once you have a tree, the recursive render function is straightforward. The important part is that output still needs escaping because recursion does not make HTML safer.

<?php

function renderTree(array $items): string
{
    if ($items === []) {
        return "";
    }

    $html = "<ul>";

    foreach ($items as $item) {
        $title = htmlspecialchars($item["title"], ENT_QUOTES | ENT_SUBSTITUTE, "UTF-8");
        $html .= "<li>" . $title . renderTree($item["children"]) . "</li>";
    }

    return $html . "</ul>";
}

The recursive call is only responsible for structure. It does not get a free pass on the boring parts that keep web apps safe: escaping output, validating input shape, and keeping database queries away from the inner loop.

Depth Limits

If the user controls the depth, treat recursion carefully. A deeply nested JSON payload, imported category tree, or comment thread can become a denial-of-service problem if the code walks it recursively with no limit.

Add a maximum depth when the input comes from outside the application.

<?php

function flattenMenuWithLimit(array $items, int $depth = 0, int $maxDepth = 20): array
{
    if ($depth > $maxDepth) {
        throw new RuntimeException("Menu nesting is too deep.");
    }

    $rows = [];

    foreach ($items as $item) {
        $rows[] = ["label" => $item["label"], "depth" => $depth];
        $children = $item["children"] ?? [];

        if ($children !== []) {
            if ($depth >= $maxDepth) {
                throw new RuntimeException("Menu nesting is too deep.");
            }

            $rows = [
                ...$rows,
                ...flattenMenuWithLimit($children, $depth + 1, $maxDepth),
            ];
        }
    }

    return $rows;
}

A leaf at maxDepth is valid because the function does not descend again. A node with children at that depth throws before visiting a level beyond the limit.

Cycles are the other quiet failure mode. A clean tree has one parent path from the root to each node. Bad imported data can produce A -> B -> C -> A, and a recursive function will keep walking that loop unless you remember what it has already visited.

<?php

function buildTreeSafely(
    array $childrenByParent,
    ?int $parentId = null,
    array $seen = [],
    int $depth = 0
): array {
    if ($depth > 20) {
        throw new RuntimeException("Tree nesting is too deep.");
    }

    $branch = [];
    $parentKey = $parentId ?? 0;

    foreach ($childrenByParent[$parentKey] ?? [] as $row) {
        if (isset($seen[$row["id"]])) {
            throw new RuntimeException("Cycle detected at node " . $row["id"]);
        }

        $branch[] = [
            "id" => $row["id"],
            "title" => $row["title"],
            "children" => buildTreeSafely(
                $childrenByParent,
                $row["id"],
                $seen + [$row["id"] => true],
                $depth + 1
            ),
        ];
    }

    return $branch;
}

That seen map looks fussy until you debug a migrated forum where two comments accidentally parent each other, and then the extra guard looks cheap.

Memoization for Repeated Subproblems

Some recursive functions repeat the same work, and the classic Fibonacci example makes recursion look worse than it has to be.

<?php

function fibonacciSlow(int $number): int
{
    if ($number < 0) {
        throw new InvalidArgumentException("Fibonacci needs a non-negative number.");
    }

    if ($number < 2) {
        return $number;
    }

    return fibonacciSlow($number - 1) + fibonacciSlow($number - 2);
}

That version recomputes the same values repeatedly. Memoization stores answers the function has already calculated.

<?php

function fibonacci(int $number, array &$cache = [0 => 0, 1 => 1]): int
{
    if ($number < 0) {
        throw new InvalidArgumentException("Fibonacci needs a non-negative number.");
    }

    if (!array_key_exists($number, $cache)) {
        $cache[$number] = fibonacci($number - 1, $cache) + fibonacci($number - 2, $cache);
    }

    return $cache[$number];
}

Memoization is useful when the same subproblem appears again and again, such as a permission tree, a dependency graph, or a calculated category count. It is not a general excuse to keep recursion when the input depth is unknown. It saves repeated work; it does not make the call stack taller.

The cache needs an owner as much as the function does. A request-local array is fine for a calculated menu or a short dependency walk. A shared cache needs invalidation rules near the data that changes the tree.

If an admin moves a category, clears a parent, or imports a new comment thread, a cached recursive result can become stale. Recursion makes that stale structure visible because one wrong parent can move an entire branch.

The cleanest recursive functions are often pure enough to test with arrays. Pass in a small tree, assert the flattened output, then pass in a cycle and assert the exception. If the function also queries the database, reads the session, prints HTML, and updates a cache, the recursion is no longer the hard part. The hard part is that the function has too many jobs.

SPL Iterators

PHP's Standard PHP Library has recursive iterators for filesystem traversal. If your job is to walk directories, reach for those before writing your own directory recursion.

<?php

$iterator = new RecursiveIteratorIterator(
    new RecursiveDirectoryIterator(__DIR__, FilesystemIterator::SKIP_DOTS)
);

foreach ($iterator as $file) {
    if ($file->isFile()) {
        echo $file->getPathname() . PHP_EOL;
    }
}

That does not mean custom recursion is wrong. It means the standard library has already handled a common recursive shape, including the iterator protocol around it. Use the library where it fits, then save custom recursion for your application data.

When a Loop Is Better

Use a loop when the problem is linear and the depth is unbounded or large.

<?php

function factorialIterative(int $number): int
{
    if ($number < 0) {
        throw new InvalidArgumentException("Factorial needs a non-negative number.");
    }

    $result = 1;

    for ($i = 2; $i <= $number; $i++) {
        $result *= $i;
    }

    return $result;
}

This version is less elegant on a whiteboard and safer for a large input. That tradeoff is usually worth taking in PHP.

For tree-shaped data, the loop equivalent usually means an explicit stack or queue. It is a little more mechanical, but the memory and depth rules are visible in your own data structure instead of hidden inside PHP's call stack.

<?php

function flattenMenuIterative(array $items): array
{
    $rows = [];
    $stack = [];

    for ($i = count($items) - 1; $i >= 0; $i--) {
        $stack[] = [$items[$i], 0];
    }

    while ($stack !== []) {
        [$item, $depth] = array_pop($stack);
        $rows[] = ["label" => $item["label"], "depth" => $depth];

        $children = $item["children"] ?? [];

        for ($i = count($children) - 1; $i >= 0; $i--) {
            $stack[] = [$children[$i], $depth + 1];
        }
    }

    return $rows;
}

The recursive version reads closer to a small, trusted menu. If the depth comes from a customer import, public API payload, or legacy table with no constraint, the explicit stack is easier to cap, log, and reason about under load.

Common Pitfalls & Debugging

The Base Case Is Missing or Unreachable

Symptom: the function keeps calling itself until the process fails. Cause: the base case is missing, or the recursive input moves away from it. Fix: put the base case before the recursive call and prove that every call moves toward it.

Deep Recursion Exhausts Memory

Symptom: a large import or nested payload consumes memory and terminates the request. Cause: every unfinished call leaves another tray on the runtime stack. Fix: enforce an application depth limit and use an explicit stack or queue when input depth can be large.

An Iterative Alternative Is Clearer

Symptom: a recursive counting function is harder to trace than the work itself. Cause: the data is linear rather than nested. Fix: use a loop for counting and an explicit stack or queue when control over memory and depth matters more than matching the data shape.

Frequently Asked Questions

What is a base case in recursion?

A base case is the input that returns a result without making another recursive call, which stops the call chain. The recursive step must also move each new input toward that case, or the function will continue consuming stack space.

Does PHP have a recursion depth limit?

PHP does not define one portable language-level depth limit for ordinary recursive calls. Available memory, the runtime stack, extensions, and environment settings can stop deep recursion. Application code should set its own depth limit when data depth is not trusted.

When is recursion better than a loop?

Recursion is often clearer when the data contains smaller versions of itself, such as category trees, nested comments, or directories with subdirectories. A loop is usually clearer for linear counting and safer when the depth can be large or unbounded.

How do you prevent cycles in a recursive tree?

Track each visited node in a seen set and reject a node that appears twice on the current path. A maximum depth provides a second guard. Database constraints and import validation should prevent invalid parent relationships before traversal begins.

Does each recursive call get its own separate set of local variables?

Yes. PHP creates a new local variable scope for every function call, recursive or not, so each unfinished call on the stack keeps its own copy of the function's parameters and local variables until that call returns.

Can RecursiveIteratorIterator walk something other than the filesystem?

Yes. It works with any class implementing the RecursiveIterator interface, such as RecursiveArrayIterator for a nested array, not only RecursiveDirectoryIterator. The filesystem is the most common use, not the only one.

Does PHP optimize recursive function calls into a loop automatically?

No. PHP has no tail-call optimization, so a recursive function still consumes one stack frame per call regardless of how the recursive call is written. Depth limits and iterative alternatives exist because PHP does not remove that cost automatically.

Does calling array_map with a callback count as recursion?

No. array_map applies a callback to each array element through iteration, not by having a function call itself. Confusing the two is common when moving from functional-style array code to genuinely recursive tree or graph traversal.

Self-Check

1. Where should the base case appear: before or after the recursive call?
2. What does countDown(3) output?
3. What label and depth sequence does flattenMenu($menu) produce for the sample menu?
4. Which pair protects a tree traversal: a seen set and maximum depth, or sorting and pagination?
5. When should an explicit stack replace recursive calls: for small trusted trees, or for large or untrusted depth?

Answers

1. Before the recursive call. A matching input returns before another tray is added to the stack.
2. 3, 2, then 1. Each call prints before subtracting one and descending.
3. Programming 0, PHP 1, SQL 1, AI Coding Tools 0. Children appear immediately after their parent.
4. Use a seen set and maximum depth. One detects repeated nodes, while the other caps the work.
5. Replace recursion when depth is large or untrusted. An explicit stack makes memory use and limits easier to control.

Next Steps

Recursion matches data that contains smaller versions of itself. Keep the tray stack bounded, make the base case visible, and switch to iteration when the depth stops being predictable.

For a place where recursion meets real application code, read beginning object-oriented programming in PHP and build your own API with PHP.