Wiesz już, jak podchodzić do rozwiązywania stawianych przed tobą problemów programistycznych. Schemat wygląda tak, że zwykle najpierw próbujemy skorzystać z gotowego rozwiązania, a jeśli to nie zadziała, modyfikujemy i rozszerzamy rozwiązania, które znamy. Ostatecznie sięgamy po metodę łączenia rozwiązań częściowych. Próbujemy zatem uprościć proces. Są jednak problemy, które możemy rozwiązać, rozbijając je na takie podproblemy, które są podobne do całości. Rozwiązywanie mniejszych podproblemów ma zaś doprowadzić do rozwiązania problemu głównego. Taką metodę nazywamy metodą rekurencyjną.

Definicja rekurencji

Z rekurencjąrekurencjarekurencją w informatyce spotykamy się w sytuacji, gdy korzystamy z rozwiązań tego samego problemu, ale dla mniejszej wartości lub liczby danych. W takim wypadku często stosujemy algorytm rekurencyjny, czyli odwołujący się do siebie. Algorytm kończy się, gdy potrafimy podać odpowiedź bez korzystania z rozwiązań dla mniejszych danych.

Przejdźmy do matematycznej definicji ciągu zdefiniowanego rekurencyjnie. Najpierw zapisujemy wyraz ciągu o indeksie 0 (lub kilka początkowych jego wyrazów). Następnie podajemy wzór na wyraz o indeksie n wyrażony za pomocą wyrazów poprzednich.

Wzór rekurencyjny uzależnia więc wartość dowolnego (ogólnego) wyrazu tego ciągu od wartości poprzedzających go wyrazów.

Jedz kaszkę
	jeśli talerz jest pusty
    	koniec jedzenia
	w przeciwnym razie
    	zjedz łyżkę kaszki
    	Jedz kaszkę

Jedz kaszkę
	jeśli talerz jest pusty
    	koniec jedzenia
	w przeciwnym razie
    	zjedz łyżkę kaszki
    	Jedz kaszkę
            jeśli talerz jest pusty
                koniec jedzenia
            w przeciwnym razie
                zjedz łyżkę kaszki
                Jedz kaszkę
                	...

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

W przykładzie została opisana za pomocą pseudokodu funkcja rekurencyjna, która oblicza n-ty wyraz ciągu według podanego wzoru rekurencyjnego. Jej parametrem jest indeks wyrazu ciągu, który chcemy obliczyć.

Jeżeli argumentem funkcji będzie wartość 0, to zwróconą wartością będzie 2. Jeśli nie, ponownie wywoływana jest funkcja rekurencyjna, ale z inną wartością argumentu. W tym przypadku wartością argumentu jest indeks poprzedniego wyrazu ciągu, czyli n - 1.

Algorytm jest rekurencyjny wtedy, gdy do rozwiązania problemu wykorzystuje on sam siebie. Funkcja jest rekurencyjna wtedy, gdy wywołuje samą siebie. Kolejne wywołania takiej funkcji nazywamy rekurencyjnym ciągiem wywołań.

Rekurencyjny ciąg wywołań musi być skończony ten nie może być nieskończony, stąd w rekurencji musi być określony warunek kończący rekurencję.

Proces taki możemy pokazać za pomocą drzewa wywołań rekurencyjnych. Przedstawiony na ilustracji przykład jest drzewem wywołań rekurencyjnych dla początkowego wywołania funkcji a(5). Takie wywołanie zwróci wartość 17.

R773dixte7pUY

Ilustracja przedstawia prostokątne pola z niebieską ramką oraz z napisami umieszczone w sześciu rządach. Na górze ilustracji znajduje się prostokąt z napisem a indeks dolny 5. Od niego w dół w lewą stronę prowadzi strzałka do prostokąta z napisem a indeks dolny 4, a w dół w prawą stronę prowadzi strzałka do prostokąta z napisem +3. Od prostokąta z napisem a indeks dolny 4 w dół w lewą stronę prowadzi strzałka do prostokąta z napisem a indeks dolny 3. Od prostokąta z napisem a indeks dolny 3 w dół w lewą stronę prowadzi strzałka do prostokąta z napisem a indeks dolny 2, a w dół w prawą stronę prowadzi strzałka do prostokąta z napisem +3. Od prostokąta z napisem a indeks dolny 2 w dół w lewą stronę prowadzi strzałka do prostokąta z napisem a indeks dolny 1, a w dół w prawą stronę prowadzi strzałka do prostokąta z napisem +3. Od prostokąta z napisem a indeks dolny 1 w dół w lewą stronę prowadzi strzałka do prostokąta z napisem a indeks dolny 0, a w dół w prawą stronę prowadzi strzałka do prostokąta z napisem +3.

Algorytm Euklidesa

Przypomnijmy: algorytm Euklidesa stosowany jest do wyznaczania największego wspólnego dzielnika (NWDNWDNWD) dwóch liczb naturalnych. NWD może być wykorzystany do skracania ułamków czy obliczania najmniejszej wspólnej wielokrotności (NWW). Więcej na temat tego algorytmu przeczytasz w e‑materiale: Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa.

Specyfikacja problemu:

Dane

• a – liczba naturalna

• b – liczba naturalna

Wynik

• NWD liczb a i b

Algorytm Euklidesa z odejmowaniem

Wersja rekurencyjna prezentuje się następująco:

funkcja NWD(a, b)
	jeżeli a != b:
		jeżeli a > b 
        	zwróć NWD(a - b, b)
		w przeciwnym razie
        	zwróć NWD(a, b - a)
	zwróć a

Funkcje są rekurencyjnie wywoływane do momentu, gdy wartości argumentów funkcji będą takie same. Wtedy zwracana jest wartość jednego z nich i to on jest największym wspólnym dzielnikiem liczb a oraz b.

Algorytm Euklidesa opiera się na prostej obserwacji: jeżeli liczba naturalna c dzieli liczby naturalne a i b, to dzieli również ich różnicę. Rzeczywiście jeśli c = NWD(a, b), wówczas istnieją takie względnie pierwszeliczby względnie pierwszewzględnie pierwsze liczby naturalne k i l, dla których a = c * k oraz b = c * l. Niech ponadto a > b. Wówczas a - b = c * k - c * l = c * (k - l), co oznacza, że liczba a - b również dzieli się przez c. To oznacza, że zarówno różnica liczb b oraz a - b, jak i różnica liczb a oraz a - b dzielą się przez c. Powtarzanie odejmowania doprowadzi do obliczenia c.

Algorytm Euklidesa z resztą z dzielenia

W tym wariancie algorytmu do znalezienia NWD – zamiast różnicy dwóch liczb – używa się reszty z ich dzielenia.

W podejściu rekurencyjnym dla b różnego od 0 przykładowa funkcja NWD(a, b) wywołuje samą siebie z argumentami NWD(b, a mod b) do momentu trafienia na przypadek podstawowy, kiedy b będzie równe 0. Pseudokod takiej funkcji wygląda następująco:

funkcja NWD(a, b):
	jeżeli a != 0:
    	zwróć NWD(b mod a, a)
    w przeciwnym razie
    	zwróć b

Funkcje są rekurencyjnie wywoływane do momentu, gdy wartość jednego argumentu funkcji jest równa 0. Wtedy zwracana jest wartość jednego z nich i to on jest największym wspólnym dzielnikiem liczb a oraz b.

Zastanówmy się, dlaczego możemy w ten sposób podejść do tego problemu.

Załóżmy, że chcemy obliczyć NWD dwóch liczb a oraz b. Są to liczby naturalne. Chcemy wyznaczyć liczbę c, która jest ich największym wspólnym dzielnikiem.

W naszym problemie a ≤ b. Podzielmy b przez a. Otrzymamy iloraz (x oraz resztę (r). Zapiszmy to.

Zatem:

natomiast:

Jeśli r = 0, to NWD(a, b) = a. Oznacza to, że jedna z liczb dzieli drugą bez reszty, zatem mniejsza z liczb jest wspólnym dzielnikiem.

Jeśli natomiast r ≠ 0, możemy zapisać, że r = b - xa. Możemy zatem zauważyć, że każda liczba, która dzieli liczby a oraz b, dzieli również całe wyrażenie b - xa, zatem dzieli również r. Wynika z tego to, że NWD liczb a oraz b dzieli również resztę r.

Możemy to zapisać jako NWD(a, b) = NWD(r, a), a ponieważ reszta z dzielenia jest wynikiem operacji modulo, to NWD(a, b) = NWD(b mod a, a).

Problemy związane z rekurencją

Programy wykorzystujące rekurencję wymagają użycia dużej ilości pamięci. Dla każdego wywołania funkcji (w tym rekurencyjnego) program musi umieścić w pamięci adres powrotu, wartości zmiennych lokalnych, jak również wartości argumentów wywoływanej funkcji. Dane te są niezbędne do odtworzenia stanu przed wywołaniem, w momencie zakończenia danej funkcji. Może to spowodować przepełnienie pamięciprzepełnienie pamięciprzepełnienie pamięci. Informacje te zapisywane są w wyznaczonym miejscu pamięci, które zwiemy stosemstosstosem.

Rozwiązywanie niektórych problemów metodą rekurencyjną może także znacząco zwiększyć złożoność czasową algorytmu. W takiej sytuacji wskazane jest użycie wersji iteracyjnej rozwiązania problemu.

Aby zobrazować problem przepełnienia stosu, posłużmy się przykładem. Uruchomienie funkcji rekurencja(n), zdefiniowanej na początku tego e‑materiału, spowoduje uruchomienie drzewa rekurencyjnego o wysokości n. Oznacza to, że aby obliczyć wartość funkcji rekurencja(n), potrzebujemy na stosie obszaru o wielkości $n\cdot c$, gdzie $c$ jest pewnym współczynnikiem stanowiącym średnią ilości pamięci zajmowanej na stosie przy każdym kolejnym wywołaniu funkcji.

Niech $c$ wynosi 16 bajtów. Wówczas przy zakładanej wielkości stosu maksymalna wartość $n$, dla której możemy wywołać funkcję rekurencja(n) bez błędu przepełnienia stosu, wynosi:

W rzeczywistości program może zakończyć się dużo wcześniej. Np. interpreter języka Python domyślnie ogranicza liczbę wywołań rekurencyjnych do 1000. W języku C++ nie ma takiego ograniczenia.

Złożoność obliczeniowa tej funkcji wynosi O(n), ponieważ funkcja wywołuje samą siebie n razy, a każde wywołanie wykonuje stałą liczbę operacji (jedno dodawanie i jeden warunek).

Złożoność pamięciowa jest również O(n), ponieważ dla każdego wywołania funkcji rezerwowany jest nowy stos o stałym rozmiarze (w tym przypadku 4 bajty) na wartości zwracane przez wywołania rekurencyjne oraz zmienne lokalne. Zatem całkowita ilość pamięci potrzebna na utworzenie wszystkich stosów wynosi O(n * 4) = O(n).

Ciekawostka

R1Uvx1k6avDMt1

Fotografia przedstawia puszkę z kakao firmy: Droste's cacao .
Znajduje się na nim kobieta trzymająca to samo opakowanie kakao oraz filiżankę na spodku z napisem: Droste . Kobieta ubrana jest w biały czepek, długą suknię zapiętą pod szyję z pionowym pasem biegnącym przez środek od kołnierzyka w dół i białą opaską na lewym rękawie. W lewym dolnym rogu opakowania znajduje się napis: netto 1/10 K.G., Tło posiada kolor czerwony.

Efekt Droste'a swoją nazwę zawdzięcza opakowaniu kakao o tej samej nazwie. Na etykiecie produktu przedstawiona została kobieta trzymająca tacę z filiżanką i puszką kakao, na której w sposób rekurencyjny powtórzony został cały rysunek.

Podobny efekt zastosowano również na opakowaniach popularnego serka. Co ciekawe, jego nazwa w Polsce to fonetyczny zapis skróconej nazwy francuskiego oryginału (fr. La vache qui rit).

Innym przykładem rekurencji mogą być matrioszki, czyli rosyjskie drewniane lalki. Ich specyfika polega na tym, że wewnątrz największej lalki znajdują się identyczne, coraz mniejszych rozmiarów.

Słownik