Turbo Pascal - Programowanie Wszystko o Turbo Pascalu
Obszerny download i wiele kodów źródłowych
Menu
Kurs
Pozostałe


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('
') 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.

Źródło: 4programmers.net.

Dodano: 2007-05-18

Twoja ocena:

 

Ocena:

[powrót]

Największy zbiór informacji o Turbo Pascalu
Copyright © 2007 by rafael. All rights reserved. : Hosting zapewnia: programuj.com turbopascal.programuj.com - programowanie najlepsze kursy w sieci unikatowe artykuły za darmo Borland Turbo Pascal 7.0