Przeczytaj

Rekurencja a iteracja

Przypomnijmy sobie najważniejsze wiadomości na temat rekurencji i iteracji.

IteracjaiteracjaIteracja to technika programowania polegająca na wielokrotnym wykonywaniu danego ciągu instrukcji. W programie iterację realizujemy za pomocą instrukcji iteracyjnych – czyli pętli. Instrukcje w pętli wykonywane są do momentu, gdy zostanie spełniony warunek wykonywania pętli.

W przypadku rekurencjirekurencjarekurencji funkcja wywołuje samą siebie ze zmienionym parametrem. Parametr ten określa poziomy wywołań rekurencyjnych funkcji, to znaczy stopień zagłębienia się wywołań. Gdy zostaje spełniony warunek początkowy rekurencjiwarunek początkowy rekurencjiwarunek początkowy rekurencji, zwracana jest konkretna wartość. Dzięki temu ciąg wywołań rekurencyjnych ma swój koniec. Gdy funkcja się zakończy lub zwróci wartość, następuje powrót do poprzedniego poziomu (w miejsce po wywołaniu funkcji) i wykonywane są kolejne zapisane instrukcje.

Jakie są zatem wady i zalety tych dwóch metod - rekurencyjnej i iteracyjnej? Sprawdźmy, którą z nich zastosować w jakiej sytuacji.

Którą technikę wybrać?

Mimo że użycie rekurencji przy rozwiązywaniu niektórych problemów zapewnia krótki i czytelny kod, to algorytmy iteracyjne często są bardziej wydajne pod względem czasu i pamięci.

Stosowanie rekurencji w wielu przypadkach jest nieefektywne, często powtarzane są wiele razy te same obliczenia. Na przykład rekurencyjny algorytm obliczania elementu ciągu Fibonacciego (przedstawiony w e‑materiale Ciąg FibonacciegoPMu9Wf5p9Ciąg Fibonacciego) ma złożoność $O (2^{n})$ , podczas gdy złożoność algorytmu iteracyjnego to $O (n)$ . Wynika to z faktu, że w celu wyznaczenia wybranego elementu ciągu metodą rekurencyjną wielokrotnie są obliczane te same, poprzedzające go wartości:

R1c8RoDrXsDZk

Ilustracja przedstawia drzewo binarne.Każde dziecko jest połączone z rodzicem za pomocą linii prostej Zaczynając od wierzchołka drzewa oznaczonego F5, posiada dwójkę dzieci w drugim rzędzie : z lewej strony f4 i z prawej strony f3.Wierzchołek f4 posiada dwójkę dzieci w trzecim rzędzie: z lewej f3 i z prawej f2. Wierzchołek f3 w trzecim rzędzie posiada dwójkę dzieci w czwartym rzędzie: z lewej f2 i z prawej f1. Wierzchołek f2 w czwartym rzędzie posiada dwójkę dzieci w piątym rzędzie: z lewej f1 i z prawej f0. Wierzchołek f2 w trzecim rzędzie posiada dwójkę dzieci w czwartym rzędzie: z lewej f1 i z prawej f0. Wierzchołek f3 w drugim rzędzie posiada dwójkę dzieci: z lewej f2 i z prawej f1. Wierzchołek f2 w trzecim rzędzie posiada dwójkę dzieci: z lewej f1 i z prawej f0. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ponadto użycie rekurencji wymaga zajęcia dużej ilości pamięci. Jest to spowodowane koniecznością rezerwacji miejsca na zmienne, argumenty wywołania i wartości zwracane z każdym wywoływaniem funkcji. To sprawia, że program w wersji rekurencyjnej może być znacznie wolniejszy od tego napisanego metodą iteracyjną.

Aby porównać te dwie techniki programowania, napiszmy funkcje obliczające potęgę danej liczby, korzystając z metody iteracyjnej, a następnie rekurencyjnej. Zacznijmy od podejścia iteracyjnego.

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą iteracyjną

Specyfikacja:

Dane:

wykładnik – wykładnik potęgi, liczba naturalna
podstawa – podstawa potęgi, liczba całkowita

Wynik:

wynik – wynik potęgowania $p o d s t a w a^{w y k ł a d n i k}$ , liczba całkowita

Oto funkcja zapisana za pomocą pseudokodu w wersji iteracyjnej:

funkcja iteracyjnie(podstawa, wykładnik)
	wynik ← 1
	dopóki wykładnik > 0 wykonuj
		wynik ← wynik * podstawa
		wykładnik ← wykładnik - 1
	zwróć wynik

Parametrami przyjmowanymi przez funkcję są podstawa, czyli element potęgowany, oraz jej wykładnik.

Wynik potęgowania przechowywany jest w zmiennej wynik. Inicjujemy ją wartością 1, dzięki czemu bezpośrednio otrzymamy wynik dla wykładnika równego 0.

Dopóki wykładnik jest większy od 0, dopóty wynik mnożymy przez podstawę. W ten sposób otrzymamy iloczyn tylu czynników podstawa, ile wynosi wykładnik.

Na koniec zwracany jest wynik, w którym zapisany będzie wynik potęgowania.

Zaprezentowany schemat przedstawia podejście iteracyjne obliczania potęgi danej liczby dla podstawy równej 3 i wykładnika równego 4. Przedstawione tu zostały kolejne iteracje pętli.

RWZuwF3ajnXgf

Ilustracja przedstawia schemat składający się z danych tekstowych oraz bloków. Od każdego z elementów wychodzi strzałka skierowana na dół, wskazująca na kolejny element. Na samej górze znajduje się pogrubiony napis: iteracyjnie(3,4). Następnie: 1. wynik=1. 2. wykładnik większy od 0, blok: wynik=1 razy 3, wykładnik=4‑1=3. 3.wykładnik większy od 0, blok: wynik=3 razy 3=9, wykładnik=3‑1=2. 4. wykładnik większy od 0, blok: wynik=9 razy 3=27, wykładnik=2‑1=1. 5. wykładnik większy od 0, blok: wynik = 27 razy 3 = 81, wykładnik=1‑1=0. 6. wykładnik nie jest większy od 0. Na samym dole znajduje się pogrubiony napis: zwróć 81. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ważne!

Przedstawiony iteracyjny algorytm obliczania potęgi według definicji jest algorytmem o relatywnie niskiej złożoności czasowej. Istnieje jednak efektywniejsze rozwiązanie iteracyjne wykorzystujące schemat Hornera - szybkie potęgowanie liczb. Omówienie tego algorytmu znajdziesz w e‑materiale Algorytmy iteracyjne i liczbowe – potęgowanie liczbPeGPO00R1Algorytmy iteracyjne i liczbowe – potęgowanie liczb.

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą rekurencyjną

Specyfikacja:

Dane:

wykładnik – wykładnik potęgi, liczba naturalna
podstawa – podstawa potęgi, liczba całkowita

Wynik:

wynik – wynik potęgowania $p o d s t a w a^{w y k ł a d n i k}$ , liczba całkowita

Oto zapisana za pomocą pseudokodu funkcja realizująca potęgowanie techniką rekurencyjną:

funkcja rekurencyjnie(podstawa, wykładnik)
	jeżeli wykładnik = 0
		zwróć 1
	zwróć podstawa * rekurencyjnie(podstawa, wykładnik - 1)

Funkcja rekurencyjnie() przyjmuje dwa parametry - podstawa oraz wykładnik. Jeżeli wykładnik jest równy 0, od razu zwracana jest wartość 1. Dzieje się tak dlatego, że niezależnie od podstawy liczba podniesiona do potęgi 0 daje wynik równy 1.

W przeciwnym wypadku mnożymy podstawę przez wynik potęgowania, którego wykładnik zmniejszony jest o 1. Oto matematyczny przykład dla 3Indeks górny 4:

3^{4} = 3 \cdot 3^{3}

R1OWgSd0yjtY4

Ilustracja przedstawia schemat zawierający bloki wypełnione tekstem. Od każdego bloku wychodzi strzałka wskazująca na kolejny element. 1. rekurencyjnie (3, 4), 3 razy rekurencyjnie (3, 3). Strzałka skierowana do dołu. 2. rekurencyjnie (3, 3), 3 razy rekurencyjnie (3, 2). Strzałka skierowana do dołu. 3. rekurencyjnie (3, 2), 3 razy rekurencyjnie (3, 1). Strzałka skierowana do dołu. 4. rekurencyjnie (3, 1), 3 razy rekurencyjnie (3, 0). Strzałka skierowana do dołu. 5. rekurencyjnie (3, 0), ZWRÓĆ 1. Strzałka skierowana do góry. 6. ZWRÓĆ 3 razy 1=3. Strzałka skierowana do góry. 7. ZWRÓĆ 3 razy 3=9. Strzałka skierowana do góry. 8. ZWRÓĆ 3 razy 9=27. Strzałka skierowana do góry. 9. ZWRÓĆ 3 razy 27=81. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Funkcja wywołuje rekurencyjnie samą siebie z drugim parametrem zmniejszonym o 1. Jeżeli parametr ten wynosi 0, spełniony zostaje warunek początkowy rekurencji. Funkcja nie wywołuje wtedy rekurencyjnie kolejnej funkcji, a zwraca konkretną wartość, w tym przypadku 1. Zwrócona wartość (pobrana ze stosu) zostaje przypisana jako wartość funkcji w miejscu jej wywołania i wykonywane są obliczenia, a przeznaczony na nią obszar pamięci na stosie zostaje zwolniony.

Szybkie potęgowanie liczb – definicja rekurencyjna

Istnieje szybszy sposób potęgowania liczb od potęgowania według definicji. Jest on oparty na schemacie Hornera.

Zwróćmy uwagę, że potęgowanie $2^{6}$ według definicji:

2^{6} = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2

możemy obliczyć inną metodą. Przedstawia się ona następująco:

2^{6} = {(2^{3})}^{2} = {(2 \cdot 2^{2})}^{2}

Stosując tę metodę, zamiast pięciu mnożeń wykonalibyśmy trzy. Oszczędność liczby mnożeń wydaje się niewielka, jednak dla większych wykładników znacząco skracamy czas przeprowadzania tego działania. Załóżmy, że znamy wartość potęgi $2^{25}$ . Wtedy chcąc wykonać działanie $2^{50}$ , dokonujemy tylko jednego mnożenia!

2^{50} = {(2^{25})}^{2}

Obliczając tę potęgę zgodnie z powszechnie znaną definicją, znając wartość $2^{25}$ , musielibyśmy wykonać jeszcze 25 dodatkowych mnożeń.

2^{50} = 2^{25} \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot . . . \cdot 2

Opierając się na powyższej analizie, możemy ustalić definicję rekurencyjną szybkiego potęgowania liczb ( $a \neq 0$ ) :

$a^n = \begin{cases} 1 & \quad \text{dla } n \text{ = 0}\\ a \cdot a ^{n-1} & \quad \text{dla } n \text{ mod 2 = 1}\\ (a^{n / 2})^{2} & \quad \text{dla } n \text{ mod 2 = 0} \end{cases}$

Na podstawie definicji konstruujemy algorytm rekurencyjny:

Specyfikacja problemu:

Dane:

n – wykładnik potęgi, liczba naturalna
a – podstawa potęgi, liczba całkowita różna od zera

Wynik:

wynik – wynik potęgowania $a^{n}$ , liczba całkowita

funkcja potęgowanie(a, n)
	jeżeli n = 0
		zwróć 1
	jeżeli n mod 2 = 1
		zwróć a * potęgowanie(a, n-1)
	w przeciwnym razie
		potęga ← potęgowanie(a, n/2)
	zwróć potęga * potęga

Ważne!

Zaprezentowana metoda ma swoją wersję iteracyjną. Jej omówienie znajdziesz w e‑materiale Algorytmy iteracyjne i liczbowe – potęgowanie liczbPeGPO00R1Algorytmy iteracyjne i liczbowe – potęgowanie liczb

Analiza złożoności czasowej

Złożoność czasowa algorytmu potęgowania liczb według następującej definicji:

a^{n} = \underset{n}{\underset{⏟}{a \cdot a \cdot \dots \cdot a}}

wyrażona jako liczba wykonanych mnożeń wynosi $O (n)$ - zarówno w wersji iteracyjnej jak i rekurencyjnej.

W przypadku algorytmu szybkiego potęgowania możemy zauważyć, że każde pojedyncze lub każde dwa kolejne wywołania rekurencyjne funkcji zmniejszają wykładnik dwukrotnie. Zatem zostanie wykonanych maksymalnie $2 \log_{2} n$ mnożeń. Złożoność algorytmu szybkiego potęgowania liczb wynosi więc $O (\log_{2} n)$ .

Słownik

iteracja

technika programowania polegająca na wielokrotnym powtarzaniu zapisanego ciągu instrukcji aż do spełnienia określonego warunku

rekurencja

technika programowania, w której funkcja wywołuje samą siebie aż do napotkania przypadku podstawowego, czyli takiego, którego nie da się rozłożyć na mniejsze problemy; przykład przypadku podstawowego dla obliczania piątego wyrazu ciągu Fibonacciego: $f i b (4) = f i b (3) + f i b (2) = (f i b (2) + f i b (1)) + (f i b (1) + f i b (0)) =$

$= ((f i b (1) + f i b (0)) + f i b (1)) + f i b (1)) + (f i b (1) + f i b (0)) =$

$= ((1 + 0) + 1) + (1 + 0) = 3$

warunek początkowy rekurencji

podana wprost wartość definiowanej wielkości, niezbędna, aby rekurencja się zakończyła

Wprowadzenie

Schemat interaktywny

Rekurencja a iteracja

Którą technikę wybrać?

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą iteracyjną

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą rekurencyjną

Szybkie potęgowanie liczb – definicja rekurencyjna

Analiza złożoności czasowej

Słownik

Wprowadzenie

Schemat interaktywny

Przeczytaj

Rekurencja a iteracja

Którą technikę wybrać?

Obliczanie potęgi p o d s t a w a w y k ł a d n i k metodą iteracyjną

Obliczanie potęgi p o d s t a w a w y k ł a d n i k metodą rekurencyjną

Szybkie potęgowanie liczb – definicja rekurencyjna

Analiza złożoności czasowej

Słownik

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą iteracyjną

Obliczanie potęgi $p o d s t a w a^{w y k ł a d n i k}$ metodą rekurencyjną