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.

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?



O rekurencyjnych problemach i ich rozwiązaniach poczytasz więcej tutaj

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++

Java

Python

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

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.

You Might Also Like
Dodaj komentarz

icon