Rekurencja (inaczej rekursja; ang. recursion), czyli odwoływanie się np. funkcji lub definicji do samej siebie.
Żeby zrozumieć rekurencję, trzeba najpierw zrozumieć – rekurencję…
Spis treści
- 1 Rekurencja – wprowadzenie
- 2 Co to jest rekurencja (rekursja)?
- 3 Rekurencyjny ciąg wywołań
- 4 Derekursywacja
- 5 Cechy algorytmów rekurencyjnych
- 6 Kiedy korzystać z rekurencji
- 7 Silnia a rekurencja (ang. factorial)
- 8 Ciąg Fibonacciego a rekurencja
- 9 Rekurencyjne wyświetlenie wszystkich katalogów
- 10 Rekursja – nie zawsze taka idealna
- 11 java.lang.StackOverflowError
- 12 Programowanie dynamiczne
- 13 Rekurencja ogonowa (ang. tail recursion)
- 14 Rekurencja ➿ – podsumowanie
- 15 20+ BONUSOWYCH materiałów z programowania
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
Zapiszmy teraz ten algorytm w wersji rekurencyjnej.
Zacznijmy od określenia warunków wyświetlenia podanej liczby:
- Jeżeli liczba jest większa od zera – to wywołaj metodę wyświetlania z liczbą pomniejszoną o jeden.
- 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.
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:
- 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 |
Więcej o ciągu Fibonacciego możesz przeczytać tutaj:
➡ ZOBACZ 👉: 🐚 Ciąg Fibonacciego – Fibonacci, Liczby Fibonacciego
Rekurencyjne wyświetlenie wszystkich katalogów
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
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.
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:
- Sprawdzamy, czy wcześniej nie obliczaliśmy już takiego problemu – i jeżeli tak to zwracamy wynik.
- 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:
- Może być tylko jedno wywołanie rekurencyjne w kodzie naszej metody i to wywołanie jest na samym końcu metody.
- 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!