ALG9

Rozdział 2

Rekurencja

Tematem niniejszego rozdziału jest jeden z najważniejszych mechanizmów używanych w informatyce - rekurencja, zwana również rekursją^{1 2}. Mimo iż użycie rckurencji nie jest obowiązkowe, jej zalety są oczywiste dla każdego, kto choć raz spróbował tego stylu programowania. Wbrew pozorom nic jest to wcale mechanizm prosty i w iele jego aspektów wymaga dogłębnej analizy.

Niniejszy rozdział ma kluczowe znaczenie dla pozostałej części książki - o ile jej lektura może być dość swobodna i nieograniczona naturalną kolejnością rozdziałów, o tyle bez dobrego zrozumienia samej istoty rekurencji nie będzie możliwe swobodne „czytanie” wielu zaprezentowanych dalej algorytmów i metod programowania.

2.1. Definicja rekurencji

Pojęcie rekurencji poznamy na przykładzie. Wyobraźmy sobie małe dziecko w wieku lat - przykładowo - pięciu. Dostaje ono od rodziców zadanie zebrania do pudelka wszystkich drewnianych klocków, które „nicrozmyślnie” zostały rozsypane na podłodze. Klocki są bardzo prymitywne, są to zwyczajne drewniane sześcianiki. które doskonale nadają się do budowania nieskomplikowanych budowli. Polecenie jest bardzo proste: „Zbierz to wszystko razem i poukładaj tak jak było w pudełku”. Problem wyrażony w ten sposób jest dla dziecka

1

   Subtelna różnica między tymi pojęciami w zasadzie już się zatraciła w literaturze, dlatego też nie będziemy się niepotrzebnie rozdrabniać w szczegóły terminologiczne.

2

   Programy zapisane w formie rekurencyjnej mogą być przekształcone - z mniejszym lub większym wysiłkiem - na postać klasyczną, zwaną dalej iteracyjną (patrz rozuział 6).