Iteracja i rekurencja – przypomnienie

Przypomnijmy sobie podstawowe informacje na temat iteracjiiteracjaiteracji i rekurencjirekurencjarekurencji.

Iteracja:

• polega na wielokrotnym wykonywaniu zapisanych w programie instrukcji,

• jest realizowana za pomocą pętli – instrukcji iteracyjnych,

• musi być wprowadzony warunek zakończenia pętli.

Rekurencja:

• funkcja wywołuje samą siebie w celu osiągnięcia rozwiązania problemu,

• musi spełniać dwa warunki:

  • warunek początkowy – warunek, który spełniony nie spowoduje wywołania funkcji rekurencyjnej, tylko zwróci konkretną wartość,

  • co najmniej jeden argument w rekurencyjnym wywołaniu funkcji musi mieć inną wartość niż poprzednie.

Którą metodę wybrać?

Dowolny problem możemy rozwiązać dwiema technikami – rekurencyjną i iteracyjną. Problem obliczania wartości elementu ciągu rekurencyjnego możemy także rozwiązać w sposób iteracyjny.

Warto jednak zastanowić się, której metody użyć w algorytmie podczas rozwiązywania danego problemu. Stosowanie techniki rekurencyjnej czyni kod często czytelniejszym, krótszym i zrozumiałym. W przypadku iteracji nasz kod może być dłuższy i trudniejszy do zrozumienia. Trzeba wziąć pod uwagę, że rozwiązując niektóre problemy metodą rekurencyjną, płacimy wysoką cenę. Często funkcja rekurencyjna jest wywoływana dużą liczbę razy, a obliczenia są nieefektywne. W tych przypadkach zdecydowanie wybieramy metodę iteracyjną.

Obliczanie wartości elementu ciągu

Sprawdźmy, jak – na podstawie kilku prostych ćwiczeń – obliczyć wartości elementu ciągu. Przy rozwiązaniu zadań skorzystamy zarówno z techniki rekurencyjnej, jak i z iteracyjnej.

Przeanalizujmy zapisaną w postaci pseudokodu funkcję realizującą algorytm obliczania wartości n‑tego elementu zdefiniowanego ciągu, przy użyciu techniki rekurencyjnej.

funkcja rekurencyjnie(n)
    jeżeli n == 0 wykonaj:
    	zwróć 1
    w przeciwnym razie wykonaj:
    	zwróć 4 * rekurencyjnie(n-1) + 2

Argumentem funkcji rekurencyjnie(n) jest numer wyrazu ciągu, który chcemy obliczyć. W przypadku zerowego wyrazu ciągu zwracana jest wartość 1, natomiast w innych wypadkach musi zostać obliczona wartość poprzedniego wyrazu ciągu, poprzez wywołanie odpowiedniej funkcji rekurencyjnej z argumentem zmniejszonym o 1.

Problem ten możemy także rozwiązać iteracyjnie. Przeanalizujmy zapisaną za pomocą pseudokodu funkcję, tym razem w wersji iteracyjnej.

funkcja iteracyjnie(n)
	a = 1
    dla i = 1, 2, ..., n wykonuj: 
    	a = 4 * a + 2
    zwróć a

Jak widać, powyższa funkcja jest również zrozumiała i krótka. Zmiennej a przypisywana jest wartość 1, to znaczy wartość naszego zerowego elementu ciągu. Następnie dla kolejnych elementów obliczane są wartości w pętli, aż do osiągnięcia naszego poszukiwanego wyrazu o numerze n. Wtedy zwracana jest jego wartość a.

Przejdźmy teraz do trudniejszego przykładu, w którym wartość elementu ciągu będzie zależała od dwóch poprzednich wyrazów ciągu:

Zacznijmy od metody rekurencyjnej:

funkcja rekurencyjnieDrugie(n)
    jeżeli n == 0 wykonaj:
    	zwróć 0
    w przeciwnym razie jeżeli n == 1 wykonaj:
    	zwróć 1
    w przeciwnym razie:
    	zwróć rekurencyjnieDrugie(n-1) * rekurencyjnieDrugie(n-2) + 3

Funkcje napisane techniką rekurencyjną są czytelne i proste. Podobnie jak w przypadku problemu 1, jeżeli funkcja przyjmie parametr 0 lub 1, od razu zwracana jest konkretna wartość, natomiast dla innych parametrów, następują dwa wywołania rekurencyjne funkcji.

W przypadku techniki iteracyjnej, kod będzie dłuższy i trudniejszy do zrozumienia:

funkcja iteracyjnieDrugie(n)
	a = 0
    b = 1
    jeżeli n == 0 wykonaj:
    	zwróć a
    dla i = 2, 3, ..., n wykonuj: 
    	c = a * b + 3
        a = b
        b = c
    zwróć b

Ponownie w przypadku zerowego i pierwszego wyrazu ciągu bezpośrednio zwracana jest wartość. Dla kolejnych wyrazów muszą zostać wykonane instrukcje w pętli. W zmiennej c umieszczany jest iloczyn dwóch poprzednich wyrazów ciągu, powiększony o 3, następnie w zmiennej a będzie przechowywana wartość poprzedniego wyrazu ciągu, która dotychczas była w zmiennej b, natomiast do zmiennej b zostaje zapisana wartość aktualnego wyrazu.

Rekurencja czy iteracja?

W przypadku problemu 1 algorytm możemy zapisać zarówno w wersji rekurencyjnej, jak i iteracyjnej. Jeżeli chodzi o problem 2, mimo iż wersja iteracyjna jest mniej czytelna, to właśnie ją lepiej jest zastosować. Technika rekurencyjna rozwiązywania zadania drugiego wymaga wielu wywołań rekurencyjnych, co jest bardzo nieefektywne obliczeniowo. Dla piątego wyrazu ciągu funkcja rekurencyjnieDwa wywoływana jest aż 15 razy!

Słownik