Recursion

A recursive function calls itself to solve a smaller version of the same problem, until the problem becomes simple enough to answer directly. Recursion is the natural tool for nested structures — menus, category trees, folders, comment threads, nested JSON — which appear constantly in web applications.

Base case and recursive case

Every recursive function needs a base case that stops the recursion and a recursive case that moves towards it. Factorial is the classic example: 5! = 5 × 4!, and 1! = 1.

PHP 
<?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(20), "\n";
Output
120
2432902008176640000

Watching the calls

PHP 
<?php

function sumTo(int $n, int $depth = 0): int
{
    $indent = str_repeat("  ", $depth);
    echo "{$indent}sumTo($n)\n";
    $result = $n === 0 ? 0 : $n + sumTo($n - 1, $depth + 1);
    echo "{$indent}= $result\n";
    return $result;
}

sumTo(3);
Output
sumTo(3)
  sumTo(2)
    sumTo(1)
      sumTo(0)
      = 0
    = 1
  = 3
= 6

Each call waits for the one below it to finish; then the results flow back up.

Recursion on nested data

This is where recursion really earns its keep. A category tree can be any depth, and two short functions print and count it:

PHP 
<?php

$categories = [
    "name" => "Shop",
    "children" => [
        ["name" => "Books", "children" => [
            ["name" => "Fiction", "children" => []],
            ["name" => "Science", "children" => [
                ["name" => "Physics", "children" => []],
            ]],
        ]],
        ["name" => "Music", "children" => []],
    ],
];

function printTree(array $node, int $level = 0): void
{
    echo str_repeat("  ", $level), $node["name"], "\n";
    foreach ($node["children"] as $child) {
        printTree($child, $level + 1);
    }
}

function countNodes(array $node): int
{
    return 1 + array_sum(array_map(countNodes(...), $node["children"]));
}

printTree($categories);
echo "Total: ", countNodes($categories), "\n";
Output
Shop
  Books
    Fiction
    Science
      Physics
  Music
Total: 6

Building a tree from flat rows

Databases usually store trees as flat rows with a parent_id. A recursive function turns them into a nested structure — for example a nested HTML menu:

PHP 
<?php

$rows = [
    ["id" => 1, "parent_id" => null, "title" => "Home"],
    ["id" => 2, "parent_id" => null, "title" => "Products"],
    ["id" => 3, "parent_id" => 2, "title" => "Laptops"],
    ["id" => 4, "parent_id" => 2, "title" => "Phones"],
    ["id" => 5, "parent_id" => 4, "title" => "Android"],
];

function menuHtml(array $rows, ?int $parentId = null, int $level = 0): string
{
    $children = array_filter($rows, fn($r) => $r["parent_id"] === $parentId);
    if ($children === []) {
        return "";
    }
    $pad = str_repeat("  ", $level);
    $html = "$pad<ul>\n";
    foreach ($children as $row) {
        $html .= "$pad  <li>" . htmlspecialchars($row["title"]) . "\n";
        $html .= menuHtml($rows, $row["id"], $level + 2);
        $html .= "$pad  </li>\n";
    }
    return $html . "$pad</ul>\n";
}

echo menuHtml($rows);
Output
<ul>
  <li>Home
  </li>
  <li>Products
    <ul>
      <li>Laptops
      </li>
      <li>Phones
        <ul>
          <li>Android
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

Walking folders

File systems are trees too. Here a function totals the size of every file under a folder (it creates a few sample files first):

PHP 
<?php

@mkdir("demo/photos/2026", 0777, true);
file_put_contents("demo/readme.txt", str_repeat("a", 100));
file_put_contents("demo/photos/cat.jpg", str_repeat("b", 2000));
file_put_contents("demo/photos/2026/dog.jpg", str_repeat("c", 3000));

function folderSize(string $dir): int
{
    $total = 0;
    foreach (scandir($dir) as $entry) {
        if ($entry === "." || $entry === "..") {
            continue;
        }
        $path = "$dir/$entry";
        $total += is_dir($path) ? folderSize($path) : filesize($path);
    }
    return $total;
}

echo folderSize("demo"), " bytes\n";
Output
5100 bytes

PHP also offers RecursiveDirectoryIterator for this job (lesson 54), but writing it once by hand shows the pattern.

Limits

Each call uses memory on the call stack. Very deep recursion — hundreds of thousands of levels — can exhaust memory and crash the script, and naive recursion can repeat work exponentially (the Fibonacci function in lesson 30 needed a cache). Use recursion for naturally nested data and divide-and-conquer algorithms; use loops for simple repetition.

Try it yourself

Flatten a nested array of any depth into a simple list.

Try it yourself · main.php
Edit the code, copy it into main.php, then run it with php main.php (PHP 8.5). How to install PHP
Output
1, 2, 3, 4, 5, 6, 7, 8, 9
PreviousClosures and Callables