ALG6

166 Rozdział 6. Derekursywacji

kosztuje cenny czas procesora, który dodaje się do ogólnego czasu wykonani! programu!

Pomysł jest zatem następujący: podczas tworzenia oprogramowania wykorzystajmy całą siłę i elegancję algorytmów rekurencyjnych, natomiast w momencie pisania wersji końcowej (tej, która ma być używana w praktyce), dokonajmy transformacji na analogiczną postać iteracyjną. Z uwagi na to, że nie zawsze jest to proces oczywisty, warto poznać kilka standardowych sposobów używanych do tego celu.

Zaletą zabiegu transformacji jest pełna równoważność funkcjonalna. Implikuje to między innymi fakt, iż ttędąc pewnym poprawności działania danego programu re-kurencyjnego, nie musimy już udowadniać poprawności jego wersji iteracyjnej. Wyrażając to innymi słowy: dobry algorytm rekurencyjny nie ulegnie zepsuciu po swojej poprawnej transformacji.

6.1. Jak pracuje kompilator?

Języki strukturalne, pełne konstrukcji o wysokim poziomie abslrakcji, nie mogłyby spełniać w ogóle swojej roli. gdyby nie istniały kompilatory. Kompilatory są to również programy, które przetłumaczą nasze dzieła na postać zrozumiałą przez (mikro)procesor.

Dodajmy jeszcze, że efekt tego tłumaczenia marnie przypomina to, co z takim trudem napisaliśmy i uruchomiliśmy. Wyklęta ongiś instrukcja goto (a w każdym razie jej odpowiedniki) występuje w kodzie wynikowym częściej. Popatrzmy dla przykładu na tłumaczenie maszynowe' zwykłej instrukcji warunkowej:

if(warunek)

Instrl;

else

Instr2;

Jest to prosta instrukcja strukturalna, ale jej wykonanie musi być sekwencyjne:

if not warunek goto etl ASM(Instrl) goto koniec etl:

¹    Pod warunkiem, że jest to konieczne z uwagi na parametry czasowe naszej aplikacji lub jej ograniczone zasoby pamięci. W każdym innym przypadku podejmowanie się derekursywacji ma sens raczej wątpliwy.

²    Przedstawione oczywiście symbolicznie za pomocą pseudokodu asemblerowego.