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ą 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.

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, 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.

RAJ6R74ML8S6L

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.

Ciekawostka

R1NDALT6QTNVT1

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, kolejno o coraz mniejszych rozmiarach.

Słownik