Рекурсивные функции в языке 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)

Распечатка массива редко бывает нужна «в реальной жизни», разве что для тестирования своих скриптов, но вот рекурсия может пригодиться довольно часто. Например, более жизненная потребность — обработка всех файлов в директории, включая поддиректории. Скажем, для удаления файлов удобно использовать рекурсивную функцию 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-протоколу с отслеживанием редиректов — вам надо открыть соединение, запросить файл (или только заголовок) и проверить ответ сервера — если в нем содержится заголовок

Location: xxx

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

Алексей Волков