Solve Small Problems with Recursion

What recursion is

A recursive function is a user-defined function that calls itself. PHP allows this because a function declared with the function keyword can be called from inside its own body. The technique suits problems with a self-similar shape, such as a countdown, a factorial or an array that contains more arrays.

Every safe recursive function has two parts:

1. A base case, which returns without calling the function again.
2. A recursive case, which calls the function with a smaller or simpler input.

If the recursive case never moves toward the base case, the function keeps calling itself. The PHP manual treats infinite recursion as a programming error. It also warns that very deep recursion, over roughly 100-200 levels, can exhaust the stack and end the script. For that reason, keep recursion for bounded problems.

Start with a countdown

The smallest useful case is a countdown. The base case is $n <= 0, which returns an empty array. Otherwise the function returns the current number followed by the countdown of $n - 1.

<?php
function countdown(int $n): array
{
    if ($n <= 0) {
        return [];
    }

    return [$n, ...countdown($n - 1)];
}

echo json_encode(countdown(4));

[4,3,2,1]

Each call waits for the call below it to finish. When countdown(0) returns [], the earlier calls finish in reverse order and build the final list.

Guard the input

A base case must cover every input the function accepts. A factorial function that checks only $n === 0 would recurse forever on -1. Decide what the invalid inputs are, and reject them before recursing.

<?php
function factorial(int $n): int
{
    if ($n < 0) {
        throw new InvalidArgumentException('n must not be negative');
    }
    if ($n <= 1) {
        return 1;
    }

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

try {
    echo factorial(5), "\n";
    echo factorial(-1), "\n";
} catch (InvalidArgumentException $e) {
    echo $e->getMessage(), "\n";
}

120
n must not be negative

The first call reaches the base case after five calls. The second call fails fast with an exception and never recurses.

Nested arrays and depth limits

Nested arrays are the most practical use of recursion in everyday PHP. You cannot know in advance how many levels a value has, but the structure repeats: each element is either a plain value or another array of the same kind.

The pattern is to loop over the items. When an item is an array, call the same function on it. Otherwise, handle the plain value directly. Here the base case is built into the loop: an array with no nested arrays never makes a recursive call. The function below also carries a depth counter, so unexpectedly deep input fails with a clear message rather than risking the stack.

<?php
function flatten(array $items, int $depth = 0, int $maxDepth = 5): array
{
    if ($depth > $maxDepth) {
        throw new RuntimeException('Nesting is too deep');
    }

    $result = [];
    foreach ($items as $item) {
        if (is_array($item)) {
            $result = array_merge($result, flatten($item, $depth + 1, $maxDepth));
        } else {
            $result[] = $item;
        }
    }

    return $result;
}

echo json_encode(flatten([1, [2, [3, 4]], 5])), "\n";

try {
    flatten([[[1]]], 0, 1);
} catch (RuntimeException $e) {
    echo $e->getMessage(), "\n";
}

[1,2,3,4,5]
Nesting is too deep

The extra parameters have defaults, so callers can ignore them. Passing state through parameters keeps the function self-contained and deterministic. Avoid global variables for counters.

A checklist for writing recursion

• Write the base case first, before the recursive call.
• Make sure each call receives a smaller input, such as a smaller number or a nested array one level down.
• Return the result of the recursive call, or combine it into your result. A forgotten return produces null.
• Test the empty input, a flat input and a deeply nested input.
• Add a depth limit when the data comes from outside your control.

Exercise contract

Write sumNested(array $items): int. The array contains integers and other arrays. It may be empty, and its arrays may be empty too. Return the sum of every integer at every level. Assume a depth of at most 20. Tests compare the returned integer, so do not print anything.

The key decision is how to treat each item. Use is_array($item) to choose between a recursive call and adding the integer directly. An empty array contributes 0, so it needs no special case, because the loop simply does not run.

Recap

Recursion is a function calling itself on a smaller problem. Define the base case, move toward it on every call, and bound the depth when input might be deep. For nested arrays, check each element with is_array() and recurse only into arrays.