ALG8

2.5.1.Stąd do wieczności

W wielu funkcjach rekurencyjnych, pozornie dobrze skonstruowanych, może z łatwością ukryć się błąd polegający na sprowokowaniu nieskończonej ilości wywołań rekurencyjnych. Taki właśnie zwodniczy przykład jest przedstawiony poniżej:

std.cpp

int SLadDofr/iecznosci(int n)

if <n— 1) return 1; else

if ((n %2) == 0)    // czy n jest parzyste?

return StadDoWiecznosci(n-2)*n;

else

return StadDoWiecznosci(n-1)*n;

J

Gdzie jest umiejscowiony problem? Patrząc na ten program trudno dopatrzyć się szczególnych niebezpieczeństw. W istocie, definicja rekurencyjna wydaje się poprawna: mamy przypadek elementarny kończący łańcuch wywołań, problem o rozmiarze n jest upraszczany do problemu o rozmiarze n-1 lub n-2. Pułapka tkwi właśnie w tej naiwnej wierze, że proces upraszczania doprowadzi do przypadku elementarnego (czyli do «-/)! Po dokładniejszej analizie można wszakże zauważyć, że dla n>2 wszystkie wywołania rekurencyjne kończą się parzystą wartością n. Implikuje to, iż w końcu dojdziemy do przypadku n=2, który zostanie zredukowany do n=(), który zostanie zredukowany do n=-2. który... Można tak kontynuować w nieskończoność, nigdzie „po drodze" nie ma żadnego przypadku elementarnego!

Wniosek nasuwa się sam: należy zwracać baczną uwagę na to, czy dla wartości parametrów wejściowych należących do dziedziny wartości, które mogą być użyte, rekurencja się kiedyś kończy.

2.5.2.Definicja poprawna, ale...

Rozpatrywany poprzednio przykład służył do zilustrowania problemów związanych ze zbieżnością procesu rekurencyjnego. Wydaje się, że dysponując poprawną definicją rekurencyjną, dostarczoną przez matematyka, możemy już być spokojni o to, że analogiczny program rekurencyjny także będzie poprawny (tzn. nie zapętli się, będzie dostarczać oczekiwane wyniki etc.). Niestety jest to wiara dość naiwna i niczym nie uzasadniona. Matematyk bowiem jest w stanie zrobić wszystko związane ze „swoją” dziedziną: określić dziedziny wartości funkcji, udowodnić, że ona się zakończy, wreszcie podać złożoność obliczeniową-jednej jednak rzeczy

Wyszukiwarka

Podobne podstrony:
P1520564 kim do regulacji wielu funkcji metabolicznych. Komórka może przekazywać do otaczającego śro
DSC00610 tuje się obecnie systemy komputerowe do wspomagania wielu funkcji. Najistotniejsze z nich t
CV8 158 DZIECI, ALKOHOL I NARKOTYKI przyjęty do jednego z wielu znakomitych ośrodków odwykowych w c
94298601 370 K. PANEK chemicznym do siebie, i stąd też objęto je ogólną nazwą kwasów proteinowych.
ALG8 48 Rozdział 2. Rekurencja W celu dokładniejszego przeanalizowania algorytmu posłużymy się kilk
ALG8 88 Rozdział 4. Algorytmy sortowania Jest chyba dość oczywiste, że wywołania rekurencyjne zatrz
Zdjęcie461a KeaKcjM uwainmnia jest procesem wybiórczego wydzielania do otoczenia wielu związków chem
210 Karpat. »Schronisko Fryderyka«), stąd do Matlar (patrz N. 49 — II), 11 */s godz.; II.
242 Oka do Łysej (patrz N. 31); stąd do Jaworzyny Spiskiej (1000; osada), dalej gościńcem przez Pods
Laboratorium Elektroniki cz I 8 172 leży doprowadzić do bramki prąd Igt i zwiększyć prąd tyrystora
SSA42132 120 Teatry Anglii elżbietańskie) (do 1642 r.) W wielu pomniejszych sprawach publiczne teatr
Rys nr8 Wyroby z keramzytu: a)    pustaki do ścian konstrukcyjnych b)   &n
page0019 5 na samym naturalnym gruncie! I jakkolwiek niejeden myślący duch przyszedł do poznania wie

więcej podobnych podstron