Рекурсия php


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

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

image

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

Создадим таблицу:

CREATE TABLE [dbo].[Test]( 	[uid] [int] IDENTITY(1,1) NOT NULL, -- уникальное поле, автоинкрементное 	[pid] [int] NULL, -- это поле указывает на элемент уровнем выше, содержит uid родителя 	[name] [varchar](255) NULL, 	[access] [varchar](50) NULL, -- права доступа ) ON [PRIMARY]   

Наполним сведениями:

image

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

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

Что ещё мы имеем. Массив, содержащий список моих доменных групп. Достаётся он достаточно просто, на IIS включена аутентификация Windows, всё работает прозрачно, в PHP логин зашедшего находится в переменной $_SERVER[«AUTH_USER»], далее LDAP запросом получаем список групп.

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

$stmt = $PDO->query("SELECT * FROM Test"); $table = $stmt->fetchAll(); //Получим таблицу из БД  $groups = LDAP::getGroups('$login'); //Получим группы ActiveDirectory 

Задача №1

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

Задача №2

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


Задача №3

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

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

$array = array(); //выходной массив  function recursive($data, $pid = 0, $level = 0){  global $array;   foreach ($data as $row) { //перебираем строки  if ($row['pid'] == $pid) { //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта  //Собираем строку в ассоциативный массив  $_row['uid'] = $row['uid'];  $_row['pid'] = $row['pid'];  $_row['name'] = $_row['name'] = str_pad('', $level*3, '.').$row['name']; //Функцией str_pad добавляем точки  $_row['level'] = $level; //Добавляем уровень   $array[] = $_row; //Прибавляем каждую строку к выходному массиву   //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть  //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом)  recursive($data, $row['uid'], $level + 1);  }  } } recursive($table); //Запускаем 

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


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

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

image

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

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

$array = array(); //выходной массив $array_idx_lvl = array(); //индекс по полю level  function recursive($data, $pid = 0, $level = 0, $path = "", $access_parent = "inherit"){  global $array;  global $array_idx_lvl; //Индекс по level  global $groups; //доменные группы   //перебираем строки  foreach ($data as $row) {  //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта  if ($row['pid'] == $pid) {  //Собираем строку в ассоциативный массив  $_row['uid'] = $row['uid'];  $_row['pid'] = $row['pid'];  $_row['name'] = str_pad('', $level*3, '.').$row['name'];  $_row['level'] = $lev.  

l[$level][$row['uid']] = $row['uid']; //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом) recursive($data, $row['uid'], $level + 1, $_row['path'], $_row['access']); } } } recursive($table); //Запускаем

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

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

2. Результирующий массив теперь формируется не по порядку, начиная с нуля а с привязкой к uid — $array[$row[‘uid’]] = $_row;. В данном случае это ни как не влияет на работу скрипта, но возможность обращаться к строке по индексу, а не перебором в цикле потребуется нам в дальнейшем, когда будем разбирать проход по дереву в обратную сторону.

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


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

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

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

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

Приступим:

 

//Функция прохода вверх по дереву на один уроверь от заданного uid, устанавливает //свойство видимости себе и родителю в зависимости от доступа или заданной ранее видимости... function backRecursive($uid, $view = null, $ident = 0) { global $array; //Если поднялись не больше чем на один уровень if($ident <= 1) { //Если видимость уже есть - не меняем текущую строку, иначе //проверяем доступ и то что пришло от дочки if($array[$uid]['view'] != 'show') { $array[$uid]['view'] = ($array[$uid]['access'] == 'allow' or $view == 'show') ? 'show' : 'hide'; } backRecursive($array[$uid]['pid'], $array[$uid]['view'], $ident+1); } }

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


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

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

function startBack(){  global $array_idx_lvl;   $levels = array_keys($array_idx_lvl); //получаем массив уровней  $maxLevel = max($levels); //Находим самый глубокий уровень дерева   //Проходимся циклом по каждому уровню начиная с самого большого  for ($i = $maxLevel; $i > 0; $i--) {  $uids = array_keys($array_idx_lvl[$i]);   //На текущем уровне обходим все элементы и по каждому инициируем обработку и движение на 1лвл  foreach ($uids as $uid) {  backRecursive($uid);  }  } } 

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

А вот и картинка:

image


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

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

habr.com

Главная Страница » Книги по PHP » Самоучитель PHP 5 для чайников с примерами » Рекурсия

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

Например, попробуем написать функцию с помощью обычного цикла 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)
 {
   return 0;
 }
if ($num == 0)
 {
   return 1;
 }
for ($i = 1, $sum = 1; $i <= $num; $i++)
 {
   $sum = $sum * $i;
 }
return $sum;
}
echo factorial(3); // выведет 6
?›
‹/body›
‹/html›

Итак, задача решена, как говорится, «в лоб». В случае передачи отрицательных значений функция будет возвращать 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 < 0)
 {
   return 0;
 }
 if ($num == 0)
 {
   return 1;
 }
 return $num*factorial($num-1); // рекурсивный вывод
}
echo factorial(3); // выведет 6
?›
‹/body›
‹/html›

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

www.php-s.ru

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

Рекурсия php

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

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

image

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

Создадим таблицу:

CREATE TABLE [dbo].[Test](  	[uid] [int] IDENTITY(1,1) NOT NULL, -- уникальное поле, автоинкрементное  	[pid] [int] NULL, -- это поле указывает на элемент уровнем выше, содержит uid родителя  	[name] [varchar](255) NULL,  	[access] [varchar](50) NULL, -- права доступа  ) ON [PRIMARY]  

Наполним сведениями:

image

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

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

Что ещё мы имеем. Массив, содержащий список моих доменных групп. Достаётся он достаточно просто, на IIS включена аутентификация Windows, всё работает прозрачно, в PHP логин зашедшего находится в переменной $_SERVER[«AUTH_USER»], далее LDAP запросом получаем список групп.

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

$stmt = $PDO->query("SELECT * FROM Test");  $table = $stmt->fetchAll(); //Получим таблицу из БД    $groups = LDAP::getGroups('$login'); //Получим группы ActiveDirectory  

Задача №1

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

Задача №2

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

Задача №3

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

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

$array = array(); //выходной массив    function recursive($data, $pid = 0, $level = 0){   global $array;     foreach ($data as $row) { //перебираем строки   if ($row['pid'] == $pid) { //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта   //Собираем строку в ассоциативный массив   $_row['uid'] = $row['uid'];   $_row['pid'] = $row['pid'];   $_row['name'] = $_row['name'] = str_pad('', $level*3, '.').$row['name']; //Функцией str_pad добавляем точки   $_row['level'] = $level; //Добавляем уровень     $array[] = $_row; //Прибавляем каждую строку к выходному массиву     //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть   //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом)   recursive($data, $row['uid'], $level + 1);   }   }  }  recursive($table); //Запускаем  

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

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

image

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

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

$array = array(); //выходной массив  $array_idx_lvl = array(); //индекс по полю level    function recursive($data, $pid = 0, $level = 0, $path = "", $access_parent = "inherit"){   global $array;   global $array_idx_lvl; //Индекс по level   global $groups; //доменные группы     //перебираем строки   foreach ($data as $row) {   //Начинаем со строк, pid которых передан в функцию, у нас это 0, т.е. корень сайта   if ($row['pid'] == $pid) {   //Собираем строку в ассоциативный массив   $_row['uid'] = $row['uid'];   $_row['pid'] = $row['pid'];   $_row['name'] = str_pad('', $level*3, '.').$row['name'];   $_row['level'] = $level; //Добавляем уровень   $_row['path'] = $path."/".$row['name']; //Добавляем имя к пути   $_row['view'] = "";     //Разруливаем доступы   if($row['access'] == 'inherit') {   $_row['access'] = $access_parent; //Если стоит наследование, делаем как у родителя   } else {   $_row['access'] = (in_array($row['access'], $groups)) ? 'allow' : 'deny';   }   $array[$row['uid']] = $_row; //Результирующий массив индексируемый по uid     //Для быстрой выборки по level, формируем индекс   $array_idx_lvl[$level][$row['uid']] = $row['uid'];     //Строка обработана, теперь запустим эту же функцию для текущего uid, то есть   //пойдёт обратотка дочерней строки (у которой этот uid является pid-ом)   recursive($data, $row['uid'], $level + 1, $_row['path'], $_row['access']);   }   }  }  recursive($table); //Запускаем  

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

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

2. Результирующий массив теперь формируется не по порядку, начиная с нуля а с привязкой к uid — $array[$row[‘uid’]] = $_row;. В данном случае это ни как не влияет на работу скрипта, но возможность обращаться к строке по индексу, а не перебором в цикле потребуется нам в дальнейшем, когда будем разбирать проход по дереву в обратную сторону.

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

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

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

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

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

Приступим:

//Функция прохода вверх по дереву на один уроверь от заданного uid, устанавливает  //свойство видимости себе и родителю в зависимости от доступа или заданной ранее видимости...  function backRecursive($uid, $view = null, $ident = 0)  {   global $array;     //Если поднялись не больше чем на один уровень   if($ident <= 1)   {   //Если видимость уже есть - не меняем текущую строку, иначе   //проверяем доступ и то что пришло от дочки   if($array[$uid]['view'] != 'show')   {   $array[$uid]['view'] = ($array[$uid]['access'] == 'allow' or $view == 'show') ? 'show' : 'hide';   }   backRecursive($array[$uid]['pid'], $array[$uid]['view'], $ident+1);   }  }  

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

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

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

function startBack(){   global $array_idx_lvl;     $levels = array_keys($array_idx_lvl); //получаем массив уровней   $maxLevel = max($levels); //Находим самый глубокий уровень дерева     //Проходимся циклом по каждому уровню начиная с самого большого   for ($i = $maxLevel; $i > 0; $i--) {   $uids = array_keys($array_idx_lvl[$i]);     //На текущем уровне обходим все элементы и по каждому инициируем обработку и движение на 1лвл   foreach ($uids as $uid) {   backRecursive($uid);   }   }  }  

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

А вот и картинка:

image

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

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

Вы можете помочь и перевести немного средств на развитие сайта



itnan.ru

Рекурсия php

Опять же добрый вечер, дорогие читатели. Сегодня поговорим о жестоком, и пугающем всех начинающих, и даже многих не начинающих программистов слове «Рекурсия», и его конкретном применении на практике.
Не знаю почему, но реальной бытовой деятельности программисты привыкли просто обходить рекурсию стороной, заменяя всевозможными циклами и тому подобными средствами.
На самом деле, по моему, это не совсем правильно, и не стоит бояться сложностей с использованием данного метода.
Рекурсия — это использование процедуры или функции (чем бы это ни было) себя самой. Тоесть, в процессе выполнения, исполняемый блок вызывает сам себя.
Понятно что не следует выучив определение пытаться внедрять данный метод везде, где надо и ненадо, его требуется использовать только там где это удобно, дабы не создавать громоздких конструкций теряя память и другие ресурсы.
В своей жизни, на практике, с рекурсией я встречался всего несколько раз, которые убедили меня, в том что это совершенно не сложно, если только задуматься.
В пример приведу многим наверное известную задачу: «Найти факториал числа n», которая прекрасно решается как с помощью рекурсии так и с помощью циклов.
В языке PHP, так же можно использовать рекурсивные алогоритмы, так же как и во многих других языках программирования без особого затруднения. Ниже я приведу примеры для двух сред разработки, именно PHP и Delphi(Pascal), с которыми я уже сталкивался сам.
Пример #1. Вычисление факториала числа в PHP, с помощью рекурсии:

function factorial($n) { // Задаём функцию и используемые ей параметры if(!$n) { return(‘Факториал числа ‘.$n.’ не существует.’); } else { if($n <= 1){ return 1; } // Если $n < или = 1, возвращаем 1 в ответ. return $n * factorial($n-1); // Повторно производим вызов функции } } echo factorial(5); // Запрашиваем факториал числа 5

Всё работает icon smile Рекурсия простым языком. Рекурсия на примерах в PHP, Delphi можете проверить. Ответ 120.

Пример #2. Вычисление факториала числа в PHP, с помощью цикла:

function factorial($n) { if(!$n) { return(‘Факториал числа ‘.$n.’ не существует.’); } else { $otvet= 1; for($i=1; $i <= $n; $i++) { $otvet *= $i; // Сам цикл } return $otvet; // Вывод ответа } } echo factorial(5); // Запрашиваем факториал числа 5

Результат аналогичный.

Пример #3. Вычисление факториала числа в Delphi(Pascal), с помощью рекурсии:

function fact(n:integer):integer; begin if (n < 1) then result := 0 else if (n = 1) then result := 1 else result := n * fact(n — 1); end;

Как использовать думаю догадаетесь icon smile Рекурсия простым языком. Рекурсия на примерах в PHP, Delphi

Пример #4. Вычисление факториала числа в Delphi(Pascal), циклическим способом:

function fact(n:integer):integer; begin var i :integer; if (n < 1) then result := 0 else begin result := 1; for i := 1 to n do result := result * i; end; end;

progerson.ru

Рекурсия php

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

Технически рекурсивные функции ничем не отличаются от обычных. Единственное различие заключается в том, что где-то в коде функции находится вызов ее самой. Например, если вы напишете

function test() {
разные операторы
test();
разные операторы
}
то это и будет рекурсивная функция.

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

Одна из наиболее употребительных применений рекурсивных функций — это обход деревьев, и сегодня мы попробуем разобрать несколько примеров. Первое, что приходит в голову — это вывод многомерного массива. Разумеется, в PHP есть функция print_r(), но мы попробуем сделать результат более красивым и приспособленным для просмотра через браузер.

 function print_array($ar) {
static $count;

$count = (isset($count)) ? ++$count : 0;

$colors = array('#FFCB72', '#FFB072', '#FFE972', '#F1FF72',
     '#92FF69', '#6EF6DA', '#72D9FE');

if ($count > count($colors)) {
echo "Достигнута максимальная глубина погружения!";
$count--;
return;
}

if (!is_array($ar)) {
echo "Passed argument is not an array!<p>";
return; }

echo "<table border=1 cellpadding=0 cellspacing=0 bgcolor=$colors[$count]>";
while(list($k, $v) = each($ar)) {
echo "<tr><td>$k</td><td>$v</td></tr>n";
if (is_array($v)) {
echo "<tr><td> </td><td>";
print_array($v);
echo "</td></tr>n";
}
}
echo "</table>";
$count--;
}

В этой функции используется статическая переменная $count, в которой будет содержаться «глубина погружения» функции — мы будем использовать ее для того, чтобы раскрашивать вложенные массивы в разные цвета, в зависимости от глубины вложенности. Статические переменные сохраняют свое значение при выходе из функции, и использовать их при рекурсии достаточно удобно. Разумеется, с тем же успехом можно было бы передавать переменную $count в качестве параметра, но статические переменные использовать удобнее…

Массив $colors содержит список разных цветов, которые будут использоваться для раскрашивания. Заодно мы его используем для ограничения максимального уровня рекурсии — как только все цвета будут исчерпаны (проверка if ($count >= count($colors)) ), функция будет выводить сообщение о том, что достигнута максимальная глубина.

На всякий случай (кстати, это всегда рекомендуется делать во избежание всяких неприятных последствий) мы проверяем и то, что в качестве аргумента передан именно массив — если это не так, то мы просто выводим сообщение об ошибке и завершаем работу функции:

 if (!is_array($ar)) {
echo "Passed argument is not an array!<p>";
return;
}

Затем мы «открываем» таблицу (echo «<table border=1 cellpadding=0 cellspacing=2>»;) и начинаем последовательно просматривать переданный в качестве аргумента массив. Конструкция

 while(list($k, $v) = each($ar)) {
...
}

является одним из стандартных способов пошагового прохода массива — в каждом проходе цикла переменным $k и $v присваиваются следующие значения индекса (или, как его еще называют, ключа) и значения элемента массива.

Получив пару «ключ-значение», мы выводим ее в строке таблицы:

echo "<tr><td>$k</td><td>$v</td></tr>n";

Обратите внимание, что если значением этого элемента является массив, то будет напечатано слово «array». Теперь мы проверяем, является ли значение массивом:

if (is_array($v)) 

и если да, то печатаем (не до конца!) еще одну строку таблицы, пропуская индекс (он уже есть на предыдущей строке):

echo "<tr><td> </td><td>";

и вызываем нашу функцию печати массива, указывая в качестве аргумента вложенный массив:

print_array($v);

Затем (после того как рекурсивно вызванная функция закончит свою работу) мы «закрываем» строку таблицы (обратите внимание, что, так как наша функция печатает «полную таблицу» — от <table> до </table>, — нам не требуется вложенную таблицу закрывать — функция об этом сама позаботится, — а надо только закрыть ячейку и строку текущей таблицы).

echo "</td></tr>n";

На этом обработка текущей пары «ключ-значение» заканчивается, и цикл while переходит к следующей паре. А когда весь массив пройден, то нам остается только закрыть таблицу:

echo "</table>";

и уменьшить значение глубины

$count--;

Из написанного выше ясно, что наша функция ничего не знает о том, вызвана она рекурсивно или нет, да ей это и безразлично — главное, чтобы в качестве аргумента был передан массив. Точно так же, при вызове самой себя для обработки вложенного массива, ей безразлично, что это рекурсивный вызов — он ничем не отличается от вызова какой-то другой функции. А заботой программиста является гарантия того, что рекурсивным вызовам где-то придет конец, то есть функция сможет закончить работу, не вызывая больше саму себя. Как только это случится, глубина вложенных вызовов начнет уменьшаться, и в конце концов функция «вынырнет на поверхность».

Результат работы подобной функции будет выглядеть примерно следующим образом (в примере максимальная глубина ограничена третьим уровнем, для наглядности добавлен вывод переменной $count, а в качестве массива для распечатки задан массив array(1, array(1.1, 1.2, 1.3), 2, 3, array(3.1, 3.2, array(3.21, 3.22, 3.23, array(3.231, 3.232), 3.24)), 4)

count key value
0 0 1
0 1 Array
0
count key value
1 0 1.1
1 1 1.2
1 2 1.3
0 2 2
0 3 3
0 4 Array
0
count key value
1 0 3.1
1 1 3.2
1 2 Array
1
count key value
2 0 3.21
2 1 3.22
2 2 3.23
2 3 Array
2 Достигнута максимальная глубина погружения!
2 4 3.24
0 5 4

Распечатка массива редко бывает нужна «в реальной жизни», разве что для тестирования своих скриптов, но вот рекурсия может пригодиться довольно часто. Например, более жизненная потребность — обработка всех файлов в директории, включая поддиректории. Скажем, для удаления файлов удобно использовать рекурсивную функцию dd() (сокращение от Directory Delete):

 function dd($file) {
if (file_exists($file)) {
chmod($file,0777);
if (is_dir($file)) {
$handle = opendir($file);
while($filename = readdir($handle))
if ($filename != "." && $filename != "..") dd($file."/".$filename);
closedir($handle);
rmdir($file);
} else {
unlink($file);
}
}
}
Рекурсия php

Работает она по точно такому же принципу — если в качестве аргумента передан файл, то он удаляется (unlink($file);), а если директория — она открывается, последовательно просматривается, и для каждого файла (включая поддиректории) вызывается все та же функция dd()…

Еще одним примером, где рекурсивные функции использовать очень удобно, является чтение файлов по HTTP-протоколу с отслеживанием редиректов — вам надо открыть соединение, запросить файл (или только заголовок) и проверить ответ сервера — если в нем содержится заголовок

Location: xxx

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

Вот, пожалуй, и все. Надеюсь, что использование рекурсивных функций сможет пополнить ваш «арсенал программиста» еще одним мощным орудием…

hostinfo.ru

Данный урок посвящен рекурсии в PHP. Из функции можно вызывать другую функцию. Программа может вызвать функцию f1(), которая вызывает функцию f2(), и т.д. Вызывающая себя функция называется рекурсивной. Такой тип рекурсии называется явной рекурсией. Если функция f1() вызывает другую функцию f2(), которая в свою очередь вызывает функцию f1(), то эти функции также рекурсивные. Такой тип рекурсии называется неявной рекурсией. Очевидно, что возможны более сложные формы неявной рекурсии.

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

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

  • часть 1, которую функция может решить;
  • часть 2, которую функция не может решить.

Для применения рекурсии часть 2 должна быть подобна начальной задаче, но относительно меньше или проще.

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

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

Для завершения рекурсии рекурсивная функция должна образовать последовательность упрощающихся (уменьшающихся) задач, которые приближаются к базисной задаче. Когда, на каком-то шаге рекурсии, функция обнаруживает базисную задачу, она возвращает решение (результат) базисной задачи в предыдущий вызов (предыдущий шаг рекурсии). В этом вызове, в свою очередь, полученный результат объединяется с частью, которую функция может решить. Образовавшееся таким путем решение возвращается на шаг выше, и т.д. Так генерируется последний результат, который возвращается в начальную точку вызова рекурсивной функции. То есть, чтобы был возможен возврат, каждый шаг функции нужно строить таким образом, чтобы он содержал в себе зарезервированное слово return.

Для демонстрации вышеизложенной идеи приведем пример использования рекурсивной функции.

Пример 1. Факториал. Факториал целого неотрицательного числа n равен n*(n-1)*(n-2)*…2*1 и обозначается n!. Принято, что 1!=1 и 0!=1. Например, 7!=7*6*5*4*3*2*1=5040.

Итеративное (нерекурсивное) решение для вычисления факториала таково (файл factorial1.php):

<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Вычисление факториала</h1>
<form action="factorial1.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Вычислить"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Введите натуральное число!<br>";
exit;
}
$f=1;
for($i=$n;$i>=1;$i--)
$f*=$i;
echo "$n!=$f";
?>
</body>
</html>

Пусть f(n)=n!, тогда
f(n)=n!=n*(n-1)!=n*f(n-1),
то есть рекурсивная формула вычисления факториала такова:
f(n)=n*f(n-1).

Пример:
f(5)=5*f(4)=5*4*f(3)=5*4*3*f(2)= 5*4*3*2*f(1)= 5*4*3*2*1=120.

На основе рекурсивной формулы составим рекурсивную функцию для вычисления факториала (файл factorial2.php):

<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Вычисление факториала</h1>
<form action="factorial2.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Вычислить"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Введите натуральное число!<br>";
exit;
}
$f=factorial($n);
echo "$n!=$f";

function factorial($i) {
if($i<2) return 1;
$k=$i*factorial($i-1);
return $k;
}

?>
</body>
</html>

Если в программу ввести число 5, то для вычисления 5! программа действует следующим образом:

Рекурсия php

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

  1. $k=$i* — часть 1, которую функция может решить;
  2. factorial($n-1) – часть 2, которую функция не может решить.

Это действие повторяется до получения базисной задачи, то есть до вызова factorial(1). Если число меньше 2 (1 или 0), то функция factorial() возвращает число 1 ($k=1), то есть решается базисная задача. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции. Там возращенный результат $k умножается на переданный функции параметр $n и присваивается $k. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции и описанный процесс повторяется. Если данный экземпляр функции factorial() был вызван из главной части программы, то $k возвращается в эту часть, где результат выводится на экран и работа программы завершается.

  • < Назад
  • Вперёд >

oftob.ru


You May Also Like

About the Author: admind

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.