Każdy kto choć trochę interesuje się programowaniem, z pewnością słyszał określenie „rekurencja”. Jeśli chcecie dowiedzieć się czym ona jest, zapraszam was do lektury poniższego wpisu.
Aby zrozumieć rekurencję, musisz zrozumieć rekurencję
Rekurencja, zwana także rekursją, to pojęcie używane zarówno w informatyce, jak i matematyce. Jest to proces, w którym np. funkcja wywołuje samą siebie. Najłatwiej będzie zrozumieć jej działanie, przechodząc od razu do kodu. Klasycznym przykładem działania rekurencji jest algorytm obliczania silni.
1 2 3 4 5 6 7 8 |
int silnia(int wartosc) { if(wartosc <= 1) { return 1; } else { return wartosc*silnia(wartosc-1); } } |
1 2 3 4 5 |
def silnia(n): if n <= 1: return 1 else: return n*silnia(n-1) |
W przypadku gdy argument wywołania tej funkcji jest większy od 1, funkcja zwraca argument, pomnożony przez wynik wywołania jej samej, z argumentem pomniejszonym o 1. Jak łatwo się domyślić, kolejne wywołania będą następować do momentu, gdy argument będzie miał wartość 1. W przypadku silni, wartość jeden jest tym co nazywamy w rekurencji warunkiem stopu. Wtedy to właśnie funkcja będzie miała możliwość „złożyć się” i zwrócić pełny wynik.
Na czym polega jednak owo „złożenie”? Patrząc bardziej technicznie, wywołanie jakiejkolwiek funkcji, polega na odłożeniu adresu aktualnie wykonywanej instrukcji na stosie i skok do nowej funkcji, którą mamy wykonać. Gdy otrzymamy już wynik, skaczemy z powrotem do odłożonego wcześniej adresu i kontynuujemy wykonywanie kolejnych instrukcji. Jak łatwo jest się domyślić, podczas wykonywania rekurencji, odkładamy na stosie kolejne adresy, do których będziemy wracać w momencie, gdy napotkamy warunek stopu w rekurencji. Po co jednak nam ta wiedza?
Rekurencja – czyli tam i z powrotem
Zrozumienie technicznego działania rekurencji jest niezwykle ważne dla znajomości kolejności wykonywania się instrukcji w funkcji rekurencyjnej. Weźmy chociażby przykład tych prostych programów:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//program prezentujacy kolejnosc //wykonywania instrukcji w rekurencji //Jan Żwirek #include <iostream> using namespace std; void funkcjaRekurencyjna(int argument) { if (argument <= 0) { cout << "Warunek stopu - wracamy!" << endl; return; } funkcjaRekurencyjna(argument - 1); cout << "Pozdrowienia z funkcji rekurencyjnej z argumentem " << argument << endl; } int main() { funkcjaRekurencyjna(4); system("pause"); return 0; } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package matura; public class Main { private static void funkcjaRekurencyjna(int n) { if (n <= 0) { System.out.println("Warunek stopu - wracamy!"); return; } funkcjaRekurencyjna(n - 1); System.out.println("Pozdrowienia z funkcji rekurencyjnej z argumentem " + n); } public static void main(String[] args){ funkcjaRekurencyjna(4); } } |
Python
1 2 3 4 5 6 7 8 |
def funkcjaRekurencyjna(n): if n <= 0: print("Warunek stopu - wracamy!") return funkcjaRekurencyjna(n-1) print("Pozdrowienia z funkcji rekurencyjnej z argumentem ", n) funkcjaRekurencyjna(4) |
Jak sądzicie, w przypadku wykonania tego programu, jak wyglądać będzie kolejność wyświetlanych komunikatów, a w którym miejscu zostanie wyświetlona informacja o napotkaniu warunku stopu? Odpowiedź może być dla niektórych nieco zaskakująca:O
1 2 3 4 5 |
Warunek stopu - wracamy! Pozdrowienia z funkcji rekurencyjnej z argumentem 1 Pozdrowienia z funkcji rekurencyjnej z argumentem 2 Pozdrowienia z funkcji rekurencyjnej z argumentem 3 Pozdrowienia z funkcji rekurencyjnej z argumentem 4 |
Czemu informacja o warunku stopu została wyświetlona na samym początku? Tak jak pisałem już wcześniej, w momencie wywołania funkcji, na stosie odkładany jest adres, po czym rozpoczęte zostaje wykonywanie instrukcji zawartych w funkcji. W momencie wywołania funkcji, instrukcje zawarte „pod” wywołaniem nie są wykonywane, aż do momentu powrotu. Tak więc w przypadku naszego programu, wywołaniem funkcji, które miało możliwość wyświetlenia jakiegokolwiek komunikatu w pierwszej kolejności, było ostatnie wywołanie z argumentem 0. Następnie nastąpił powrót do wywołania z argumentem 1, itd. Dokładniejszą kolejność wykonywania poszczególnych instrukcji znajdziecie na poniższej grafice:

Zagrożenia rekurencji
Rekurencja jest niezwykle przydatnym narzędziem, które m.in. znacząco zwiększa przejrzystość kodu. Nie bez powodu jest ona wykorzystywana w wielu algorytmach, czego przykładem jest chociażby, znane nam, przeszukiwanie drzewa binarnego, bądź wyliczanie ciągu Fibonacciego.
Jeśli jednak zaimplementujemy rekurencję nieuważnie, możemy doprowadzić do wielu nieprzyjemnych konsekwencji. Najczęstszym błędem jest brak bądź zły warunek stopu. W przypadku braku napotkania warunku stopu, nasz program będzie odkładał kolejne adresy na stosie wywołań, aż do momentu jego przepełnienia, co doprowadzi do znanego błędu Stack Overflow.

Dodatkowo, źle zaimplementowana rekurencja, może znacząco wpłynąć na spowolnić nasz program.
Podsumowanie
Zagadnienie rekurencji, to jedno z wielu które mogą okazać się przydatne na maturze z informatyki. Jeśli poszukujecie materiałów do nauki bądź sami chcecie się takimi podzielić, zapraszamy na naszą grupę maturalną. Link do niej znajdziecie po kliknięciu w poniższą grafikę:

Dobrnęliśmy więc do końca niniejszego wpisu. Mam nadzieję, że dzięki niemu zrozumieliście w pełni, czym jest rekurencja. Jeśli jednak chcecie pogłębić swoją wiedzę o rekurencji jeszcze bardziej, zapraszam was do tego wpisu.