Прочитав заголовок, ты, возможно, отмахнешься от этой статьи, подумав – какой прок от рекурсии, что нам преподавали на скучных уроках информатики. Причем, смысл рекурсивных процедур сводился к нахождению факториала и прочих математических вещей.
Если подумать, легко найти множество применений рекурсии, с которыми может столкнуться практически любой программер. Рассмотрим конкретный пример.
1. От малого до великого.
Представим себе, что нам дана некоторая ветка каталогов, которую нужно просмотреть рекурсивно. Пусть это будет обычный логический диск c:\ со всеми подкаталогами. Решить подобную задачу можно несколькими способами, даже не прибегая к рекурсивной процедуре.
Например, в пингвине (да и вообще в *nix-like системах) данный прием реализуется такими командами, как:
# find .
# ls –R1
и прочими. В Windows подобный трюк реализуется через обычный dir с парой параметров:
> dir /S /B c:\
Но использовать системные команды занятие не для опытного программиста. Стремясь к созданию универсального проекта, программер обязательно будет использовать рекурсивную процедуру, которая выполнит вышеописанный алгоритм пластичнее и, быть может, быстрее.
Вот мой пример подобной процедурки. Программа берет первый аргумент командной строки в качестве каталога и рекурсивно обрабатывает вложенные директории. Ничего хитрого.
#!/usr/bin/perl
rls($ARGV[0]); ## Выполняем рекурсивную процедуру rls() с параметром аргумента командной строки.
sub rls {
my $dir=shift; ## Локализуем переменную $dir, которая была взята в качестве параметра процедуры
rls().
my(@files); ## Локализуем массив, в котором будут содержаться файлы текущего каталога.
$dir=~s/\\/\//g; ## Заменяем символ ‘\’ на ‘/’ (только ради красоты и стандарта).
chdir("$dir"); ## Переходим в каталог.
opendir(DIR,"."); ## Открываем директорию для чтения.
@files=readdir(DIR); ## Все файлы помещаем в массив
@files.
foreach (@files) { ## Перебираем элементы в цикле.
unless ($_ eq '..' || $_ eq '.') { ## Игнорируем текущую директорию и родительский каталог.
if (-d "$dir$_") { ## Если элемент является каталогом...
print "Dir: $dir$_\n"; ## Напишем, что это директория.
rls("$dir$_/"); ## И вызываем rls() уже для вложенной папки.
chdir(".."); ## После этого переходим на каталог выше (внутри уже все просмотрено.
} else {
print "File: $dir$_\n"; ## Если это файл – просто сообщим об этом.
}
}
}
}
Ничего сложного, правда? Следует лишь подчеркнуть важность локализации массива @files (в противном случае рекурсия будет работать один раз).
Зачем было переходить в заданные каталоги, если их можно просто открыть для чтения? Ответ на этот вопрос ты найдешь далее.
2. Сетевая рекурсия.
Возьмем пример посложнее. Допустим, мне понадобилось проиндексировать некий ftp-сервер. То есть залогиниться на него, пролистать все каталоги и выделить из них файлы (неважно зачем). Переделать вышеописанную программу для этого алгоритма становится очень просто. Во-первых, для соединения будет использован популярный perl-модуль Net::FTP, входящий в комплект libnet
(http://perl.com/CPAN). Во-вторых, локальный chdir() будет заменен на эквивалентный метод $self->chdir(). В итоге программа преобразовывается в иной вид.
#!/usr/bin/perl
use Net::FTP; ## Используем
Net::FTP.
new Net::FTP(“ftp.server.ru”); ## Вызываем конструктор
new.
$ftp->login("login","password"); ## Логинимся на FTP-сервер.
$ftp->binary(); ## Переключаемся в бинарный режим.
$ftp->cwd("/"); ## Уходим в корень (впрочем, сюда можно подставить любой каталог).
rls(“/”); ## Вызываем процедуру rls() для корня
$ftp->quit; ## И дисконнектимся с сервера.
}
sub rls {
my $dir = shift;
my (@files); ## Начало не изменяем.
$ftp->cwd(“$dir”); ## Переходим в каталог (действуем аналогично локальному алгоритму).
@files = $ftp->dir(); ## Получаем список файлов.
foreach (@files) { ## Перебираем элементы в цикле.
unless ($_ eq '..' || $_ eq '.') { ## Игнорируем текущую директорию и родительский каталог.
$type = parse(“$_”); ## Вызовем процедуру для парсинга вывода
$ftp->dir()
if ($type) {
print "Dir: $dir$_\n"; ## Напишем, что это директория.
rls("$dir$_/"); ## И вызываем rls() уже для вложенной папки.
$ftp->cdup(); ## Перемещаемся назад.
} else {
"File: $dir$_\n"; ## Если это файл – просто сообщим об этом.
}
}
}
}
Как видишь, после нехитрой модификации кода, программа стала работать.
3. Слово о модулях.
На самом деле мы изобрели велосипед. Потому как существует замечательный модуль Net::FTP::Recursive, помогающий сделать рекурсию в несколько строк. В его основу входит работа с FileHandle. То есть, создается переменная-дескриптор, в который будет записан вывод Net::FTP. Реализуется это всего в несколько строк.
#!/usr/bin/perl
use Net::FTP::Recursive;
use FileHandle; ## Используем модули, о которых я сказал выше.
$host = shift;
$username = shift;
$passwd = shift;
$remote_path = shift;
$filename = shift; ## Берем 5 параметров из командной строки (хост, логин, пароль, директорию-начало и имя файла, в который будет записан вывод).
$fh = new FileHandle;
$fh->open(">$filename"); ## Создаем новый дескриптор и “привязываем” его к файлу.
select $fh;
$| = 1;
select STDOUT; ## Вырубаем буферизацию и включаем бинарный поток на
STDOUT.
$ftp = Net::FTP::Recursive->new($host, Debug => 1,FilenameOnly => 1); ## Создаем новый метод модуля рекурсии. В параметрах укажем Debug и вывод только имен файлов (без каталогов).
$ftp->login($username, $passwd);
$ftp->binary(); ## Логинимся на сервер и переключаемся в бинарный режим.
$ftp->cwd($remote_path); ## Переходим в начальный каталог.
$ftp->rdir( Filehandle => $fh ); ## И вызываем процедуру rdir(), входящую в модуль (в качестве параметров выступает дескриптор).
$fh->close; ## Закроем файл.
$ftp->quit; ## И завершим соединение.
Вот, собственно, и вся программа. Модуль содержит не только эту процедуру, а также rput(), rget() и rls(). Об их назначениях ты можешь прочитать, если заюзаешь команду perldoc Net::FTP::Recursive.
А теперь внимание! Все вышеописанные сетевые проекты нуждаются в доработке на предмет исключения. Например, если вход в каталог будет невозможен (по какой-либо причине), вся рекурсия сойдет на нет. Поэтому следует добавлять “|| return” к методам объекта (или что-либо подобное).
5. И в заключение...
Вот и все. Теперь ты понимаешь, что рекурсия может быть очень полезной для составления каких-либо проектов. Можно придумать ряд других “жизненно важных” алгоритмов, которые проще реализовать с помощью рекурсии. Поэтому, всегда важно знать, как выполняется такая реализация. А когда рекурсию совмещают с тредами, результат превосходит все ожидания. Не веришь? Попробуй сам ;).
