PHP – как использовать рекурсию
В данном примере мы выведем дерево элементов из массива. Будем использовать рекурсивное обращение функции к самой себе.
PHP пример рекурсии
Данная задача встречается довольно часто, особенно, при построении навигационных цепочек, меню, различных sitemaps и т.п.
Итак, для начала мы запишем простой массив с несколькими уровнями вложенности:
$tree = array( 'test0', 'test1' => array( 'test1.1', 'test1.2' => array( 'test1.2.1' ) ), 'test3' );
Видим что test0 и test3 не являются массивами, а вот в элементе массива test1 находится ассоциативный массив.
Значит, нам нужно проверять, является ли значение ключа массива, массивом ��
Надеюсь вы еще не запутались. Создадим функцию, и в ней вользопльемся is_array а после этого уже вызовем ее для нашей переменной $tree.
Собственно, сама функция:
Как видим, в параметр функции мы передаем массив;
затем создаем пустую строку;
затем проходим циклом по элементам массива и через сокращенную запись if ? else : (он же, тернарный оператор) – проверяем является ли ключ массивом (ключ это $twig) и если является – запускаем функцию.
Ну и конечно в ответе функции мы просим вернуть через return полученное “дерево” элементов.
Полный код выглядит вот так:
А результат выполнения, так:
Вот и всё, надеюсь вы всё поняли, и с рекурсией больше вопросов не будет ��
автор: Dmitriy
З 2011 року займаюся веб-розробкою. Зараз я – PHP Full Stack Developer.
Обговорити ваш проект, а також дізнатися більше про мене ви можете на цьому сайті:
dev.forwww.com
Читайте також:
2 коментаря
Alex Junior Padawan :
Спасибо за великолепную статью. Перелопатил много. Лучше чем здесь нигде не видел объяснения! Спасибо
Dmitriy :
Спасибо за отзыв)
Залишити відповідь Скасувати відповідь
Щоб відправити коментар вам необхідно авторизуватись.
Простой пример работы с рекурсиями в 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) и для элемента с так же есть родительский элемент и тд.
Поэтому будет вызываться рекурсивно $this->parent->getPath() т.е. этот же метод (getPath) но каждый раз для нового (родительского) элемента. Вызов пойдет по цепочке:
6 — name6 — 5
5 — name5 — 4
4 — name4 — 1
1 — name1 — null
и только когда не будет найден $this->parent (т.е. для элемента с перестанет вызываться рекурсия, начнутся вызовы $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 фреймворков, своими объектами:
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();
Примеры использования рекурсивной функции в PHP
Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Другими словами, рекурсия — это вызов функции внутри самой себя.
Простой пример рекурсии в PHP
Ниже показан примитивный пример использования рекурсии. По сути, ничего полезного данный код не делает. Более того, такой скрипт (бесконечный) переполнит стэк и аварийно завершит свою работу. Мы получим ошибку: Fatal error: Uncaught Error: Maximum function nesting level of ‘256’ reached, aborting! .
function recursion() < recursion(); >recursion();Факториал
Чтобы избавится от бесполезного и бесконечного вызова функции, необходимо прописать условие при котором эта функция вызывала бы сама себя, делая при этом что-то полезное и нужное. В классическом исполнение хорошо подходит пример функции вычисляющей факториал числа.
Факториал — произведение всех целых чисел, меньших или равных данному числу.
function factorial($n) < if ($n echo factorial(5); // 120Факториал числа так же можно вычислить, применив цикл, полностью заменяющий рекурсию:
function factorial($n) < $result = 1; for ($i = 1; $i return $result; > echo factorial(5); // 120Пример функции для защиты от XSS
Практически все данные (за редким исключением) из форм необходимо, во избежания XSS, пропускать через функцию htmlspecialchars() . Наша задача написать такую функцию, которая будет принимать массив (включая вложенные массивы) всех входящих данных и "прогонять" эти данные через встроенную функцию php htmlspecialchars() . И как раз здесь мы будем использовать рекурсию.
$value) < // Перебираем исходный массив $result[$key] = xss($value); // Рекурсивно вызываем функцию xss >return $result; // Возвращаемый "защищённый" массив > return htmlspecialchars($data, ENT_QUOTES); // Если это не массив, то вызываем htmlspecialchars() > // Предположим, что в строке запроса у нас такая строка: // /?name=John&age=<>45 $data = xss($_REQUEST); // Вызываем функцию, передав туда в качестве аргумента весь REQUEST // Распечатаем результат var_dump($data);Класс дерева категорий
В данном примере выведем дерево категорий, используя рекурсивный метод, написанный в ООП стиле.
CREATE TABLE IF NOT EXISTS category ( `id` INT NOT NULL AUTO_INCREMENT, `name` VARCHAR(100) NOT NULL, `parent_id` VARCHAR(40) NOT NULL, PRIMARY KEY ( id ) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci; INSERT INTO category (`id`, `name`, `parent_id`) VALUES (1, 'Компьютеры и периферия', 0), (2, 'Комплектующие для ПК', 0), (3, 'Смартфоны и смарт-часы', 0), (4, 'Телевизоры и медиа', 0), (5, 'Игры и приставки', 0), (6, 'Аудиотехника', 0), (7, 'Фото-видеоаппаратура', 0), (8, 'Офисная техника и мебель', 0), (9, 'Компьютерные системы', 1), (10, 'Периферия', 1), (11, 'Программное обеспечение и аксессуары', 1), (12, 'Системные блоки', 9), (13, 'Моноблоки', 9), (14, 'Неттопы и компьютеры-флешки', 9), (15, 'Платформы', 9), (16, 'Игровые компьютеры', 12), (17, 'Компьютеры для офиса', 12), (18, 'Компьютеры для бизнеса', 12), (19, 'Сенсорные моноблоки', 13), (20, 'Моноблоки с IPS экраном', 13), (21, 'Моноблоки с VA экраном', 13), (22, 'Моноблоки с TN экраном', 13), (23, 'Основные комплектующие', 2), (24, 'Хранение данных и охлаждение', 2);-
"; if(is_array($data)): foreach ($data as $item): echo '
- '; echo "id>\">"; echo $item->name; echo ""; if(count($item->children) > 0): $this->renderTemplate($item->children); endif; echo ''; endforeach; endif; echo "
Выводим дерево категорий:
require 'Category.php'; $category = new Category(); $data = $category->getData(); $tree = $category->createTree($data); $category->renderTemplate($tree);Основы хранения в БД древовидных структур можно почитать здесь.
Что такое рекурсия php
Рассмотрим задачу поиска соответствия со строкой, находящихся внутри неограниченного количества круглых скобок. Без использования рекурсии лучшее, что можно сделать - написать шаблон, который будет решать задачу для некоторой ограниченной глубины вложенности, так как обработать неограниченную глубину не предоставляется возможным. В Perl 5.6 предоставлены некоторые экспериментальные возможности, которые в том числе позволяют реализовать рекурсию в шаблонах. Специально обозначение (?R) используется для указания рекурсивной подмаски. Таким образом, приведём PCRE шаблон, решающий поставленную задачу (подразумевается, что используется модификатор PCRE_EXTENDED, незначащие пробелы игнорируются): \( ( (?>[^()]+) | (?R) )* \)
Вначале он соответствует открывающей круглой скобке. Далее он соответствует любому количеству подстрок, каждая из которых может быть последовательностью не-скобок, либо строкой, рекурсивно соответствующей шаблону (т.е. строкой, корректно заключённой в круглые скобки). И, в конце, идёт закрывающая круглая скобка.
Приведённый пример шаблона использует вложенные неограниченные повторения, поэтому использование однократных шаблонов значительно ускоряет процесс сопоставления, особенно в случаях, когда строка не соответствует заданной маске. Например, если его применить к строке: (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa() , то несоответствие будет обнаружено достаточно быстро. Но в случае, если однократные шаблоны не используются, сопоставление будет затягиваться на длительное время, так как существует множество способов разделения строки между квантификаторами + и *, и все они должны быть проверены, прежде чем будет выдано сообщение о неудаче.
Значение, устанавливаемое для захватывающей подмаски будет соответствовать значению, захваченному на наиболее глубоком уровне рекурсии. В случае, если приведённый выше шаблон сопоставляется со строкой (ab(cd)ef) , захваченным значением будет 'ef', которое является последним значением, принимаемым на верхнем уровне. В случае, если добавить дополнительные скобки \( ( ( (?>[^()]+) | (?R) )* ) \) , захваченным значением будет "ab(cd)ef". В случае, если в шаблоне встречается более, чем 15 захватывающих скобок, PCRE требуется больше памяти для обработки рекурсии, чем обычно. Память выделяется при помощи функции pcre_malloc, и освобождается соответственно функцией pcre_free. Если память не может быть выделена, сохраняются данные только для первых 15 захватывающих скобок, так как нет способа выдать ошибку out-of-memory изнутри рекурсии.
(?1) , (?2) и так далее могут быть использованы для рекурсивных подмасок. Также возможно использовать именованные подмаски: (?P>name) или (?&name) .
Если синтаксис ссылки на рекурсивную подмаску (как по имени, так и по числовому индексу) используется вне скобок, к которым он относится, он отрабатывает аналогично подпрограмме в языке программирования. Возьмём более ранний пример, указывающий что шаблон (sens|respons)e and \1ibility соответствует "sense and sensibility" и "response and responsibility", но не "sense and responsibility". Если вместо этого использовать шаблон (sens|respons)e and (?1)ibility , он совпадёт с "sense and responsibility" так же, как и с другими двумя строками. Однако, такие ссылки должны быть указаны после подмаски, на которую они ссылаются.
Максимальная строка обрабатываемой строки не должна превышать максимально доступного целого числа. Однако, так как для обработки подмасок и бесконечного повторения PCRE использует рекурсию, это означает, что размер обрабатываемых строк в некоторых шаблонах также может быть ограничен доступным размером стека.