что такое рекурсия php

Рекурсия на PHP — алгоритм, применение

К написанию статьи сподвигли часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах, но в последствии решил реализовать на PHP, дабы снять зависимость от СУБД. На простом примере я покажу как можно пройти от корня иерархии до каждого конечного элемента и обратно, информация скорее для новичков.

Итак, тестовая иерархия, с которой нам предстоит работать:

В базе данных имеется самая простая таблица на самом простом MSSQL сервере, тонкости подключения опустим, наша цель — разобраться с иерархией и рекурсией.

Описание полей есть в комментариях, чуть подробнее о поле access:

По умолчанию в моей системе для каждого нового документа проставляется inherit, то есть наследование от родителя. Для нашего эксперимента для некоторых эелементов пропишем доменные группы. В группе Domain Users моя учётная запись имеется, а вот в AD Group Secret меня нет.

Теперь предлагаю получить необходимые данные и перейти непосредственно к делу:

Задача №1

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

Задача №2

Необходимо гибко управлять доступами, то есть, давать права на группы, отдельные документы и т.д., по аналогии с файловой системой NTFS, можно закрыть права на всю папку, но для одного документа в этой папке доступ нарезать — тоже самое должно получиться и у нас.

Задача №3

Необходимо скрыть от пользователей ресурсы, к которым у них нет доступа, но самое главное, при наличии прав хотя бы на один документ где то в глубине закрытой для него ветки, делать видимыми элементы ведущие к этому документу (иначе как пользователь до него доберётся?)

Вот собственно базовая функция:

Описание по большей части привёл в комментариях, но если говорить просто — после того как цикл foreach проходит строку и делает что то с данными(в нашем случае просто копирует данные в другой массив, добавляя поле level и точки к имени), он запускает эту же функцию, передав ей uid строки, и поскольку в условии if мы сравниваем его с pid, то следующий запуск однозначно захватит дочерние элементы. Цикл foreach перебирает все строки у которых uid родителя совпадает с переданным значением, поэтому перезапуская саму себя, функция отработает на каждом элементе каждого уровня. Для наглядности, мы так же передаём level увеличивая его на единицу. В итоге мы увидим какой документ какой уровень вложенности имеет.

Выводим массив $array в браузер:

Уже не плохо, не так ли?

А теперь немного усложним нашу функцию:

Разбираем по порядку:

1. Добавлено поле path — для формирования пути, добавляем к значению «/» и имя строки, затем полученное значение передаём в функцию, где история повторяется и на выходе получается путь от корня до элемента.

3. Добавлен индекс $array_idx_lvl = array();. Этот индекс нам так же потребуется позже, смысл таков — результирующий набор складывается не в одну кучу, а с разбивкой на массивы индексируемые по level.

4. Поле Access. Когда функция запускает саму себя, вместе с остальными параметрами она передаёт свою настройку прав $_row[‘access’] дочерям, а далее происходит следующее, проверяются права — если выставлено наследование (inherit), то применяются права родителя, если нет — через in_array проверяем, есть ли указанная в access доменная группа среди групп зашедшего пользователя. Если есть — добавляем в строку allow (разрешить), иначе deny (запрет).

Итоговый результат:

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

Почему здесь нужен проход в обратную сторону? Предположим у пользователя закрыт доступ для всего контента за исключением одного, самого дальнего(на последнем уровне) документа, если подумать, логично было бы брать начало от доступного, и вести его к корню дерева, показывая только нужные элементы.

Что делает эта функция — принимает в качестве параметра uid строки, с которой нужно начать действовать, обращается к этой строке и проверяет видимость. Если в поле view не show(т.е. показывать), а что то другое, проверяет что находится в безопасности, и если там стоит allow(доступ открыт), делает элемент видимым, в противном случае скрытым(hide), затем запускает себя же, передавая свой pid и настройку видимости, а так же переменную $ident увеличенную на 1, тем самым блокируя последующие самозапуски. При втором проходе, по переданному pid находится родительский элемент, выполняется та же проверка, за исключением одного, если от дочернего в переменной $view передано ‘show‘, то не смотря ни на что, текущему элементу так же присвоится show, то есть видимый.

На мой взгляд, работа с ограничителем — самый оптимальный вариант, ибо представьте ситуацию, на 10 уровне у нас 100 документов, для полного обхода всего дерева, нам нужно запускать эту функцию на каждом элементе, т.к. если на последнем уровне мы запустим функцию 100 раз, то выполняя самозапуски, перебор 100 раз дойдёт до корня. Если умножить на 10 уровней — уже получится 1000 циклов, что не есть хорошо, поэтому подъём нужно осуществлять равномерно, уровень за уровнем.

Запускает эту функцию следующий код:

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

Перед запуском, я намеренно прописал разрешающую группу для пункта «Отчет для налоговой», чтобы наглядно показать что код отрабатывает корректно. Несмотря на то, что доступ к разделу «Бухгалтерская отчетность» закрыт, он видимый.

Вот и собственно всё, думаю с задачей мы справились, основа получена, алгоритм работает, можно применить в реальной системе.

Источник

Рекурсивные алгоритмы на PHP. Часть 1. Основы рекурсии

В этой статье я расскажу о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Понятие рекурсии

Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.

Существует два варианта реализации рекурсивных функций: простой и сложный. В простом случае рекурсивная функция вызывает саму себя. В сложном — функция вызывает другую функцию, которая вызывает исходную функцию, с которой всё начиналось.

Рассмотрим пример из жизни. Если взять два больших зеркала и поставить их друг напротив друга, то можно увидеть бесконечный коридор из изображений зеркал. Каждое зеркало несёт в себе функцию отражения пространства расположенного перед ним. Поэтому здесь мы имеем пример сложной рекурсии (функция вызывает другую функцию, которая вызывает исходную).

Другим примером можно взять всем хорошо известное детское стихотворение:

Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).

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

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.

Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.

Источник

PHP скрипты

Apache

PHP Скрипты

Для Дизайна Сайта

Навигация

Партнеры

При объяснении решения задач математики очень часто применяют словосочетание «по индукции», которое многих ставит в тупик, так как это понятие является не самым простым. В программировании тоже имеется своеобразная индукция, называемая рекурсией.

Например, попробуем написать функцию с помощью обычного цикла for, возвращающую факториал числа. Из курса математики известно, что он вычисляется следующим образом: n! =1*2. *(n-1 )*n. Причем 0!=1, а факториала отрицательных чисел не бывает (листинг 7.13).

Листинг 7.13. Функция нахождения факториала числа без рекурсии.

‹html›
‹head›
‹title›Функция нахождения факториала числа без рекурсии‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
<
if ($num

Итак, задача решена, как говорится, «в лоб». В случае передачи отрицательных значений функция будет возвращать 0. Это реализуется с помощью первого оператора if. Далее если передано число 0, то возвращаем единицу. И наконец, в цикле for вычисляем факториал при любых других значениях.

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

n! = 1, если n=0
n! = n*(n-1)!, если n>0

Заметьте, что второе утверждение содержит в себе знак факториала. Именно в этом и состоит основной смысл рекурсии. При решении определенной задачи мы используем то, что нам нужно найти. В программировании функцию называют рекурсивной, если в ее описании присутствует обращение саму на себя.

Итак, вернемся к рассуждению о факториале. При решении задач с помощью рекурсии всегда надо иметь два типа утверждений: базисное и рекурсивное. В нашем случае базисным утверждением является n! = 1, если n = 0. Как вы, наверное, уже догадались, работая с рекурсивным утверждением, мы должны перейти к базисному и получить результат. Теперь попробуем реализовать все это на практике (листинг 7.14).

Листинг 7.14. Функция нахождения факториала числа с рекурсией

‹html›
‹head›
‹title›Функция нахождения факториала числа с рекурсией‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
<
if ($num

В этом случае первые два условия аналогичны примеру, разобранному выше. Но теперь вместо цикла fоr мы записываем рекурсивное выражение, в котором функция вызывает сама себя. В нашей программе это происходит до тех пор, пока в качестве входного параметра не будет число 0, при котором функция возвратит 1. Причем это значение возвратится не в основную программу, а в тело предыдущей функции. Эта функция, в свою очередь, возвратит свое значение в тело следующей функции и т. д., пока нужное значение не возвратится в основную программу.

Источник

Рекурсия и многомерные структуры в PHP

Дан массив многомерный произвольного уровня вложенности, например, такой:

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

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

Зато для перебора такого массива очень удобно будет использовать рекурсию.

Для начала сделаем функцию, в которую параметром будем передавать наш массив, а в функции сделаем цикл для перебора нашего массива:

Давайте теперь будем разделять в цикле элементы-примитивы и элементы-массивы:

Дан многомерный массив произвольного уровня вложенности, например, такой:

С помощью рекурсии выведите все примитивные элементы этого массива на экран.

Сумма элементов массива

Давайте найдем сумму примитивных элементов нашего массива:

Дан многомерный массив произвольного уровня вложенности, например, такой:

С помощью рекурсии найдите сумму элементов этого массива.

Дан многомерный массив произвольного уровня вложенности, содержащий внутри себя строки, например, такой:

С помощью рекурсии слейте элементы этого массива в одну строку:

Манипуляции с элементами

Давайте что-нибудь сделаем с перебираемыми элементами массива, к примеру, запишем им в конец знак ‘!’ :

Дан многомерный массив произвольного уровня вложенности, например, такой:

Возведите все элементы-числа этого массива в квадрат.

Источник

Что такое рекурсия php

Cтатические переменные

Если в теле пользовательской функции объявлена статическая переменная, то компилятор не будет ее удалять после завершения работы функции. Пример работы пользовательской функции, содержащей статические переменные:

Данный сценарий выводит строку:

1 2 3 4 5 6 7 8 9 10

Если мы удалим инструкцию static, будет выведена строка:

1 1 1 1 1 1 1 1 1 1

Это связано с тем, что переменная $a будет удаляться при завершении работы функции и обнуляться при каждом ее вызове. Переменная $a инкрементируется сразу после обнуления, а только потом выводится.

Рекурсивные функции

Рассмотрим пример рекурсивной функции (прямой), используемой при вычислении факториала x! :

В рассмотренном примере пользовательская функция factorial() вызывает сама себя, что является прямой рекурсией.

При создании рекурсивных функций необходимо соблюдать осторожность, стараясь избегать зацикливания.

Вот пример неправильного использования рекурсивной функции:

Условно определяемые функции

PHP позволяет, в зависимости от определенных факторов, одной и той же функции выполнять различные действия. Рассмотрим пример:

php
$ phpver = phpversion ();
if ($ phpver [ 0 ] === «5» )
<
function getversion () < return "Вы используете PHP5" ; >
>
if ($ phpver [ 0 ] === «4» )
<
function getversion () < return "Вы используете PHP4" ; >
>
if ($ phpver [ 0 ] === «3» )
<
function getversion ( ) < return "Вы используете PHP3" ; >
>
echo @ getversion ();
?>

Рассмотренный скрипт выводит версию используемого интерпретатора PHP. Одна и та же функция getversion() может возвращать различный результат, в зависимости от значения переменной $phpver.

Возврат функцией ссылки

Рассмотренный скрипт выведет 0, поскольку если вы измените значение одной из переменных ($a или $b), автоматически будет изменено значение другой переменной. Для разрыва связи между объектом и ссылкой, используйте оператор UnSet(). Подробнее о ссылках можно узнать здесь.

Источник