ALG5

Rozdział 6

Derekursywacja

Podjęcie tematu przekształcania algorytmów rekurencyjnych na ich postać itc-racyjną - oczywiście równoważną funkcjonalnie! — jest logiczną konsekwencją omawiania rekurencji. Pomimo iż temat ten był kiedyś podejmowany wyłącznie na użytek języków nie umożliwiających programowania rekurencyjnego (FORTRAN, COBOL), nawet obecnie znajomość tych zagadnień może mieć pewne znaczenie praktyczne.

Sam fakt poruszenia tematu derekursywacji w książce poświęconej algorytmom i technikom programowania jest trochę ryzy kowny - nie są to zagadnienia o charakterze czysto algorytmicznym. Tym niemniej w praktyce w'arto coś na temat wiedzieć, gdyż trudno derekursywacji odmówić znaczenia praktycznego. Skąd jednak wziął się sam pomysł takiego zabiegu? Programy wyrażone w formie rekurencyjnej są z natury rzeczy bardzo czytelne i raczej krótkie w zapisie. Nie trzeba być wybitnym specjalistą od programowania, aby się domyślić, iż wersje iteracyjne będą zarówno mniej czytelne, jak i po prostu dłuższe. Po cóż więc w ogóle podejmować się tego — zdawałoby się bezsensownego - zadania?

Rzeczywiście, postawienie sprawy w ten sposób jest zniechęcające. Poznawszy kilka istotnych zalet stosowania technik rekurencyjnych chcemy się teraz od tego całkowicie odwrócić plecami! Na szczęście nie jest aż tak źle, bowiem nikt tu nie ma zamiaru proponować rezygnacji z rekurencji. Nasze zadanie będzie wchodziło w zakres zwykłej optymalizacji kodu w celu usprawnienia jego wykonywania w rzeczywistym systemie operacyjnym, w prawdziwym komputerze.

Piętą Achillesową większości funkcji rekurencyjnych jest intensywne wykorzystywanie stosu, który- służy do odtwarzania „zamrożonych” egzemplarzy tej samej funkcji. Z każdym takim nieczynnym chwilowo egzemplarzem trzeba zachować pełny zestaw jego parametrów wywołania, zmiennych lokalnych czy w-reszcie adres powrotu. To tyle, jeśli chodzi o samą zajętość pamięci. Nie zapominajmy jednak, iż zarządzanie przez kompilator tym całym bałaganem