Rekurencja ➿ rekursja ➿ rekurencja

Rekurencja, rekursja, rekurencja

Rekurencja (inaczej rekursja; ang. recursion), czyli odwoływanie się np. funkcji lub definicji do samej siebie.

Żeby zrozumieć rekurencję, trzeba najpierw zrozumieć – rekurencję…

Rekurencja – wprowadzenie

Z tego materiału dowiesz się:

  • Czym jest rekurencja?
  • Jak wykonać rekurencję?
  • Czym jest rekurencyjny ciąg wywołań?
  • Jakie istnieją sposoby na optymalizację algorytmu rekurencyjnego?

Co to jest rekurencja (rekursja)?

W praktyce o funkcji rekurencyjnej mówimy, jeżeli logika funkcji polega między innymi na wywołaniu samej siebie.

Za pierwszym razem brzmi to trochę jak nieskończona pętla wywołań lub przekładając to na bardziej uniwersalny język jak pies, który goni swój ogon i próbuje go złapać, jednak nigdy mu się to nie udaje… 🐕

Czasami rzeczywiście może się zdarzyć, że taka metoda zapętli się i nie zwróci prawidłowego wyniku – co nie jest tak naprawdę pożądanym rezultatem. Dlatego tak ważne jest, by dobrze zaprojektować warunki końcowe, po których spełnieniu metoda ma przestać wywoływać samą siebie.

Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nierekurencyjnego), który zakończy jej działanie.

Zobaczmy 🔎 to na prostym przykładzie.
Naszym zadaniem jest wyświetlenie rekurencyjnie liczb z przedziału od 0 do 10.

Iteracyjne podejście

W standardowym iteracyjnym podejściu moglibyśmy w tym celu wykorzystać pętlę for oraz dekrementację.

for (int i = 10; i >= 0; i--) {
	System.out.println(i);
}
  • Pętla zaczyna się od wartości licznika 10.
  • W ciele metody wyświetlamy licznik.
  • Następnie zmniejszamy go o 1.
  • Jeżeli licznik dalej jest większy bądź równy 0 – to wykonujemy kolejną iterację pętli.

Więcej o podejściu iteracyjnym i iteracji możesz przeczytać tutaj:

➡ ZOBACZ 👉: Iteracja, iteracje | powtarzanie w programowaniu vs Rekurencja ➿

Rekurencyjne podejście

Recursion – Rekurencja Algorytm

Zapiszmy teraz ten algorytm w wersji rekurencyjnej.

Zacznijmy od określenia warunków wyświetlenia podanej liczby:

  1. Jeżeli liczba jest większa od zera – to wywołaj metodę wyświetlania z liczbą pomniejszoną o jeden.
  2. W przeciwnym wypadku – nie rób nic (warunek bazowy).
display(10);

void display(int i) {
	System.out.println(i);

	if (i > 0) {
		display(i - 1);
	}
}

Rekurencyjny ciąg wywołań

Wynik działania programu w obu przypadkach będzie dokładnie taki sam – w kolejnych liniach zostaną wyświetlone liczby od 10 do 0.

Natomiast sam stos wywołań dla podejścia rekurencyjnego wyglądałby całkowicie inaczej:

display(10);
    10
    display(9);
        9
        display(8);
            8
            display(7);
                7
                display(6);
                    6
                    display(5);
                        5
                        display(4);
                            4
                            display(3);
                                3
                                display(2);
                                    2
                                    display(1);
                                        1
                                        display(0);
                                            0

Kolejne wywołania takiej funkcji nazywamy rekurencyjnym ciągiem wywołań.
Bardzo ważne jest poprawne określenie warunku bazowego (nierekurencyjnego), który zakończy wywołania rekurencyjne – w tym przypadku jest to if (i > 0), które musi być niespełnione, aby zakończyć rekurencję. Jeżeli źle zdefiniujemy ten warunek, to nasza aplikacja się zwyczajnie zapętli.

Derekursywacja

Gdybyśmy chcieli przeprowadzić operację odwrotną – czyli zamienić algorytm rekurencyjny na iteracyjny – mówimy wtedy o derekurencji.
Derekursywacja – czyli przekształcenie algorytmu rekursyjnego w odpowiadający mu funkcjonalnie algorytm iteracyjny.

Cechy algorytmów rekurencyjnych

  • Zakończenie algorytmu nie jest jasno określone – mamy, tylko warunek bazowy, który mówi nam, kiedy mamy skończyć rekurencję.
  • Ogólny, bardziej rozbudowany problem zostaje rozbity na mniejsze, elementarne problemy, które łatwiej jest rozwiązać.
  • Problem jest upraszczany tak długo, aż dojdziemy do warunku bazowego, który jest na tyle trywialny, że nie da się już go rozdrobnić i zwyczajnie podajemy jego wynik.
  • Główny problem przedstawiamy jako „mniejszą wersję” tego samego problemu.

Kiedy korzystać z rekurencji

Skoro wiele problemów możemy rozwiązać iteracyjne oraz rekurencyjne, to w takim przypadku kiedy zdecydować się na który sposób?

Zazwyczaj wybieramy rekurencję, kiedy:

  • Rozwiązywany problem da się zredukować do łatwiejszego podproblemu, który można dalej upraszczać – główny problem da się przedstawić jako „mniejszą wersję tego samego problemu”.
  • Możemy znaleźć bazowy przypadek, którego dalej już nie redukujemy.
!!Pamiętaj!! Rekurencja może być wolniejsza od wersji iteracyjnej ze względu na konieczność dodatkowych wywołań metody – może być, co nie znaczy, że zawsze tak jest – jednak warto zwrócić uwagę na wydajność obu rozwiązań.

Silnia a rekurencja (ang. factorial)

Przyjrzyjmy się teraz kilku praktycznym przykładom wykorzystania rekurencji.

Silnia (ang. factorial) z liczby N to iloczyn wszystkich liczb naturalnych dodatnich nie większych niż liczba N, czyli silnia z 7 to:

7! = 7*6*5*4*3*2*1

można to jednak zapisać również jako:

7! = 7 * 6!

Natomiast ten przypadek – bardzo łatwo jest już zapisać w formie funkcji rekurencyjnej:


int factorial(int n) {
	if (n <= 0) {
		return 1;
	}

	return n * factorial(n - 1);
} 

Wartości silni dla kolejnych 10 liczb:
0 => 1
1 => 1
2 => 2
3 => 6
4 => 24
5 => 120
6 => 720
7 => 5040
8 => 40320
9 => 362880
10 => 3628800

Ciąg Fibonacciego a rekurencja

Ciąg Fibonacciego – to kolejny problem, który bardzo często rozwiązywany jest w sposób rekurencyjny.

Co to jest Ciąg Fibonacciego?

Ciąg Fibonacciego – to ciąg liczb naturalnych w którym:

Ciąg Fibonacciego – wzór rekurencyjny

Ciąg Fibonacciego – wzór rekurencyjny

  • Pierwszy wyraz jest równy 0;
  • Drugi wyraz jest równy 1;
  • Każdy kolejny element jest sumą dwóch poprzednich.

Przykładowo 6. element Ciągu Fibonacciego będzie miał wartość:

Element ciągu 0 1 2 3 4 5 6
Wartość 0 1 1 2 3 5 8
Fibonacci – rekurencja

Fibonacci – rekurencja

Więcej o ciągu Fibonacciego możesz przeczytać tutaj:

➡ ZOBACZ 👉: 🐚 Ciąg Fibonacciego – Fibonacci, Liczby Fibonacciego

Rekurencyjne wyświetlenie wszystkich katalogów

Rekurencja katalogi

Kolejnym bardzo wyraźnym przykładem zastosowania rekurencji jest rekurencyjne wyświetlanie i przeszukiwanie katalogów w systemie plików.

Mamy główny katalog – np. w systemie Unix „/” – a w nim podkatalogi: /tmp, /run itp. Każdy z tych katalogów znowu ma swoje podkatalogi itp.

Dlatego chcąc np. znaleźć plik, przeszukując cały dysk, możemy:

  • Wejść do głównego katalogu.
  • Sprawdzić, czy nie ma tam naszego pliku.
  • Wyświetlić listę wszystkich podkatalogów i dla nich odpalić ten sam algorytm 😉

Rekursja – nie zawsze taka idealna

Rekurencja – jak każde inne narzędzie ma swoje plusy i minusy – a co za tym idzie, nie zawsze jest idealnym rozwiązaniem problemu.

Przyjrzyjmy się teraz kilku potencjalnym problemom, które musimy zaadresować w kontekście podejścia rekurencyjnego.

  • Skomplikowane problemy rekurencyjne mogą znacząco wpłynąć na wykorzystanie zasobów – ponieważ wymaga zapamiętywania między innymi adresów powrotu z wywołań rekurencyjnych.
  • Kompletnie niezależne rozwiązywanie podproblemów – tak że czasem jeden problem jest rozwiązywany wielokrotnie. Prześledź np. stos wywołań dla ciągu Fibonacciego dla 4 elementu – fib(2) zostaje obliczone dwukrotnie. Rozwiążemy za chwilę ten problem, korzystając z programowania dynamicznego.
  • Przy źle zdefiniowanym warunku kończącym istnieje ryzyko zapętlenia wywołań. Może to doprowadzić do przepełnienia stosu i pojawienia się bardzo niechcianego wyjątku StackOverflowError.

java.lang.StackOverflowError

Jeżeli korzystając z rekurencji, źle zdefiniujemy warunek bazowy i doprowadzimy do zapętlenia się algorytmu – można powiedzieć, że mleko 🥛 się już rozlało i nasz algorytm nie działa poprawnie.

Jednak taka sytuacja niesie za sobą jeszcze inne negatywne konsekwencje – prędzej czy później skończą nam się zasoby wykorzystywane na stosie wywołań (ang. stack) i JVM (ang. java virtual machine) poinformuje nas o tym niechlubnym błędem: java.lang.StackOverflowError.

Recursion – Rekurencja StackOverflowError

Więcej na ten temat pisałem w kontekście stosu i LIFO – dlatego zachęcam do zapoznania się z poniższym tekstem:

➡ ZOBACZ 👉: Stos (Stack) – 7+ tajników implementacji LIFO 

➡ ZOBACZ 👉: Stos – StackOverflowError

Programowanie dynamiczne

Programowanie dynamiczne jest jednym ze sposobów na optymalizację złożonych algorytmów rekurencyjnych.

Sama idea jest dosyć prosta i polega na identyfikacji podproblemów w ten sposób, by ich obliczenia wykonywać tylko raz.

Zobaczmy to na przykładzie:

int fibRecDP(int i) {
	if (i == 0) {
		return 0;
	}
	if (i == 1) {
		return 1;
	}

	if(results.containsKey(i)){
		return results.get(i);
	}

	int result = fibRecDP(i - 2) + fibRecDP(i - 1);
	results.put(i, result);

	return result;
}

W tym przykładzie rozbudowaliśmy pierwotną metodę rekurencyjną o dwie rzeczy:

  1. Sprawdzamy, czy wcześniej nie obliczaliśmy już takiego problemu – i jeżeli tak to zwracamy wynik.
  2. Przechowujemy obliczenia w pomocniczej mapie.

Dzięki tej prostej optymalizacji zużyjemy odrobinę więcej pamięci na przechowanie wyników, jednak znacząco skrócimy czas obliczeń dla większej ilości elementów ciągu Fibonacciego.

Rekurencja ogonowa (ang. tail recursion)

Rekurencja ogonowa jest kolejnym sposobem na optymalizację algorytmów rekurencyjnych.
Tym razem musimy jednak przeorganizować nasz algorytm w taki sposób, by pomóc kompilatorowi odpowiednio go zoptymalizować.

Rekurencja ogonowa wymusza na nas spełnienie dwóch warunków:

  1. Może być tylko jedno wywołanie rekurencyjne w kodzie naszej metody i to wywołanie jest na samym końcu metody.
  2. Wyniku kolejnego wywołania nie można modyfikować – więc potrzebujemy dodatkowej zmiennej na przechowanie aktualnego wyniku, który na sam koniec zostanie zwrócony.

Prawda, że proste? 😏

To spróbujmy przemodelować nasz algorytm ciągu Fibonacciego:

long fibRecTail(int n, long a, long b) {
	if (n == 0) {
		return b;
	}

	return fibRecTail(n - 1, a + b, a);
}

Na pierwszy rzut oka obie wersje wyglądają bardzo podobnie – jednak te drobne różnice pozwalają na bardzo znaczącą optymalizację.

Jeżeli wykorzystywany przez nas kompilator obsługuje optymalizację rekurencji ogonowej (większość współczesnych kompilatorów to robi) – zauważy wtedy, że nie ma potrzeby zapisywania ramki na stosie, ponieważ i tak później ma zwrócić wynik kolejnego wywołania. Dzięki tej drobnej różnicy stos wywołań nie rośnie już przy każdym kolejnym zagnieżdżeniu, a ma stały rozmiar.

Rekurencja ➿ – podsumowanie

W ramach tego materiału przećwiczyliśmy tworzenie algorytmów rekurencyjnych. Zapoznaliśmy się również z 2 sposobami na optymalizację algorytmu rekurencyjnego – rekurencją ogonową i programowaniem dynamicznym.

Jeżeli spodobał Ci się ten materiał lub jeśli dopiero co zaczynasz swoją przygodę z programowaniem i chcesz dobrze wejść, w świat deweloperów zapraszam Cię do zapoznania się z moim programem dotyczącym Javy:

➡ ZOBACZ 👉: Java od podstaw


20+ BONUSOWYCH materiałów z programowania

e-book – „8 rzeczy, które musisz wiedzieć, żeby dostać pracę jako programista”,
e-book – „Java Cheat Sheet”,
checklista – „Pytania rekrutacyjne”
i wiele, wiele wiecej!

Jak zostać programistą

No comments
Share:

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *