Форум программистов [Powered by Invision Power Board]

Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.

Плюс рекурсии – простота алгоритма, а так же лаконичность кода. Для примера рассмотрим алгоритм выхода из лабиринта, заданного прямоугольной матрицей, где 1 – стена, 0 – свободное место, 2 – выход.
Алгоритм простейший:

Код

1.    если ты находишься на двойке – ты вышел
2.    если ты не находишься на 1, делай следующее:
2.1    встань на клетку правее тебя и запусти процедуру поиска ещё раз.
2.2    встань на клетку левее тебя и запусти процедуру поиска ещё раз.
2.3    встань на клетку выше тебя и запусти процедуру поиска ещё раз.
2.4    встань на клетку ниже тебя и запусти процедуру поиска ещё раз.
3.    завершаем процедуру

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

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

Код

#!/usr/bin/perl
open PL,'>file_list.txt' or die "file pl.txt not open"; # открываем файл в который будем складывать найденные файлы

read_dir("/home"); # вызываем процедуру поиска файлов передаём ей первую, корневую, папку для поиска

sub read_dir(){
    my $n;
    local *dr; # объявляем локальные переменные
    my $name= shift @_; # получаем имя директории для поиска
    opendir dr, $name; # открываем директорию на чтение
    while ($n=readdir(dr)) # читаем директорию по одной записи и обрабатываем их ниже
        {
        if (-f "$name/$n") # если данному имени соответствует файл
            {
            $t="$name/$n\n";
            print PL "$t";# пишем файл в наш лист
            }
        elsif ( ($n ne '.')and($n ne '..'))# если текущая запись не файл и не спец. символы .. и . , то запускаем эту же процедуру.
            {
            read_dir("$name/$n");
            }
        }
        closedir dr; # закрываем директорию
    }
close PL; # закрываем полученный список файлов

А теперь рассмотрим как можно преобразовать данный алгоритм в линейный. Обратимся к сути алгоритма: нам нужно по очереди читать записи из текущей директории и искать в под директориях новые папки.
Значит можно очередную найденную папку просто добавить в некий список, очередь, вместо того чтобы вызывать для него процедуру:

Код

#!/usr/bin/perl
@dir=("/home"); # очередь директорий, пока содержит только "корневую" директорию для поиска
open PL,'>list.txt' or die "file pl.txt not open"; # открываем файл в который будем складывать найденные файлы

while ($name= shift @dir) # пока в очереде есть хоть одна директория производить поиск
    {
    opendir dr, $name; # окрываем текущую директорию на чтение
    while ($n=readdir(dr)) # читаем её содержимое
        {
        if (-f "$name/$n") #  если текущая запись файл
            {
            $t="$name/$n\n";
            print PL "$t";# пишем файл в наш лист
            }
         elsif ( ($n ne '.')and($n ne '..')) # если текущая запись не файл и не спец. символы .. и .
            {
             push @dir,"$name/$n"; # добавляем директорию в очередь
            }
        }
        closedir dr; # закрываем текущую директорию
    }
close PL; # закрываем полученный список файлов

Отдельное спасибо участнику dimes за ошибку найденную в коде примеров.
P.S. В этой статье я хотел показать, что собой представляют рекурсивные алгоритмы и как их можно заменить линейными.