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.

REKURENCJA W TEORII

Takie same wyrażenie znajduje się w matematyce i istotnie odnosi się do tego samego. Termin ten 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ł (matma to ostatni przedmiot przy którym pozwoliłbym sobie głośno się wypowiadać). 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 przy większych algorytmach. Ze względu na ciągłe wywoływanie tej samej funkcji w funkcji, wszystkie poprzednie parametry formalne 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.

REKURENCJA W KODZIE ŹRÓDŁOWYM

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 dodatnich nie większych od zadanego N. Popatrzcie poniżej jak to wygląda:

#include <stdio.h>

#define FACTORIAL 10

unsigned long factorial(unsigned int n);

int main(void)
{
	printf("%d! = %u\n", FACTORIAL, factorial(FACTORIAL));
	getchar();
	
	return 0;
}

// rekurencja
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. 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 metodę 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 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 metoda, która ponownie rezerwuje kolejny "unsigned int" o nazwie "n", ale teraz przyjmujący wartość jeden! I teraz uważajcie! Wykonywane jest sprawdzenie 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):

Silnia jako rekurencja

Wzór rekurencyjny na silnię.

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. Mówię to ja, laik siedzący w tym fachu już parę ładnych lat. Kilka na widoku, jeszcze więcej w ukryciu.