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.

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

def rekurencja (n):
    if n == 0:
        return 2
    else:
        return rekurencja(n-1) + 3
print(rekurencja(5))
# wynik
# 17

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.

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.

Słownik