Recursive Functions

A recursive function is a function that calls itself. It is a way to solve a big problem by solving a smaller copy of the same problem.

Every recursive function needs two parts:

1. A base case: the simple situation where it stops.
2. A recursive case: where it calls itself with a smaller problem.

Countdown

1
2
3
4
5
6
7
8
9
10
11
12
13

<?php
function countdown(int $n): void
{
    if ($n === 0) {          // base case
        echo "Go!";
        return;
    }

    echo $n . " ";
    countdown($n - 1);       // recursive case
}

countdown(3);

1

3 2 1 Go!

Factorial

The factorial of 4 is 4 * 3 * 2 * 1. Notice the pattern: 4! = 4 * 3!.

1
2
3
4
5
6
7
8
9
10
11

<?php
function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }

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

echo factorial(5);

1

120

What happens step by step

factorial(3) calls factorial(2), which calls factorial(1). That returns 1, then 2 returns 2 * 1, then 3 returns 3 * 2. Each call waits for the next one to finish.

Where recursion really helps: nested data

When data has levels of unknown depth, such as menus, comments with replies or folders, recursion fits naturally.

1
2
3
4
5
6
7
8
9
10
11
12
13

<?php
function sumAll(array $data): int
{
    $total = 0;

    foreach ($data as $item) {
        $total += is_array($item) ? sumAll($item) : $item;
    }

    return $total;
}

echo sumAll([1, [2, 3], [4, [5, 6]]]);

1

21

A menu tree

1
2
3
4
5
6
7
8
9
10
11
12
13

<?php
function printMenu(array $items, int $level = 0): void
{
    foreach ($items as $name => $children) {
        echo str_repeat("  ", $level) . "- " . $name . "\n";
        printMenu($children, $level + 1);
    }
}

printMenu([
    "Home" => [],
    "Shop" => ["Books" => [], "Pens" => ["Gel" => []]],
]);

1
2
3
4
5

- Home
- Shop
  - Books
  - Pens
    - Gel

Limits

• Each call uses memory. Very deep recursion can run out of memory.
• A missing base case means endless calls until the script crashes.
• PHP does not optimise tail calls, so a loop is usually faster.

If you can solve the problem with a simple loop, use the loop. Use recursion when the data is nested.

1
2
3
4
5
6
7
8
9
10
11

<?php
function sumDigits(int $n): int
{
    if ($n < 10) {
        return $n;
    }

    return ($n % 10) + sumDigits(intdiv($n, 10));
}

echo sumDigits(1234);

1

10