Recursion

Picture a set of nesting dolls. To get to the smallest doll, you open the big one, and inside there is the same doll, only smaller, so you repeat the same move. The smallest doll does not open: that is where it all ends.

A function can work the same way: solve a task by calling itself for the same task, only smaller. This is called recursion.

The classic example is the factorial, the product of the numbers from 1 to n. For example, the factorial of 4 is 4 * 3 * 2 * 1, that is 24. Notice that the factorial of 4 is 4 times the factorial of 3. Let's write it that way:

<?php

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

echo factorial(4), "\n"; // 24
echo factorial(1), "\n"; // 1

The base case and the recursive step

A recursive function always has two parts:

• the base case, if ($n <= 1) { return 1; }: the answer is known at once, without a new call, like the smallest doll;
• the recursive step, return $n * factorial($n - 1);: the task turns into the same task, only smaller.

Each step must bring the function closer to the base case. Here $n gets 1 smaller with every call and sooner or later reaches 1.

How the calls go

Let's follow the call factorial(3):

1. factorial(3) cannot answer at once and waits for factorial(2).
2. factorial(2) waits too, now for factorial(1).
3. factorial(1) is the base case and returns 1.
4. factorial(2) gets 1 and returns 2 * 1, that is 2.
5. factorial(3) gets 2 and returns 3 * 2, that is 6.

As you already know, each call has its own variables. While the calls wait for each other, three different $n live in memory at once, 3, 2 and 1, each in its own frame.

Here the dolls and recursion part ways. The dolls only sit one inside another, while each call waits for the next one's answer and finishes its own part of the work on the way back.

The order of the result's parts

Recursion can build a string too. Then the order of the parts depends on where the recursive call stands in the expression:

function upTo(int $n): string
{
    if ($n === 0) {
        return '';
    }
    return upTo($n - 1) . $n;
}

echo upTo(3), "\n"; // 123

Let's see how the answer is built:

1. upTo(3) is upTo(2) with 3 added on the right.
2. upTo(2) is upTo(1) and 2, and upTo(1) is upTo(0) and 1.
3. upTo(0) is the base case and returns the empty string ''.
4. On the way back the parts come together as '', '1', '12' and finally '123'.

The recursive call stands to the left of $n, so the parts of the deeper calls come first. If you swap the parts, $n . upTo($n - 1), the program prints 321: each call puts its own $n in front of the rest of the string.

Recursion is the choice for data nested inside itself: folders in folders, comments with replies to replies, nested arrays. For plain counting, like the factorial, an ordinary loop works too.

The depth of recursion

Each call that waits for an answer takes up memory. PHP does not turn recursion into a loop by itself, so very deep recursion uses a lot of memory, and endless recursion ends with an error.

Interviewers ask what a base case is and what happens without one. The answer: it is the condition under which the function answers without a new call, and without it the calls do not end until memory runs out.

Common mistake

The base case was forgotten:

<?php

function countDown(int $n): int
{
    return countDown($n - 1); // ✗
}

echo countDown(3), "\n";

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 2097152 bytes)

The function always calls itself again, and the chain of calls never ends. Each call takes a little memory, and when the allowed memory runs out, PHP stops the program. The numbers in the message depend on PHP's settings. The fix is a base case at the start of the body: if ($n === 0) { return 0; }.

Key points

• A recursive function calls itself for a smaller task.
• The base case answers without a new call, and every step must bring the function closer to it.
• Each call has its own variables, and the answer is built on the way back: the place of the recursive call in the expression sets the order of the parts.
• Without a base case the calls never end, and PHP stops the program when memory runs out.