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:
1 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.
2 Przedstawione oczywiście symbolicznie za pomocą pseudokodu asemblerowego.
Wyszukiwarka
Podobne podstrony:
ALG6 186 Rozdział 6. Derekursywacja D(x); while((N!=i)44(N%2>) ) l N-N/2; C (x)
ALG6 176 Rozdział6. Derekursywacja
ALG8 168 Rozdział 6. Derekursywacjł Jak odróżnić powrót z procedury P, który powoduje definitywne j
ET6 166 Rozdział 10. Polityka turystyczna Młodzieżowych, Polskie Stowarzyszenie Campingu i Caravani
ALG6 26 RozdziaH. Zanim wystartujemy 1.5 metody niezmienników (zwanej niekiedy metodą Floyda). Mają
ALG6 36 Rozdział 2. Rekurencja każemy. W rozdziale 9 zostanie omówiona ciekawa technika programowan
ALG6 46_ _ Rozdział2. Rekurencja rekurencyjnych jest pamięcioźerność: wielokrotne wywołania rekuren
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else //element zost
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy
ALG 6 96 Rozdział 5. Struktury danych Rys. 5 - 3. FCOOh FCI4h FFEEh Przykład listy jedno-kierunk
ALG6 106 Rozdziała. Strukturydanjt 5.1 będzie ich fuzją. Rekurencyjny zapis tego procesu jest bardz
ALG6 116 Rozdział 5. Struktury danych Iisla2.li int alfabetycznie(ELEMENT *q],ELEMENT *q2) { II czy
ALG6 126 Rozdział 5. Struktury danych Rys. 5 - 12. Metoda„ tablic równoległych " (2) DANE L2
ALG6 136 Rozdział 5. Struktury danycł forfint i=0; i<4;i+~) kolejka.wstaw(tab[i)); for(i=0;
ALG6 146 Rozdział 5. Struktury danycti Jak widać, inteligentne użycie tablic może nam podsunąć możl
ALG6 156 Rozdział 5. Struktury danya Proces przechadzania się po drzewie nie jest bynajmniej zakońc
więcej podobnych podstron