Rekurencja w programowaniu. Jak działa rekurencja – wyjaśnienie.

Rekurencja w programowaniu – podstawy krok po kroku. Jak działa rekurencja ?

Ucząc się podstaw programowania w dowolnym języku, w końcu będziemy zmuszeni poznać znaczenie rekurencji. O ile większość programistów posiada wiedzę dotyczącą tego czym jest rekurencja, to rzadko z niej korzysta, lub nie bardzo wie jak można jej użyć. W tym poradniku postaram się wyjaśnić w prosty sposób jak działa rekurencja i jak z niej korzystać.

rekursja-300x240 Rekurencja w programowaniu. Jak działa rekurencja - wyjaśnienie.

Źródło: flickr,▓▒░TORLEY░▒▓

Czym jest rekurencja w programowaniu ?

Rekurencja w dowolnym języku programowania to nic innego jak wywołanie przez funkcję samej siebie. Na myśl przychodzi mi porównanie rekurencji do pętli, ponieważ jest ona również wywoływana określoną liczbę razy (do momentu, gdy zajdzie warunek stopu). I tak jest w rzeczywistości – rekurencja dość często zastępuje pętle w programowaniu.

for (int i = 0; i < 5; i++) {
 Console.WriteLine("Wywolanie" + i.ToString());
}

Moglibyśmy zastąpić powyższy fragment kodu, za pomocą rekurencyjnego wywołania funkcji:

static public void Wyswietl(ref int licznik){
   Console.WriteLine("Wywolanie" + licznik.ToString());
   licznik++;
   if (licznik < 5) {  Wyswietl(ref licznik); licznik++; }
}

Wywołanie funkcji będzie miało postać:  Wyswietl(ref licznik);

W efekcie otrzymamy ten sam rezultat tzn. na ekranie zostaną wyświetlone kolejno komunikaty :

  • Wywolanie 0
  • Wywolanie 1
  • Wywolanie 2
  • Wywolanie 3
  • Wywolanie 4

Oczywiście powyższy przykład jest prosty do wykonania i byłoby głupotą pisanie funkcji rekurencyjnej dla tak postawionego problemu. Większość zadań programistycznych można wykonać w klasyczny sposób za pomocą pętli, ale zdarzają się również takie, które wykonywane za pomocą klasycznych metod stają się mało czytelne.

Posłużę się teraz dość często spotykanym przykładem Silni (przypomnę, że jest to iloczyn wszystkich liczb naturalnych nie większych od n). Dla naszego przykładu weźmiemy sobie do policzenia 4! = 1 * 2 * 3 * 4 = 24.

I w tym wypadku wykonanie zadania za pomocą klasycznej pętli jest bardzo proste, ale naszym celem jest lepsze poznanie rekurencji – dlatego napiszemy funkcję rekurencyjną, która policzy silnię:

static public int Silnia(int podstawa) {
if (podstawa < 1) return 1;
 else return podstawa * Silnia(podstawa - 1);
        }

Jeżeli prześledzimy sposób w jaki obliczany jest wynik dla tak prostego kodu, to w przyszłości łatwiej nam będzie pisać funkcje wykorzystujące rekurencję.

Wspomniana powyżej funkcja Silnia(int podstawa), zwraca wynik: podstawa * Silnia(podstawa -1), a więc kolejne wywołania powodują że otrzymujemy:

  • 4 * Silnia(3)
  • 3 * Silnia(2)
  • 2* Silnia(1)
  • 1* Silnia(0)
  • Silnia(0) zwraca nam 1

A więc otrzymujemy równanie: 4 * 3 * 2 * 1 * 1 = 24, warto jednak dodać, że wynik liczony jest od końca – a więc de facto mamy 1 * 1 * 2 * 3 * 4.

Można to jeszcze przedstawić w ten sposób: 4 * Silnia(3) = 4 * 3 * Silnia(2) = 4 * 3 * 2 * Silnia(1) = 4 * 3 * 2 * 1 * Silnia (0) = 4 * 3 * 2 * 1 * 1

Mam nadzieję, że w tym krótkim wpisie chociaż trochę rozjaśniłem Wam działanie rekurencji. Warto w takich sytuacjach korzystać z debuggera, który pozwoli Ci prześledzić krok po kroku proces zdobywania rozwiązania. Jeżeli masz jakieś pytania, lub wątpliwości, a może chciałbyś żebym w którymś z wpisów na blogu poruszył inny temat związany z programowaniem to napisz w komentarzu 😉

Przeczytaj również

Szybszy WordPress, czyli skuteczny sposób na popra... Jeżeli Wasz blog, lub strona internetowa oparta o WordPress wczytuje się zbyt wolno, to prawdopodobnie jest źle, lub co gorsza w ogóle nie jest zoptym...
Sterowanie telewizorem za pomocą smartfonu. Mi Pil... Chciałbym się z Wami podzielić ciekawą aplikacją na systemy Android, która umożliwia sterowanie urządzeniami RTV za pomocą telefonu. Jeżeli zepsuł Ci ...
Fotomontaż online. Jak zrobić fotomontaż w interne... Przerabianie zdjęć w internecie. Fotomontaż online. Jak zrobić fotomontaż w internecie - ciekawe darmowe efekty graficzne, filtry na zdjęcia, ramki, w...
Chip z RFID dla wszystkich obywateli. Czy to możli... Czy już wkrótce każdy obywatel będzie miał obowiązkowo wszczepiany microchip RFID pod skórę? Czym jest ObamaCare i jakie ustawy przygotował rząd Stanó...

Jeden komentarz “Rekurencja w programowaniu. Jak działa rekurencja – wyjaśnienie.

Dodaj komentarz

Twój adres email nie zostanie opublikowany.