Artur Bugajski

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