W ten piękny (przynajmniej w moim rejonie) czwartek witam Was z następnym tematem programistycznym dotyczącym pewnej techniki wielokrotnego wykonywania tych samych instrukcji. Zachowanie identyczne jak w pętli, ale samo w sobie to nie jest pętla. To tak zwana "rekurencja", nie mylić z "referencją" (o niej było tu)! Eleganckie tłumaczenie w teorii plus przykład kodu źródłowego w języku C.
| Tweet |
REKURENCJA W TEORII
Takie same wyrażenie znajduje się w matematyce i istotnie odnosi się do tego samego. Termin "recursion" oznacza "odwoływanie się do samego siebie". Może to być jakaś reguła, wniosek, ale także funkcja w programowaniu bo właśnie o tym będę teraz pisał. Jest to alternatywna postać pętli, która naturalnie ma swoje wady i zalety. Zacznę jak zawsze od wad, żebyście od razu mieli świadomość co to ze sobą niesie.
Rekurencja może wywołać przepełnienie stosu podczas operowania na dużych zbiorach danych (ang. "stack overflow"). Ze względu na ciągłe wywoływanie tej samej funkcji w funkcji, wszystkie poprzednie parametry aktualne muszą być zachowane w celu zachowania zgodności i możliwości "powrotu" do początku ciągu wywołań. Ponadto, większość twierdzi że działa wolniej niż podejście iteracyjne. Patrząc na przechowywanie wszystkich zmiennych na stosie jest to całkiem prawdopodobne.
Zalety rekurencji? W większości przypadków pozwala na dużo wygodniejszy zapis w kodzie źródłowym. Wygodniejszy, to znaczy krótszy, czytelniejszy i bardziej zwięzły. Ponadto, pewne wyjątkowe problemy programistyczne mogą zostać rozwiązane wyłącznie przy użyciu rekurencji, jak na przykład funkcja Ackermanna. Nie ma tego za wiele, ale wszystko w informatyce ma plusy i minusy. Nie inaczej jest tutaj.
PRZYKŁAD KODU ŹRÓDŁOWEGO
Rozpatrzmy następujący kod źródłowy. Klasyczny przykład prezentowany przy rekurencji to między innymi silnia. Silnia to iloczyn wszystkich liczb naturalnych nie większych od zadanego N. Popatrzcie poniżej jak to wygląda:
#include <stdio.h>
#define N 10
unsigned long factorial(unsigned int n);
int main(void)
{
printf("%d! = %u\n", N, factorial(N));
getchar();
return 0;
}
unsigned long factorial(unsigned int n)
{
if(n <= 1)
{
return 1;
}
else
{
return n*factorial(n - 1);
}
}Po przyjrzeniu się wpisom łatwo dostrzec funkcję obliczającą silnię rekursywnie. Typy "unsigned int" i "unsigned long" są z tego powodu, iż silnia (ang. "factorial") nie obejmuje liczb ujemnych. Ponadto, przy większej silni wynik rośnie bardzo gwałtownie i to jest kolejny powód stojący za zmiennymi bez znaku. Zmniejszamy szansę na przekroczenie zakresu liczb całkowitych. Stosując typ "unsigned" pozbywamy się liczb ujemnych w zamian za podwójnie większy zakres liczb dodatnich (zobaczcie ten artykuł jeśli nie wiecie dlaczego tak się dzieje).
Zaglądając do funkcji, widzimy jak wygląda rekurencja w języku C. Według jej treści, wykonywane jest zupełnie inne obliczenie w zależności od aktualnej wartości parametru formalnego o nazwie "n". Gdy jest większy od 1, to dosłownie zwracamy funkcję pomnożoną przez "n" a bardziej po ludzku, to zwracamy wyrażenie w postaci "n" przemnożonego przez funkcję obliczającą silnię w sposób rekursywny przekazując "n" o jeden mniejsze. Gdy "n" "spadnie" do jedynki, zwracana jest wartość jeden, natomiast to NIE JEST ostateczny zwrot wartości funkcji.
REKURENCJA ZA KULISAMI
Jeszcze raz po kolei. Wchodzimy do funkcji, przekazujemy jej parametr, powiedzmy 3, zatem chcemy obliczyć 3!, tak? Oto co się dzieje od tej chwili w komputerze:
POZIOM I
Pierwszy etap to zarezerwowanie pamięci dla "n" równego 3. Następuje sprawdzenie przez instrukcję warunkową czy "n" jest mniejsze bądź równe 1. To jest fałsz, zatem program przechodzi do bloku "else" i zwraca wyrażenie "n*factorial(n - 1)". W naszym przypadku to będzie podstawione jako "3*factorial(2)", a matematycznie, 3*2!. Idziemy dalej.
POZIOM II
Rekurencja cały czas przechowuje poprzednią zmienną "n" równą 3, nie usuwa jej z pamięci. Alokuje pamięć dla CAŁKOWICIE ODRĘBNEJ zmiennej "n" przyjmującej wartość 2. Znowu jest sprawdzenie czy "n" jest mniejsze bądź równe 1 i znowu wyrażenie jest nieprawdziwe! Zatem, ponownie zwraca wyrażenie "n*factorial(n - 1)" będące teraz w postaci "2*factorial(1)", czyli 2*1!.
POZIOM III
Zostawiając na stosie poprzednie "n-ki", wywoływana jest po raz kolejny ta sama funkcja, która ponownie rezerwuje kolejny "unsigned int" o nazwie "n", ale teraz przyjmujący wartość jeden! I teraz uważajcie! Instrukcja warunkowa weryfikuje czy "n" jest mniejsze bądź równe jeden. Jest równe, zatem wyrażenie jest prawdziwe i zwraca wartość jeden. Zwalniana jest pamięć "trzymająca" "n" równe jeden.
POZIOM II
Rekurencja "wraca" do poprzedniego poziomu poznawszy odpowiedź na pytanie ile wynosi 1!. Jest to jeden, zatem już "wie" ile wynosi 2*1!. Zwraca wynik 2 w taki sam sposób do jakiego się przyzwyczailiśmy, czyli "za kulisami" wyrażenie przekształca się w "return 2". Zwalnia pamięć dla zmiennej "n" równej 2.
POZIOM I
I tak program wraca do początku wznawiając działanie od "wyjścia" z wywołania funkcji "factorial(n - 1)" poznawszy odpowiedź na pytanie ile to jest 2!. Zostaje mu ostatnie działanie do policzenia: 3*2!. Wynikiem jest sześć, usuwa zmienną "n" równą 3, a wynik DOPIERO TERAZ jest zwracany.
Prościej już wyjaśnić się tego nie da. Jeszcze jedna wątpliwość do rozwiania. Może niektórych dziwić, że jest porównanie do jedynki mimo tego, że wzór na silnię w sposób rekurencyjny prezentuje zwrócenie wartości jeden dla 0! (zero silnia):
 |
Wzór rekurencyjny na silnię.
Źródło: Wikipedia
Zgodnie z rekurencyjną definicją silni, wyraz jest równy 1 przy 0! (zero silnia). Ponieważ jednak 1! nie wpływa w żaden sposób na wynik, możemy "popchnąć" wartość o jeden do góry oszczędzając na jednej iteracji, stąd sprawdzenie czy "n" jest mniejsze bądź równe jeden. Nikt z matematyków się nie pogniewa.
To na razie wszystko w tym artykule. Opanowanie rekurencji przyda się Wam wielokrotnie. Piszę to ja, laik siedzący w tym fachu dopiero parę ładnych lat. Kilka na widoku, jeszcze więcej w ukryciu.