Recursive Functions

What Is a Recursive Function?

In simple terms: A recursive function is a function that calls itself to solve a smaller version of the same problem, until the problem becomes so small that the answer is obvious. Technically: Recursion is a technique in which a function's body contains a call to the same function. Each call gets its own set of local variables on the call stack. A correct recursive function always has:

1. A base case — a condition where it returns a result without calling itself.
2. A recursive case — where it calls itself with input that moves closer to the base case.

Why Recursion Is Useful

Some data is naturally self-similar: a category contains subcategories, which contain subcategories; a folder contains folders; a comment has replies, which have replies; a JSON document contains nested arrays. For such structures, a recursive function often mirrors the shape of the data and is much simpler than an equivalent loop.

A First Example: Factorial

The factorial of n (written n!) is n × (n − 1) × … × 1. It can be defined recursively:

• 1! = 1 (base case)
• n! = n × (n − 1)! (recursive case)

<?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(1) . "\n";

Output

120
1

How the Calls Unfold

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))       ← base case reached
= 120

1. Each call waits for the result of the next call.
2. When factorial(1) reaches the base case, it returns 1 without recursing.
3. The waiting calls then complete in reverse order, multiplying as they return.

The Call Stack

Every function call is placed on the call stack, a memory area that records where each call should return to and stores its local variables. Each recursive call adds a new frame to the stack; each return removes one. You can watch this happen by tracing the calls:

<?php
function countdown(int $n, int $depth = 0): void
{
    $indent = str_repeat('  ', $depth);
    if ($n === 0) {
        echo "{$indent}Liftoff!\n";
        return;
    }
    echo "{$indent}Entering countdown($n)\n";
    countdown($n - 1, $depth + 1);
    echo "{$indent}Leaving countdown($n)\n";
}
countdown(3);

Output

Entering countdown(3)
  Entering countdown(2)
    Entering countdown(1)
      Liftoff!
    Leaving countdown(1)
  Leaving countdown(2)
Leaving countdown(3)

The "Leaving" lines appear in reverse order because each call only finishes after the call it made has finished. Code after the recursive call runs on the way back up.

Recursion With Nested Data

Summing a Nested Array

<?php
function nestedSum(array $values): int|float
{
    $total = 0;
    foreach ($values as $value) {
        if (is_array($value)) {
            $total += nestedSum($value);   // recursive case: go deeper
        } else {
            $total += $value;              // base case: a plain number
        }
    }
    return $total;
}
echo nestedSum([1, [2, 3], [4, [5, 6]], 7]) . "\n";

Output

28

The function does not need to know how deep the nesting goes. Whenever it meets an array, it hands that array to a new call of itself.

Flattening a Nested Array

<?php
function flatten(array $values): array
{
    $result = [];
    foreach ($values as $value) {
        if (is_array($value)) {
            $result = [...$result, ...flatten($value)];
        } else {
            $result[] = $value;
        }
    }
    return $result;
}
echo implode(', ', flatten([1, [2, 3], [4, [5, [6]]], 7])) . "\n";

Output

1, 2, 3, 4, 5, 6, 7

Each nested array is flattened by a recursive call, and the results are combined with the spread operator.

Practical Example: Category Tree

Online shops store categories in a database table where each category has an optional parent. Displaying them as a tree is a classic recursive task.

<?php
$categories = [
    ['id' => 1, 'name' => 'Electronics', 'parent' => null],
    ['id' => 2, 'name' => 'Laptops', 'parent' => 1],
    ['id' => 3, 'name' => 'Gaming Laptops', 'parent' => 2],
    ['id' => 4, 'name' => 'Phones', 'parent' => 1],
    ['id' => 5, 'name' => 'Books', 'parent' => null],
];
function printTree(array $categories, ?int $parentId = null, int $depth = 0): void
{
    foreach ($categories as $category) {
        if ($category['parent'] === $parentId) {
            echo str_repeat('  ', $depth) . '- ' . $category['name'] . "\n";
            printTree($categories, $category['id'], $depth + 1);
        }
    }
}
printTree($categories);

Output

- Electronics
  - Laptops
    - Gaming Laptops
  - Phones
- Books

Step-by-Step Explanation

1. The first call looks for top-level categories (parent === null): Electronics and Books.
2. For each category found, the function prints it and calls itself with that category's ID as the new parent, one level deeper.
3. The base case is implicit: when no categories have the given parent, the loop prints nothing and the call returns.
4. $depth controls indentation, increasing by one level with each recursive call. This version scans the whole list in every call, which is fine for a few hundred categories. For large trees, group categories by parent first ($byParent[$parentId][] = $category) so each call only loops over its own children.

Fibonacci and the Cost of Repeated Work

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, …) is defined recursively, but a direct recursive implementation is very slow:

<?php
function fibonacci(int $n): int
{
    if ($n < 2) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}
echo fibonacci(10) . "\n";

Output

55

Each call makes two more calls, and the same values are calculated again and again: fibonacci(30) already needs more than a million calls. Two common fixes:

• Memoization: remember results that have already been calculated, for example in a static array (see Static Variables, which includes a memoized Fibonacci example).
• Iteration: a simple loop that keeps the last two values computes the result in n steps. Recursion is elegant, but always consider how many calls it will make.

Recursion Depth and Its Limits

Each recursive call uses memory on the call stack. Recursing too deeply — for example, because the base case is never reached — eventually fails.

function broken(int $n): int
{
    return broken($n - 1);   // no base case: never stops
}

What happens depends on the configuration:

• PHP 8.3+ detects deep recursion and throws an Error such as "Maximum call stack size of … reached. Infinite recursion?" (controlled by the zend.max_allowed_stack_size setting).
• Older versions may exhaust memory_limit or crash the process.
• With the Xdebug extension enabled, recursion is stopped earlier by its nesting limit (xdebug.max_nesting_level). PHP does not optimize tail recursion, so even a correct recursive function can fail for very deep inputs (for example, a recursion depth of hundreds of thousands). For long linear sequences, use a loop; reserve recursion for tree-shaped data whose depth is naturally limited.

Converting Recursion to Iteration

<?php
function factorialIterative(int $n): int
{
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}
echo factorialIterative(5) . "\n";

Output

120

The loop version uses constant stack space. For tree structures, the iterative equivalent needs an explicit stack (an array of items still to process), which is usually less readable than recursion.

When to Use Recursion

Related built-in tools: array_walk_recursive() applies a function to every leaf value of a nested array, and RecursiveIteratorIterator with RecursiveDirectoryIterator walks directory trees.

Common Mistakes

Missing or Unreachable Base Case

Effect: Infinite recursion and a stack overflow error. Fix: Define the base case first, and make sure every recursive call moves closer to it (for example, $n - 1, a smaller array, or a child node).

Not Returning the Recursive Result

function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    $n * factorial($n - 1);   // result calculated but not returned
}

Fix: return $n * factorial($n - 1);.

Repeating the Same Work

Effect: Exponential running time (as in naive Fibonacci). Fix: Memoize results or use iteration.

Using Recursion for Very Deep Linear Problems

Effect: Stack overflow on large inputs. Fix: Use a loop.

Best Practices

• Write the base case first and keep it obvious.
• Make each recursive call work on a strictly smaller problem.
• Use recursion for naturally nested data with limited depth.
• Memoize or iterate when the same subproblems repeat.
• Pass depth or path information as parameters when you need indentation or limits. Official reference: https://www.php.net/manual/en/functions.user-defined.php