Рекурсия

Представьте матрёшку. Чтобы добраться до самой маленькой куклы, вы открываете большую. Внутри такая же, только меньше, и вы повторяете то же действие. Самая маленькая кукла не открывается: на ней всё и заканчивается.

Функция может работать так же: решать задачу, вызывая саму себя для такой же задачи поменьше. Это называют рекурсией.

Классический пример — факториал, произведение чисел от 1 до n. Например, факториал 4 равен 4 * 3 * 2 * 1, то есть 24. Заметьте: факториал 4 — это 4, умноженное на факториал 3. Так и запишем:

<?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

Базовый случай и шаг рекурсии

В рекурсивной функции всегда две части:

• базовый случай — if ($n <= 1) { return 1; }: ответ известен сразу, без нового вызова, как у самой маленькой матрёшки;
• шаг рекурсии — return $n * factorial($n - 1);: задача сводится к такой же, но поменьше.

Каждый шаг должен приближать к базовому случаю. Здесь $n с каждым вызовом уменьшается на 1 и рано или поздно доходит до 1.

Как идут вызовы

Давайте проследим вызов factorial(3):

1. factorial(3) не может ответить сразу и ждёт factorial(2).
2. factorial(2) тоже ждёт — теперь factorial(1).
3. factorial(1) — базовый случай — возвращает 1.
4. factorial(2) получает 1 и возвращает 2 * 1, то есть 2.
5. factorial(3) получает 2 и возвращает 3 * 2, то есть 6.

Как вы уже знаете, у каждого вызова свои переменные. Пока вызовы ждут друг друга, в памяти одновременно живут три разные $n — 3, 2 и 1, каждая в своей рамке.

Здесь матрёшка расходится с рекурсией. Куклы только лежат одна в другой, а каждый вызов ждёт ответа следующего и доделывает свою часть работы на обратном пути.

Порядок частей результата

Рекурсия может собирать и строку. Тогда порядок частей зависит от того, где в выражении стоит рекурсивный вызов:

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

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

Разберём, как строится ответ:

1. upTo(3) — это upTo(2), к которому справа приписано 3.
2. upTo(2) — это upTo(1) и 2, а upTo(1) — это upTo(0) и 1.
3. upTo(0) — базовый случай — возвращает пустую строку ''.
4. На обратном пути части собираются в '', '1', '12' и, наконец, '123'.

Рекурсивный вызов стоит слева от $n, поэтому впереди оказываются части более глубоких вызовов. Если поменять части местами, $n . upTo($n - 1), программа напечатает 321: каждый вызов поставит свой $n перед остальной строкой.

Рекурсию выбирают для данных, вложенных друг в друга: папки в папках, комментарии с ответами на ответы, вложенные массивы. Для простого счёта, как факториал, подойдёт и обычный цикл.

Глубина рекурсии

Каждый вызов, который ждёт ответа, занимает память. PHP сам не превращает рекурсию в цикл, поэтому память растёт вместе с глубиной рекурсии, а бесконечная рекурсия заканчивается ошибкой.

На собеседовании спрашивают, что такое базовый случай и что будет без него. Ответ: это условие, при котором функция отвечает без нового вызова, а без него вызовы не кончаются, пока не закончится память.

Частая ошибка

Базовый случай забыли:

<?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)

Функция всегда вызывает себя снова, и цепочка вызовов не кончается. Каждый вызов занимает немного памяти, и, когда разрешённая память заканчивается, PHP останавливает программу. Числа в сообщении зависят от настроек PHP. Исправление — базовый случай в начале тела: if ($n === 0) { return 0; }.

Главное

• Рекурсивная функция вызывает саму себя для задачи поменьше.
• Базовый случай отвечает без нового вызова, а каждый шаг должен к нему приближать.
• У каждого вызова свои переменные, и ответ собирается на обратном пути: порядок частей задаёт место рекурсивного вызова в выражении.
• Без базового случая вызовы не кончаются, и PHP останавливает программу, когда заканчивается память.