ALG1

2.B. Typy programów rekurencyjnych 41

if (x==0)

return 1;

else

return x*silnial !x-l); t

Nie jest to bynajmniej jedyna możliwa realizacja funkcji obliczającej silnię. Spójrzmy dla przykładu na następującą wersję:

unsigned long int silnia2(unsigned long int x,

unsigned long int tirp=l)

{

if (x==C) return tmp; else

return 3ilnia2(x-1,x*tmp);

)

W pierwszym momencie działanie tej funkcji nie jest być może oczywiste, ale wystarczy wziąć kartkę i ołówek, aby przekonać się na kilku przykładach, że wykonuje ona swoje zadanie. Osobom nie znającym dobrze C++ należy się niewątpliwie wyjaśnienie konstrukcji funkcji silnia2. Otóż dowolna funkcja w C++ może posiadać parametry domyślne. Dzięki temu funkcja o nagłówku:

FunDoxi(int a, int k=l)

może być wywołana na dwa sposoby:

•    określając wartość drugiego parametru, np FunDom(12,5): w tym przypadku k przyjmuje wartość 5;

•    nie określając wartości drugiego parametru, np. FunDom(12): k przyjmuje wtedy wartość domyślną równą tej podanej w nagłówku, czyli 1.

Ta użyteczna cecha języka C++ wykorzystana została w drugiej wersji funkcji do obliczania silni. Jednak jakie istotne względy przemawiają za używaniem tej osobliwej z pozoru metody programowania? Argumentem nie jest tu wzrost czytelności programu, bowiem już na pierwszy rzut oka silnia2 jest o wiele bardziej zagmatwana niż silnia l\

Istotna zaleta rekurencji „z parametrem dodatkowym” jest ukryta w sposobie wykonywania programu. Wyobraźmy sobie, że program rekurencyjny „bez parametru dodatkowego” wywołał sam siebie 70-krotnie, aby obliczyć dany wynik. Oznacza to, że wynik cząstkowy z dziesiątego, najgłębszego poziomu rekurencji będzie musiał być przekazany przez kolejne dziesięć poziomów' do góry, do swojego pierwszego egzemplarza.

Jednocześnie z każdym „zamrożonym” poziomem, który czeka na nadejście wyniku cząstkowego, wiąże się pewna ilość pamięci, która służy do odtworzenia

Wyszukiwarka

Podobne podstrony:
ALG1 3.7. Analiza programów rekurencyjnych 71 Cały ten bagaż wzorów był naprawdę niezbędny! Dla zil
144 ROZDZIAŁ 19. TYPY ZŁOŻONE e ■ A; u.a • 0; 3.a • 0; return e ♦ u.a + s.a;} Nie jest to jednak
skanowanie0031 (41) Niowspólmiornosć nych społeczeństw są odrębne, nie jest to po. prostu ten sam św
7b (3) I Zadanie 3. (lOp.) Dany jest następujący program: int f(int i) { if(x>0) return x+f(x-l);
ALG1 2.2. Ilustracja pojęcia rekurencji 31 od psychologii zachowań dziecka chwyciłby się za głowę z
ALG3 3.7. Analiza programów rekurencyjnych 737X1) = 1 + 1 = 2, -2 + 7 T(n) = 1 + 1 + 71 Widać już,
ALG5 3.7. Analiza programów rekurencyjnych 75 otrzymując w efekcie: =26„_, +3log, 3} _ frównanie li
ALG9 3.7. Analiza programów rekurencyjnych 69 W tym paragrafie przedstawiona zostanie metoda mająca
ALG0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
Alg0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
PLD11 IF/THEN/ELSE w przeciwnym razie Jeśli prawda to "instrukcja", " instrukcja"
Co to jest paradygmat programowania? ■    Nie jest to wzorcowy sposób pisania

więcej podobnych podstron