ALG0
40
Rozdział 2. Rekurencji
Zapęt lenie jest spowodowane próbą obliczenia parametru p, tymczasem to drugie' wywołanie jest w ogóle niepotrzebne do zakończenia funkcji! Istnieje w niej bowiem warunek obejmujący przypadek elementarny: jeśli n=0, to zwróć J.j. Niestety, kompilator o tym nie wie i usiłuje obliczyć ten drugi parametr, powo-l dując zapętlenie programu...
Przykład omówiony w niniejszym paragrafie należy traktować jako swoisty ciekawostkę, niemniej warto go zapamiętać ze względów czysto edukacyjnych. I
2.6. Typy programów rekurencyjnych
Na podstawie lektury poprzednich paragrafów Czytelnik mógłby wyciągnąć kilka ogólnych wniosków na temat programów używających technik rekurencyjnyeh:l typowo zachłanne w dysponowaniu pamięcią komputera, niekiedy „zawieszają” system operacyjny... Na szczęście jest to błędne wrażenie! Programy rekuren-cyjne mają jedną olbrzymią zaletę: są łatwe do zrozumienia i zazwyczaj zajmują mało miejsca jeśli rozpatrujemy liczbę linii kodu użytego na ich realizację. Z tym ostatnim jest ściśle związana łatwość odnajdywania ewentualnych błędów.l Wróćmy jednak do tematu.
Zauważyliśmy wspólnie, że program rekurencyjny może być pamięciochłonny i wykonywać się dość wolno. Pytanie brzmi: czy istnieją jakieś techniki programowania pozwalające usunąć (lub co najmniej zredukować) powyższe wady z programu rekurencyjnego? Odpowiedź jest na szczęście pozytywna! Otóż pewna klasa problemów natury „rekurencyjnej” da się zrealizować na dwa sposoby, dające dokładnie taki sam efekt końcowy, ale różniące się nieco realizacją praktyczną. Podzielmy metody rekurencyjne, tytułem uproszczenia, na dwa podstawowe typy:
• rekurencja „naturalna”;
• rekurencja „z parametrem dodatkowym”1.
Typ pierwszy mieliśmy okazję zobaczyć podczas analizy dotychczasowych przykładów, teraz zapoznamy się z drugim.
Rozważmy raz jeszcze przykład funkcji obliczającej silnię. Do tej pory znaliśmy ją w postaci:
rekS.cpp
unsigned long int silnidl(unsigned long int x)
{
Pozostaniemy na moment przy tej nieprecyzyjnej nazwie; ten typ rekurencji powróci nam jeszcze w rozdziale 6 - w innym jednakże kontekście.
Wyszukiwarka
Podobne podstrony:
DSC02154 6. Rozkład normalny jest określony jednoznacznie przez 2 parametry Są to
ALG0 30 Rozdział 2. Rekurencja 2.2 potwornie skomplikowany: klocków jest cala masa i niespecjalnie
ALG3 2.7. Myślenie rekurencyjne 43 Rckurcncyjność naszego zadania jest oczywista, bowiem program wy
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
ALG8 88 Rozdział 4. Algorytmy sortowania Jest chyba dość oczywiste, że wywołania rekurencyjne zatrz
ALG0 140 Rozdział 5. Struktury danych porządek. Czy czasem owa procedura nie jest na tyle kosztowna
ALG0 170 Rozdział 6. Oerekursywaci 6.3. Uwaga: Wywołanie rekurencyjne procedury P zawarte w jakiejk
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
golf0 Silnik wysokoprężny Filtr umieszczony jest nad prawym amorty-zatorym. W celu odwodnienia nale
histologia wyk?ad6 Przyczyny anomalii sercowo - naczyniowych Ocenia się, że 8% jest spowodowanych
ŁŚ0 190 warunku podanego wylej (jest nawat aniejazy od ubytku luzu AL, co oznacza, la nastąpiłaby k
img040 (54) Zdaniem Kułakowskiej (1998) autyzm jest spowodowany specyficzną dysfunkcją mózgu, dla kt
IMG58 (2) Achromatopsja Achromatopsja jest spowodowana całkowitym lub niemal całkowitym brakiem
IMG70 BN *0«*13000 Tam gdzie niezbędne jest zapewnienie wiarygodnych wyników, wyposażenie pomiarowe
więcej podobnych podstron