Zrozumieć rekurencję

Jak wiadomo temat ten jest prawdziwą zgrozą dla początkujących programistów ale mam nadzieję, że po przeczytaniu tego artykułu wiele rzeczy stanie się jasne. Zaczniemy od wyjaśnienia tegoż pojęcia...

.. a najłatwiej to zrobić na najbardziej banalnych przykładach, bowiem w prostocie tkwi potęga. Aby zrozumieć to, o czym tu mówimy - zróbmy taki eksperyment. Otóż patrząc na jakiś program z poziomu kodu, wyobrażamy sobie ciąg czynności jakie po sobie następują - są to kolejne linie kodu, które po kolei się wykonują - jak na poniższym schemacie:

Instrukcja 1;
Instrukcja 2;
Instrukcja 3;

// itd.

Czasem potrzeba jest wykonania pewnych czynności określoną ilość razy - wtedy korzystamy z pętli. Jednak z biegiem czasu okazuje się, że już nam one nie wystarczają - ponieważ zaistniała sytuacja gdy musimy w danym kroku pętli - wykonać inne polecenia. Wtedy przychodzą na myśl pętle zagnieżdżone, gdzie mamy już większe pole manewru. Jednak i to później nie wystarcza. Pętle zagnieżdżone są dobrym rozwiązaniem pod warunkiem, że znamy ich ilość. Mówiąc przykładowo: chcąc pobrać listę wszystkich plików i katalogów z dysku - nie jesteśmy w stanie zrobić tego za pomocą znanych pętli (for, repeat..until, while..do). Owszem - mielibyśmy taką możliwość - gdyby była z góry określona maksymalna długość ścieżki, np. tylko do drugiego podkatalogu. Jednak jest to niewiadoma - nie wiemy ile katalogów ma dany katalog - i czy te mają kolejne. Tu właśnie z pomocą przychodzi omawiana rekurencja. Można sobie ją wyobrazić jako swoisty "konstruktor pętli" - co oczywiście jest pojęciem czysto "wyobrażeniowym", gdyż jak wiemy pętla
nie jest żadnym obiektem, tym bardziej nie może posiadać konstruktora - jest jedynie elementem języka Object Pascal.

Ale starczy już tych nudnych teorii, ale jakże niezbędnych. Najpierw należy uświadomić sobie pewien fakt (co jednak dla znacznej większości czytających jest pewnie oczywiste, jednak muszę o tym wspomnieć).

Przeanalizujmy taki oto fragment kodu:

procedure Test;
begin
  ShowMessage('1');
  Test2;
  ShowMessage('3');
end;

procedure Test2;
begin
  ShowMessage('2');
end;

Sam kod jest oczywiście zbyt banalny aby go omawiać krok po kroku - jednak napisałem go tu, aby uświadomić pewną istotną rzecz. Mianowicie - co zobaczymy po uruchomieniu programu? Oczywiście kolejne message: 1, 2, 3... Nasuwa się pewnie pytanie: i co z tego? - przecież to oczywiste! - a jednak nie. Ważny jest fakt wystąpienia instrukcji ShowMessage('3'), która widnieje pod wywołaniem innej procedury. Mimo tego, że omawiam tu najprostsze przykłady, wiele osób zapomina, że kod po zakończeniu procedury dalej jest wykonywany w procedurze, z której został wywołany. Tym właśnie głupim błędem nawet zaawansowani programiści robią pomyłki, zwalniając na przykład kilka razy zasoby - przez co powstają błedy naruszenia pamięci (Acces Violation). Ale jak to się mówi - lećmy dalej..

W przykładzie tym wywołaliśmy procedure Test2. A dlaczego by nie wywołać procedury samej z siebie? Brzmi to trochę głupio, albo i groźnie - jednak jak zaraz się przekonamy tak nie jest.

Spójrzmy na taki kod:

procedure ZawiesProgram;
begin
ZawiesProgram;
end;

Jest to chyba najbardziej prymitywny przykład rekurencji - jednak całkowicie bezużyteczny, gdyż po pierwsze - nie wykorzystuje on wspomnianego wyżej aspektu, a po drugie - zawiesza program. Jego działanie na siłę można porównać z nieskończoną pętlą. Przeanalizujmy go - chociaż nie ma co tu dużo analizować - jedna linijka kodu. Zatem jest ona natychmiast wywoływana - i co dalej? - znowu to samo.. i dalej.. i dalej - i tak w nieskończoność.

Aby bardziej użytecznie wywoływać procedurę samą z siebie, przeanalizujmy taki przykład. Postaw na formę dowolnego Buttona, będzie on wywoływał naszą procedurę...

procedure TForm1.Button1Click(Sender: TObject);
begin
  RekTest(True);
end;

A samą procedurę RekTest (z jednym parametrem typu Boolean) zapisz tak:

procedure TForm1.RekTest(Check: Boolean);
begin
  if Check then
  begin
    i := 0;
    RekTest(False);
    if i = 1 then ShowMessage('Co jest grane?');
  end
  else
  i := 1;
end;

I pytanie brzmi .. czy na ekranie wyświetli się napis 'Co jest grane?'... Na pierwszy rzut oka widać, że jednak nie - przypisujemy przecież do zmiennej "i" wartość równą zero, później sprawdzenie- oczywiście warunek niespełniony. Jednak zapominamy o samoistnym wywołaniu: RekTest(False), który istotnie zmienia wartość zmiennej "i". I tu właśnie można zobaczyć w akcji działanie tego, o czym mówiłem wcześniej. Gdyby nie to - rekurencja nie miała by najmniejszego sensu użycia. Napis wyświetli się - jeśli nie wierzycie - sami zobaczcie na swoim komputerze. Przeanalizujmy program krok po kroku:

1. Wywołuję procedurę RekTest z parametrem True (przez kliknięcie na Button)

2. W pierwszej linii RekTest procedura sprawdza stan parametru Check. Ponieważ ma on wartość True (gdyż tak ustawiliśmy parametr), wykonują się kolejne 3 linie pomiędzy begin i end.

3. Następuje zmiana wartości zmiennej "i" na zero.

4. Wywołanie procedury RekTest - tym razem z parametrem wartości False. Zapamiętaj to miejsce!

   1. Rozpoczyna się nowe wywołanie procedury z punktu 4.
   2. Znowu sprawdzenie parametru Check - tym razem jest on ustawiony na False, zatem wykonuje się kod: " i := 1".
   3. Następuje koniec wywołania procedury - ale czy to koniec? - Nie! - ponieważ tak jak wcześniej było mówione - wracamy w poprzednie wywołanie...

5. Spójrzmy na punkt 4 - wywołaliśmy tam procedurę RekTest - wyobraźcie sobie, że wywołujemy inną, dowolną procedurę - zatem dalszy kod jest wywoływany - tak samo jest i tu.

6. if i = 1 then ShowMessage('Co jest grane?');, a zmienna "i" jest przecież równa 1 bo tak się stało.

7. Koniec.

Mam nadzieję, że dzięki tym 10-ciu punktom zrozumieliście istotę rekurencji. Spójrzcie teraz jak zapisałem punkty 5, 6, 7 -są one wcięte - należą jak gdyby do punktu "4" - gdzie nastąpiło wywołanie procedury. Ważne jest również rozumienie parametru Check, typu Boolean - który w naszym przypadku został użyty aby nie zawiesić programu nieskończoną rekurencją. Zauważ jednak, że komputer nie zapomina wartości parametru wywołania nadrzędnego, pomimo tej samej nazwy (zresztą nie tyle nazwy - w końcu jest to ten sam parametr w kodzie). Mam nadzieję, że po przeczytaniu moich wypocin choć trochę wyjaśniło ci się działanie rekurencji. W razie problemów - zawsze można do mnie pisać.. [ przedtem się przedstawiając oczywiście ].

( Nazwa artykułu zapożyczona z myśli Dryobatesa "Zrozumieć komputer" - mam nadzieję, że nie ma tego za złe :)