[о рекурсивных функциях в PHP]материал подготовил: Дмитрий Турецкий 28.04.2004
большинство языков программирования поддерживает рекурсивные функции, то есть такие, которые вызывают сами себя. Это весьма мощный инструмент, позволяющий создавать довольно изящные и функциональные программы, но вот используется он достаточно редко – по всей видимости, из-за его сложности для начинающих программистов и умения вызывать неприятные ошибки. Поэтому в сегодняшней заметке мы поговорим о создании и использовании рекурсивных функций в PHP.
Технически рекурсивные функции ничем не отличаются от обычных. Единственное различие заключается в том, что где-то в коде функции находится вызов ее самой. Например, если вы напишете
function test() { разные операторы test(); разные операторы } то это и будет рекурсивная функция.
Основная сложность при работе с рекурсивными функциями заключается в том, что их достаточно легко зациклить – для того чтобы этого не происходило, вам надо очень тщательно следить за возможностью выхода из функции без рекурсивного вызова, иначе функция начнет “бесконечно” вызывать сама себя и быстро исчерпает ресурсы компьютера.
Одна из наиболее употребительных применений рекурсивных функций – это обход деревьев, и сегодня мы попробуем разобрать несколько примеров. Первое, что приходит в голову – это вывод многомерного массива. Разумеется, в PHP есть функция print_r(), но мы попробуем сделать результат более красивым и приспособленным для просмотра через браузер.
В этой функции используется статическая переменная $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); } } }
Работает она по точно такому же принципу – если в качестве аргумента передан файл, то он удаляется (unlink($file);), а если директория – она открывается, последовательно просматривается, и для каждого файла (включая поддиректории) вызывается все та же функция dd()…
Еще одним примером, где рекурсивные функции использовать очень удобно, является чтение файлов по HTTP-протоколу с отслеживанием редиректов – вам надо открыть соединение, запросить файл (или только заголовок) и проверить ответ сервера – если в нем содержится заголовок
Location: xxx
то надо соединение закрыть и снова вызвать функцию чтения файла, но уже с новым адресом. Написание такой функции можно предложить в качестве “домашнего задания”, но учтите, что к ней надо подходить осторожно – следует обязательно сохранять список всех редиректов (удобно использовать для этого статичный массив) и сравнивать а
