Простой пример работы с рекурсиями в PHP.

Рекурсии часто используются при работе с базами данных, при получении данных из таблиц в которых есть иерархия - родительские и дочерние элементы. Например если нужно составить дерево элементов относительно одного (нужного) элемента - т.е. вывести все его родительские или дочерние элементы в порядке иерархии.
В данной заметке пример такой рекурсии и подробным описанием. Цель - научиться «читать» и составлять рекурсии.

Допустим в БД есть таблица с 3-мя полями:
id
name
parent_id

где поле parent_id ссылается на другой (родительский) элемент (на id) из этой же таблицы.

Для примера - есть 8 строк в таблице с такими данными (id - name - parent_id):
1 - name1 - null
2 - name2 - 1
3 - name3 - null
4 - name4 - 1
5 - name5 - 4
6 - name6 - 5
7 - name7 - null
8 - name8 - 4

Задача.

Составить метод, который будет относительно любого из элементов строить список (дерево) начиная с родительских элементов и до текущего, с разделителем «/». Например это может понадобиться для того, чтобы сформировать свою маршрутизацию, вывести в адресной строке названия рубрик интернет-магазина:
компьютернаяТехника / системныеБлоки / Core-i7

Данный пример из реального проекта использующего php-фреймворк с Active Record, т.е. каждая строка в БД представляет из себя отдельный объект. Поэтому в примере поля представляют из себя свойства объекта.

Допустим, что нужно получить такой URL для строки с id=6.

Реализация.

Метод использующий рекурсию (который добавляем в нужную модель/сущность) будет выглядеть так:

public function getPath(): string
{
    return ($this->parent_id ? $this->parent_id->getPath() . '/' : '') . $this->name;
}

В нем проверяется наличие родительского элемента (по полю parent_id) и в случае наличия - рекурсивный (повторный) вызов этого же метода но уже для родительского элемента.
Выражение после return берется в скобки для того, чтобы вызов $this->name присоединить к результату который будет получен.

Вызовы метода.

Итак, метод getPath() вызван для строки с id=6. Сначала будет несколько раз выполняться условие $this->parent_id т.к. для элемента «6 - name6 - 5» заполнено свойство parent_id (5) и для элемента с id=5 так же есть родительский элемент и тд.
Поэтому будет вызываться рекурсивно $this->parent->getPath() т.е. этот же метод (getPath) но каждый раз для нового (родительского) элемента. Вызов пойдет по цепочке:
6 - name6 - 5
5 - name5 - 4
4 - name4 - 1
1 - name1 - null

и только когда не будет найден $this->parent (т.е. для элемента с id=1) перестанет вызываться рекурсия, начнутся вызовы $this->name и будут возвращены данные в таком виде:
первый раз $this->name вернет «name1» и эта строка разместится на месте вызова $this->parent->getPath() добавив в конце '/', потом $this->name вернет «name4» добавив в конце '/' и тд.

Результат:
name1/name4/name5/name6

Чтобы проще понять, что же возвращает рекурсия, нужно представить ее работу с конца. Если рекурсивные вызовы в данном примере завязаны на условие $this->parent_id, то нужно мысленно подняться наверх до ближайшего элемента при котором данное условие будет нарушено и начнется по цепочке возврат данных с конца до самого первого элемента для которого изначально метод и вызывался.
Итак поднялись наверх до элемента при котором условие не выполняется и ставим, мысленно, результат выполнения метода (в примере это $this->name) на место вызова рекурсии на предыдущем шаге (в примере это $this->parent_id->getPath()). Тут мы еще к результату слэш добавляем. Остальные шаги будут выполняться аналогично с конца и до первого элемента.

Тестирование без БД.

Чаще всего такая задача стоит при извлечении данных из БД, но можно это реализовать (для тестирования) без использования Active Record фреймворков, своими объектами:

<?php

class Test
{
    private $id;
    private $name;
    private $parent_id;

    public function __construct(int $id, string $name, self $parent_id = null)
    {
        $this->id = $id;
        $this->name = $name;
        $this->parent_id = $parent_id;
    }

    public function getPath(): string
    {
        return ($this->parent_id ? $this->parent_id->getPath() . '/' : '') . $this->name;
    }
}

$obj1 = new Test(1, 'name1', null);
$obj2 = new Test(2, 'name2', $obj1);
$obj3 = new Test(3, 'name3', null);
$obj4 = new Test(4, 'name4', $obj1);
$obj5 = new Test(5, 'name5', $obj4);
$obj6 = new Test(6, 'name6', $obj5);
$obj7 = new Test(7, 'name7', null);
$obj8 = new Test(8, 'name8', $obj4);

echo $obj6->getPath();

Результат такой же :
name1/name4/name5/name6

Для другого элемента:

echo $obj8->getPath();

name1/name4/name8