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.