Pomoc - Algorytmika i Modelowanie

Spis paragrafów >> Iteracja i rekurencja << Powrót

<< Poprzedni Następny >>

74. Iteracja i rekurencja

W niektórych algorytmach, np. przy obliczaniu sumy liczb od 1 do 10, pewne sekwencje poleceń się powtarzają. W każdym kolejnym przebiegu algorytmu, zamiast pisać go na nowo, wykonujemy tzw. pętlę, czyli wprowadzamy do obliczeń wartość x o 1 większą. Zapisujemy to jako x:= x+1 i czytamy: za x podstaw x + 1. Powtarzanie sekwencji poleceń do czasu spełnienia warunku zakończenia powtarzania nazywamy iteracją.

Iteracja występuje w różnych dziedzinach życia. Na przykład w literaturze cechy iteracji wykazuje popularny dziecięcy wiersz.

Na zielonej łące, raz, dwa, trzy.
Pasły się zające, raz, dwa, trzy.
A to była pierwsza zwrotka.
Teraz będzie druga zwrotka.

Na zielonej łące, raz, dwa, trzy.
Pasły się zające, raz, dwa, trzy.
A to była druga zwrotka.
Teraz będzie trzecia zwrotka.

Itd.

W ten sposób możemy dodawać liczbę zwrotek, która wcześniej powinna być określona.

Oprócz algorytmów iteracyjnych znane są też algorytmy rekurencyjne. Rekurencja lub rekursja to odwoływanie się funkcji lub definicji do samej siebie. Prostym przykładem rekurencji jest składanie na pół arkusza papieru. Po każdym powtórzeniu czynności, czyli złożeniu arkusza, otrzymujemy arkusz podobny do poprzedniego i tak w nieskończoność. Składanie arkusza w praktyce jednak da się wykonać tylko skończoną liczbę razy.

Innym przykładem rekurencji są fraktale. To figury samopodobne, czyli takie, których część jest podobna do całości. Przykładem fraktala jest dywan Sierpińskiego. Powstaje on przez powtórzenie nieskończoną liczbę razy ciągu następujących poleceń:

1. kwadrat dzielimy na 9 mniejszych kwadratów;

2. usuwamy środkowy kwadrat;

3. do pozostałych nieusuniętych kwadratów stosujemy tę samą zasadę.

W wyniku trzykrotnego powtórzenia tych operacji uzyskujemy poniższy rysunek. Kolorem pomarańczowym oznaczono usunięte kwadraty.

<< Powrót [Do góry]