Rekurencja

Rekurencja boli. Nie jest to rzecz łatwa do zastosowania, a jeszcze trudniejsza
do zrozumienia. Błędy w warunkach zakończenia pętli rekurencji są trudne do
znalezienia, a i debugowanie samego kodu może spowodować potrzebę kupna nowej
klawiatury.

Po tym zachęcającym wstępie: więc co to ta rekurencja i po co ją używać,
skoro taka trudna? Najpierw po co. Więc o ile wiele rzeczy można załatwić
iterowaniem (for, while, repeat & synowie), to są takie rzeczy, których się w ten
sposób zrobić nie da, bądź zrobienie jest bezsensownie trudne. Na przykład
przejechanie się po wszystkich plikach i podkatalogach w zadanym katalogu...
ale o tym zaraz.

Teraz definicja: górnolotnie: jest to taki proces, gdy kawałek kodu programu
wywołuje samego siebie. Innymi słowy, masz jakąś procedurę tudzież funkcję,
a w jej wnętrzu - w jej kodzie - masz wywołanie jej samej. Może jakiś przykład:

procedure rek1;
begin
  rek1
end;

begin
  rek1
end.

No i fajnie. Jak uruchomisz ten kawałek kodu, to momentalnie TP wysypie Ci się
z błędem przepełnienia stosu :) No tak, bo zrobiła się nieskończona pętla - każde
uruchomienie procedury rek1 uruchamia jej kopię, kopia uruchamia następną... i tak
w nieskończoność, w praktyce do momentu, kiedy nie skończy się miejsce na stosie
(stąd ten błąd). Wniosek: rekurencja kiedyś się musi skończyć! W kodzie muszą być
warunki, które pozwolą na zakończenie rekurowania.

var
  i : integer;

procedure rek2;
begin
  if i = 10 then exit else inc(i);
  rek2
end;

begin
  i := 0;
  rek2
end.

Taki kod jest w zasadzie równoważny pętli for i := 0 to 10 do rek2, i jako
taki nie ma sensu - chodzi tylko o pokazanie, jak zatrzymać pętlę rekurencji.

Musisz pamiętać, że jak zatrzymasz jedną "instancję" (poziom) kodu, to wszystkie
te, które były odpalone wcześniej, dalej takowe będą, więc warunki zakończenia
pętli muszą być na tyle sprytne, żeby po jakimś czasie wyjść z całej pętli,
a nie tylko jej części. W tym przykładnie, jeśli i = 10, to po kolei będą się
kończyć wszystkie instancje rekurencji, jako iż procedura rek2 jest wywoływana
tylko raz wewnątrz niej samej. Nieco zabawniej by było, gdyby dorzucić jeszcze
jedną zmienną - j - i wywoływać rek2 w pętli for j := 0 to i do rek2... Jesteś
w stanie przewidzieć, co się stanie? Pewnie nie, i to jest właśnie wadą
rekurencji: niełatwo zrozumieć, o co w kodzie chodzi, i łatwo się pomylić.
Ale przejdźmy do praktyki. Wyobraź sobie program przeszukujący zadany katalog
(razem z podkatalogami!) w poszukiwaniu jakiegoś pliku. Jak można zrobić coś
takiego iteracyjnie, kiedy nie wiadomo, jak głęboko sięga drzewo katalogów?
Ja swojego czasu próbowałem z dziesięcioma identycznymi procedurami, każdą
obsługującą odpowiednie 'piętro' podkatalogów, ale było to wyjątkowo
nieeleganckie rozwiązanie (aczkolwiek można to zrobić inaczej, ładniej i krócej,
no i iteracyjnie, ale to wymaga niezłego rzeźbienia w kodzie). Więc oto coś
eleganckiego.
Potrzebujemy wejść do każdego podkatalogu naszego katalogu, i każdego
podkatalogu tych podkatalogów itp itd, i w każdym z nich należy sprawdzić,
czy nie ma tam szukanego pliku. Struktura procedury, która to zrobi, narzuca
się sama: przeszukujemy katalog, jeśli trafimy na katalog, to wchodzimy do niego
i wywołujemy kolejną instancję procedurki, jeśli na plik - to sprawdzamy,
czy zgadza się on ze wzorcem; jeśli katalog został przeszukany, to wychodzimy
z niego piętro wyżej i wychodzimy z procedury (też piętro wyżej).

Ze szczegółów technicznych: korzystamy z modułu DOS, procedur ChDir do
wchodzenia/wychodzenia z katalogu, FindFirst/FindNext do przeszukiwania
jego zawartości, oraz typu SearchRec.

uses dos;
const
  maska : string = '*.*';

procedure writename(const SR : searchrec);
begin
with sr do
begin
  write(name:14);
  if sr.attr and $10 < 0 then write('   <dir>   ') else   write(size:9,'  ');
  {tu jakies bonusy}
    writeln;
  end;
end;

procedure Dir;
var
  SR : SearchRec;
begin
  {katalog przeszukujemy dwa razy; može nie jest to optymalna
   metoda, ale na pewno prosta}
  FindFirst(maska,$3F,SR); {najpierw przeszukujemy wszystkie nazwy}
  while DosError = 0 do    {dopóki coś znajdowane, powtarzaj pętlę}
  begin
    writename(SR);
    FindNext(SR);
  end;

  FindFirst('*.*',$3F,SR); {potem jedziemy po katalogach - wszystkich}
  while DosError = 0 do
  begin
    if (SR.Attr and $10 < 0) and (SR.Name < '.') and (SR.Name < '..') then
    begin
      ChDir(SR.Name);
      Dir;             {<--- sedno rekurencji}
      ChDir('..');
    end;

    FindNext(SR);
  end;
end;

begin
  writeln('Program wyszukuje podany plik w biežĄcym katalogu');
  write('Podaj jego nazwŠ (ze znakami * i ?): '); readln(maska);
  if maska = '' then maska := '*.*';
  Dir;
end.

W zasadzie da się zrozumieć, prawda? Trzeba pamiętać, że każda nowa
instancja procedury ma swoje własne zmienne lokalne, więc zmiana SR
w jednym poziomie wywołań funkcji nie spowoduje zmiany - wydawałoby się
tej samej - zmiennej z procedury z piętra niżej.

Zaprezentowany kod po minimalnych przeróbkach może służyć do usuwania,
kopiowania, przenoszenia całego drzewa katalogów, do zliczania miejsca
zajętego przez pliki w zadanym podkatalogu... w zasadzie jest to szkielet
do wszystkich operacji dotyczących całych drzewek katalogów.

Miłej zabawy.

Kod źródłowy przykładowego programu znajduje się tutaj.