Построение дерева категорий на PHP. Рекурсия. Уроки PHP. Рекурсия Рекурсивная функция php

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

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

Привожу код функции:

function xss($data) {
if (is_array($data)) { // Если это массив
$result = array(); // Создаём новый массив
foreach ($data as $key => $value) { // Перебираем исходный массив
$result[$key] = xss($value); // Рекурсивно вызываем функцию xss
}
return $result; // Возвращаемый "защищённый" массив
}
return htmlspecialchars($data, ENT_QUOTES); // Если это не массив, то вызываем htmlspecialchars()
}
$data = xss($_REQUEST); // Пример вызова функции
?>

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

1. Если входящие данные - это НЕ массив, то просто вызываем функцию htmlspecialchars() .
2. Если входящие данные - это массив, то перебираем все элементы массива и для каждого вызываем эту же функцию. А дальше возвращаемся к пункту 1 .

Я понимаю, что для новичков рекурсия в PHP - это достаточно сложная вещь, но я рекомендую прямо пройтись по коду, как будто Вы интерпритатор PHP . Тогда станет всё яснее.

Данный урок посвящен рекурсии в 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):

Вычисление факториала

Адади натурали (n>=0):

";
exit;
}
$f=1;
for($i=$n;$i>=1;$i--)
$f*=$i;
echo "$n!=$f";
?>

Пусть 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):

Вычисление факториала

Адади натурали (n>=0):

if(!isset($_GET["n"]) || ($n = $_GET["n"])=="") {
echo "Введите натуральное число!
";
exit;
}
$f=factorial($n);
echo "$n!=$f";

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

?>

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

При первом вызове функции 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 возвращается в эту часть, где результат выводится на экран и работа программы завершается.

Большинство языков программирования поддерживает рекурсивные функции, то есть такие, которые вызывают сами себя. Это весьма мощный инструмент, позволяющий создавать довольно изящные и функциональные программы, но вот используется он достаточно редко — по всей видимости, из-за его сложности для начинающих программистов и умения вызывать неприятные ошибки. Поэтому в сегодняшней заметке мы поговорим о создании и использовании рекурсивных функций в 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)) {

";
return; }

echo "

";
echo "\n";
if (is_array($v)) {
echo "\n";
}
}
echo "

$k	$v
	"; print_array($v); echo "

";
$count--;
}

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

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

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

If (!is_array($ar)) {
echo "Passed argument is not an array!

";
return;
}

Затем мы "открываем" таблицу (echo "

";) и начинаем последовательно просматривать переданный в качестве аргумента массив. Конструкция

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

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

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

Echo "

\n";
Обратите внимание, что если значением этого элемента является массив, то будет напечатано слово «array». Теперь мы проверяем, является ли значение массивом:
if (is_array($v))
и если да, то печатаем (не до конца!) еще одну строку таблицы, пропуская индекс (он уже есть на предыдущей строке):
echo "\n";
На этом обработка текущей пары "ключ-значение" заканчивается, и цикл while переходит к следующей паре. А когда весь массив пройден, то нам остается только закрыть таблицу:
echo "

$k

$v

"; и вызываем нашу функцию печати массива, указывая в качестве аргумента вложенный массив: print_array($v); Затем (после того как рекурсивно вызванная функция закончит свою работу) мы "закрываем" строку таблицы (обратите внимание, что, так как наша функция печатает "полную таблицу" — от до , — нам не требуется вложенную таблицу закрывать — функция об этом сама позаботится, — а надо только закрыть ячейку и строку текущей таблицы). echo "

";
и уменьшить значение глубины
$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

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);
}
}
}

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

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

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

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