Rekurencja (2)


0x01 graphic
0x01 graphic
0x01 graphic
0x01 graphic

0x01 graphic
0x01 graphic
Rekurencja.


Z rekurencją mamy do czynienia wtedy, gdy podprogram (funkcja lub procedura) wywołuje sam siebie. W Pascalu taka konstrukcja językowa jest dozwolona. Podprogramy rekurencyjne pozwalają na zgrabny i przejrzysty zapis algorytmu takich problemów, w których wynik końcowy jest złożeniem wielu wyników cząstkowych. Jednym z takich problemów jest np. obliczenie n!.



Jak widać, aby obliczyć n! musimy znać (n - 1)!, znając (n - 1)! musimy znać (n - 2)! itd. Cały proces kończy się w momencie kiedy n = 0.


Function silnia(n: integer): Longint;
Begin
If n = 0 Then
silnia := 1
Else
silnia := n * silnia(n - 1);
End;

Dla n = 4 kolejne rekurencyjne wywołania funkcji silnia można przedstawić następująco:



Z chwilą wywołania podprogramu następuje powołanie do życia zmiennych lokalnych podprogramu i zmiennych przechowujących wartość argumentu dla parametrów formalnych podprogramu przekazywanych przez wartość. W trakcie rekurencyjnego wywołania takiego podprogramu powstaje następny komplet takich zmiennych. Wielokrotne rekurencyjne wywołanie podprogramów sprawia, że w pamięci występuje wiele takich kompletów zmiennych, z których aktualnie dostępny jest tylko jeden (na schemacie oznaczenia z indeksami ', '', ''', ''''). Z tego wynika, że podprogram rekurencyjny zajmuje więcej pamięci niż odpowiadający mu podprogram iteracyjny. Poza tym podprogramy iteracyjne są zwykle szybsze. Tym niemniej niektóre przykłady da się rozwiązać tylko przy użyciu rekurencji.


Iteracja.


Jest to metoda matematyczna polegająca na wielokrotnym kolejnym zastosowaniu tego samego algorytmu postępowania, przy czym wynik i-tej operacji stanowi dane wejściowe dla kolejnej, (i+1)-szej operacji.


INSTRUKCJE ITERACYJNE.
Służą do ograniczenia cykli programowych, tj. wielokrotnego wykonywania pewnych sekwencji instrukcji.
W języku Turbo Pascal występują trzy instrukcje iteracyjne.
· instrukcja [dla] FOR,
· instrukcja [dopóki] WHILE,
· instrukcja [powtarzaj] REPEAT.


Instrukcję iteracyjną [dla] FOR stosuje się w programie w przypadku, gdy liczba powtórzeń jest znana w danym miejscu programu. Instrukcja for może mieć jedną z dwóch postaci:
gdy wartość początkowa się zwiększa
FOR wartość := wartość_pocz TOwartość_końcowa DO instrukcja
gdy wartość początkowa się zmniejsza
FOR wartość := wartość_pocz DOWNTO wartość_końcowa DO instrukcja


Kolejną instrukcją iteracyjną jest instrukcja [dopóki] WHILE. Instrukcja ta służy do sprawdzenia warunku iteracji na początku i ma postać:

WHILE wyrażenie DO instrukcja

Wyrażenie jest najczęściej wyrażeniem porównania, powinno w wyniku dawać wartość logiczną TRUE lub FALSE, a instrukcja po słowie DO może być dowolną instrukcją prostą lub strukturalną. Instrukcja ta wykonywana jest tak długo dopóki wartością wyrażenia jest TRUE.


REPEAT
instrukcja
instrukcja
UNTIL warunek logiczny



Wyszukiwarka

Podobne podstrony:
Metody układania algorytmów rekurencja, metoda dziel i zwyciężaj, programowanie dynamiczne, metoda
mata2 rekurencja slajdy
Definicja Rekurencji i Iteracji
06 Rekurencja
13 PP Rekurencjaid 14488 (2)
Algorytmy Rekurencja
36 Rekurencja
rekurencyjnie
Rekurencja
Matematyka dyskretna 2002 07 Rekurencja
2 5 Rekurencja i tablice
Wykład 2 strumienie rekurencyjne
2 4 Funkcje rekurencyjne
zadania rekurencja, informatyka
08 Funkcje rekurencjaid 7257 ppt
Rekurencje
MAD Liniowe rownania rekurencyjne
rekurencja wskazniki, WAT, semestr I, wdp

więcej podobnych podstron