Algorytmy

Rekurencja

Co to właściwie oznacza? Jest to procedura która wykonuje samą siebie. To oczywiście nie wiele Tobie mówi. Przypuśćmy więc, że musisz pobrać nazwy wszystkich katalogów i podkatalogów znajdujących się w danej lokalizacji. Wtedy najlepiej jest zastosować rekurencję. Trzeba przy tym być ostrożnym i wiedzieć co się robi gdyż w najlepszym przypadku program może się zapętlić w nieskończoność, a w najgorszym po prostu zawiesi się komputer. Tak więc napiszemy procedurę, która w danym katalogu pobierze nazwy wszystkich innych katalogów. Jeżeli już pobierze np. dwa katalogi, które znajdują się w danej lokalizacji to następnie wywołuje samą siebie tyle, że z innym parametrem - nazwą znalezionego katalogu. Oto przykład:

procedure TMainForm.SearchDir(StartPath: String);
var
  SR:  TSearchRec;
  Found : Integer;
 
  function IsDir(Value : String) : String;
  begin
    if Value[Length(Value)] <> '\' then
      Result := Value + '\' else Result := Value;
  end;
 
begin
  Found := FindFirst(IsDir(StartPath) + '*.*', faDirectory, SR);
  while Found = 0 do
  begin
    Application.ProcessMessages;
    if ((SR.Attr and faDirectory) = faDirectory) and
       ((SR.Name <> '.') and (SR.Name <> '..')) then
    begin
      ListBox1.Items.Add(IsDir(StartPath) + SR.Name);
      SearchDir(IsDir(StartPath) + SR.Name); {<-- w tym miejscu następuje wywołanie 
samej siebie }
    end;
    Found := FindNext(SR);
  end;
  FindClose(SR);
end;


Jak widzisz w tej procedurze (SearchDir) jest zagnieżdżona druga - IsDir.

Sprawdza ona, czy na końcu podanej ścieżki występuje znak \ jeżeli nie - dodaje go. Na początek trzeba wykluczyć pozycję . oraz .. . Jeżeli program znajdzie katalog oznaczony kropkiem lub dwiema kropkami to oznacza, że istnieje katalog wyżej. My w naszym programie pomijamy to - po prostu gdy nazwa znalezionego katalogu jest różna od kropki to idziemy dalej. Następuje dodanie do komponentu ListBox znalezionego katalogu. To co następuje później to właśnie rekurencja - procedura wywołuje samą siebie tyle, że ze zmienionym parametrem StartPath. Jeżeli na przykład początkowy parametr tej procedury to C:\ to ta procedura znajdzie przykładowo na dysku C katalog Moje dokumenty - następuje w tym momencie wywołanie samej siebie tyle, że to parametru początkowego - C:\ zostaje dodany parametr Moje dokumenty i tak na okrągło dopóki zmienna Found nie przybierze wartości 0 - wtedy oznacza to, że nie istnieje żaden katalog niżej.

Oto zastosowanie tego algorytmu, tyle, że w PHP (po drobnej modyfikacji będzie dobrze działać również w Perlu):

   $dirs[] = '';
 
   function FindDir($dir) {
     global $dirs;
 
     chdir($dir);
     $handle = opendir($dir);
     while ($file = readdir($handle)) {
       $dane = split("\.", $file);
       if (($file <> '.') and ($file <> '..') and (strlen($dane[1])) == 0) {
         array_push($dirs, "$dir$file/");
         FindDir("$dir$file/");
       }
     }
     closedir($handle);
   }
 
  FindDir('C:/usr/sfp/www/');


W tym wypadku tablica v zawierać będzie wszystkie ścieżki pod katalogów.

4 komentarze

Twardy 2005-07-02 19:47

Artykul slaby. Nie mowi za duzo o rekurencji. Glownie o problemach i ich omijaniu. A czym jest rekurencja bezposrednia i posrednia?

Deti 2003-08-22 22:04

Witam, właśnie jest mi potrzebne takie coś.. mam tylko takie pytanie.

Katalog 1
Katalog 2
  * jakis podkatalog1
  * jakis podkatalog2
Katalog 3

Jadąc w tej kolejności, czy procka ta uwzględni Katalog 3? Napisane było, że nie uwzględniamy kropki ".", czyli... ? że nie? Gdzie mogę znajść pełną procedure na wyszukanie wszystkich plików i podkatalogów w danym katalogu /?

jas_dream 2003-06-24 15:30

Zbytnio nie widze zastosowania procedury, ale nie jest zła

brodny 2003-05-07 09:18

Powiem tylko tyle: to jest poryte ;)