Informatyka

Temat: Rekurencja

Rekurencja (znana także pod nazwą rekursji) jest terminem matematycznym, badaniem którego zajmuje się dział logiki matematycznej o nazwie teoria rekursji. Nie jest to pojęcie nowe, początki tego działu określa się bowiem na lata 30-te XX wieku. Obecnie rekurencja znajduje praktyczne zastosowanie nie tylko w matematyce, ale również w informatyce. Rekurencję łatwo jest również zaobserwować w naszym codziennym życiu.

Co to jest rekurencja?

Według definicji rekurencja to odwołanie się np. funkcji do samej siebie. Dokładna ilość tych odwołań nie ma zupełnie znaczenia, ponieważ już sam fakt wywołania jest podstawą do określenia funkcji jako rekurencyjnej.

Rozróżniamy dwa typy rekurencji:

rekurencja pośrednia – funkcja jest wywoływana przez inną funkcję, wywołaną (pośrednio lub bezpośrednio) przez samą funkcję;
rekurencja bezpośrednia – funkcja wywołuje samą siebie bezpośrednio wewnątrz ciała funkcji (rozwiązanie spotykane częściej).

Jaki jest cel stosowania rekurencji?

Rekurencja w matematyce wykorzystywana jest w celu rozwiązania konkretnego problemu. W sieci możemy znaleźć wiele przykładów zadań, które możemy rozwiązać właśnie za jej pomocą. Często przytaczanym przykładem jest definicja funkcji obliczającej wartość silni. Mechanizm rekurencji jest stosowany także dość często do definiowania i opisywania różnych algorytmów.
Rekurencja w informatyce jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Użycie opisu rekurencyjnego pozwala na przejrzysty, zwarty opis funkcji lub procedury używanej w kodzie.

Gdzie stosuje się rekurencję?

Rekurencja w informatyce, tak jak zresztą rekurencja w matematyce, stosowana jest bardzo często. Używa się jej np. w algorytmach sortowania(na przykład Quick Sort). Jedną z typowych sytuacji, jest przeszukiwanie struktury danych w postaci nieregularnego drzewa, np. plików XML. Istnieją także specyficzne algorytmy, w których wykorzystanie rekurencji jest czymś naturalnym. Dla przykładu trudno rozwiązać problem “wież Hanoi” inaczej niż w sposób rekurencyjny.

Jakie są wady rekurencji?

Okazuje się, że w informatyce zastosowanie rekurencji nie zawsze jest efektywne. Wręcz przeciwnie, na hasło rekurencja informatyka odpowiada: „uniknijmy, kiedy się da”. Każdorazowo zwiększa ona zapotrzebowanie programu na pamięć, ponieważ każde kolejne z rzędu wywołanie funkcji wymaga zapamiętania pewnych informacji, które są niezbędne do odtworzenia stanu sprzed wywołania. Jeżeli funkcje muszą wykonać się zbyt wiele razy, komputer może napotkać spore problemy podczas ich obliczania. Świetnym przykładem może być tutaj obliczanie silni dla 1000 lub też liczenie setnego elementu wspomnianego już ciągu Fibonacciego.
Stosując rekursję, musimy być także ostrożni w definiowaniu warunku końcowego. Jeżeli zdefiniujemy go niewłaściwie, możemy spowodować, że w naszym programie funkcja będzie się wywoływać w nieskończoność.

Kiedy zatem powinniśmy stosować rekurencję?

Pojawia się zatem pytanie, kiedy na hasło rekurencja informatyka może odpowiedzieć: tak.
Przede wszystkim w oczywistych jej zastosowaniach, gdy wiemy, że nie spowoduje ona dużego spadku wydajności naszej aplikacji. Zaletą rozwiązań rekurencyjnych jest przejrzystość kodu, więc możemy ją zastosować, kiedy nasz problem posiada bardzo proste rozwiązanie rekurencyjne, za to bardzo złożone rozwiązanie iteracyjne.
Należy pamiętać, że funkcje rekurencyjne mają mogą być powolne w działaniu i bardzo szybko zużyć znaczną ilość pamięci. Zatem wszędzie, gdzie nie widzimy przewagi zastosowania rekurencji, powinniśmy jej unikać. Niestety jej zlikwidowanie w napisanym już kodzie bywa czasami bardzo trudne.

Powinieneś umieć: