Rekurencyjnepodejście rekurencyjneRekurencyjne i iteracyjnepodejście iteracyjneiteracyjne podejście do rozwiązywania problemów algorytmicznych omówimy na przykładzie zadania maturalnego, w którym należy wyznaczyć liczby względnie pierwsze.

Zadanie 1. Iteracyjna alternatywa

Dana jest następująca funkcja rekurencyjna:

funkcja wynik(i)
	jeżeli i < 3:
		zwróć 1 i zakończ;
	w przeciwnym razie:
		jeżeli i mod 2 = 0:
			zwróć wynik(i – 2) + wynik(i – 1)
		w przeciwnym razie:
			zwróć wynik(i – 1) mod 7

Uwaga: Operator mod oznacza resztę z dzielenia.

Zapisz za pomocą pseudokodu lub w wybranym języku programowania program, który wyznaczy wartość wynik(100) bez wywołań rekurencyjnych.

Rozwiązanie

Iteracyjnie obliczymy kolejne wywołania funkcji wynik() i zapiszemy je w tablicy. Definiujemy tablicę o rozmiarze równym 100:

Wyniki[1..100] ← tablica liczb naturalnych

Rekurencja kończy się, jeżeli argument jest mniejszy niż 3 i zwraca wartość 1. W związku z tym do pierwszych dwóch elementów tablicy przypiszemy wartość 1:

Wyniki[1..100] ← tablica liczb naturalnych
Wyniki[1] ← 1
Wyniki[2] ← 1

Każde kolejne wywołanie funkcji w wersji rekurencyjnej potrzebuje - w zależności od parzystości - albo jednego, albo dwóch poprzednich wywołań. Skoro dwa pierwsze elementy mamy zdefiniowane, możemy zadeklarować pętlę od 3 do 100 wypełniającą tablicę Wyniki na podstawie elementów na wcześniejszych indeksach:

Wyniki[1..100] ← tablica liczb naturalnych
Wyniki[1] ← 1
Wyniki[2] ← 1

dla i = 3, 4, ..., 100 wykonuj:

Jeżeli i jest parzyste, wartość kolejnego elementu tablicy jest równa sumie dwóch poprzednich (czyli tak jak w ciągu Fibonacciego). W przeciwnym wypadku jest to reszta z dzielenia poprzedniego elementu przez 7. Po wyjściu z pętli zwracamy odpowiedź.

Wyniki[1..100] ← tablica liczb naturalnych
Wyniki[1] ← 1
Wyniki[2] ← 1

dla i = 3, 4, ..., 100 wykonuj:
	jeżeli i mod 2 = 0:
    	Wyniki[i] ← Wyniki[i - 1] + Wyniki[i - 2]
    w przeciwnym wypadku:
    	Wyniki[i] ← Wyniki[i - 1] mod 7
zwróć Wyniki[100]

W ten sposób wyliczymy wartość wywołania wynik(100) bez jakichkolwiek wywołań rekurencyjnych.

Słownik