Rekurencja
Pojęcie rekurencji
Wiele sposobów rekurencyjnego rozwiązywania problemów ma pewne elementy wspólne. Gdy metoda rekurencyjna jest wywoływana w celu rozwiązania problemu, najczęściej potrafi jedynie rozwiązać przypadek najprostszy, nazywany przypadkiem bazowym. Jeśli metoda zostanie wywołana dla przypadku bazowego, po prostu zwraca wynik. Jeśli metoda zostanie wywołana z bardziej złożonym problemem, dzieli go na dwie części: fragment, z którym „wie”, jak sobie poradzić, i fragment, z którym „nie wie”, jak sobie poradzić. Aby uczynić rekurencję możliwą, drugi przypadek musi dać się przedstawić jako prostsza lub mniejsza wersja. Ponieważ nowy problem podobny jest do pierwotnego, metoda wywołuje nową kopię samej siebie, aby obsłużyć mniejszy problem — to tak zwane wywołanie rekurencyjne, nazywane również krokiem rekurencyjnym.
Krok rekurencyjny najczęściej zawiera instrukcję return, ponieważ jego wynik będzie łączony z częścią problemu, która jest znana. Zasada podziału problemu na mniejsze części to podejście typu dziel i rządź. Krok rekurencyjny wykonuje się, gdy oryginalne wywołanie metody pozostaje aktywne (nie zakończyło się). Może to doprowadzić do wielu wywołań rekurencyjnych, bo metoda dzieli każdy nowy podproblem na dwa koncepcyjnie mniejsze problemy. Aby udało się w pewnym momencie przerwać ciąg rekurencyjnych wywołań, sekwencja coraz to mniejszych problemów musi dążyć do przypadku bazowego. Gdy metoda rozpozna przypadek bazowy, zwróci wynik do wcześniejszej kopii metody. Ciąg powrotów spowoduje przejście aż do oryginalnej
metody, która zwróci wynik kodowi wywołującemu.
Rekurencyjna metoda może wywołać inną metodę, a dopiero ta metoda spowoduje wywołanie rekurencyjne. To tak zwane pośrednie wywołanie rekurencyjne lub rekurencja pośrednia. Przykładowo metoda A wywołuje metodę B, która to
znowu wywołuje metodę A. To rekurencja, ponieważ drugie wywołanie metody A ma miejsce, gdy pierwsze wywołanie metody A jest nadal aktywne — pierwsze użycie A jeszcze się nie zakończyło (bo czeka na wynik działania metody B) i nie zwróciło wyniku do kodu wywołującego A.
Rekurencyjna struktura folderów
Aby lepiej zrozumieć pojęcie rekurencji, przyjrzyjmy się przykładowi, który powinien być dobrze znany użytkownikom komputerów — jest to rekurencyjna definicja folderów w komputerowym systemie plików. Komputer najczęściej przechowuje powiązane ze sobą pliki w konkretnym folderze (katalogu). Folder może być pusty, może zawierać pliki lub może zawierać inne foldery (nazywane
podfolderami lub podkatalogami). Każdy z tych podfolderów, może zawierać inne pliki lub foldery. Jeśli chcemy wyświetlić zawartość każdego pliku w folderze (w tym pliki z podfolderów), musimy napisać metodę, która najpierw wyświetli pliki aktualnego folderu, a następnie w sposób rekurencyjny wywoła listy plików z podfolderów. Przypadek bazowy ma miejsce, gdy osiągniemy
miejsce, w którym folder nie ma żadnych podfolderów. Oznacza to, że nie jest potrzebna żadna dodatkowa rekurencja.
Przykład użycia rekurencji — silnia
Napiszmy program rekurencyjny wykonujący bardzo popularne obliczenia matematyczne. Weźmy silnię liczby całkowitej n zapisywaną jako n! (wymawiamy „n silnia”), która jest wynikiem iloczynu:
gdzie 1! wynosi 1, a 0! jest zdefiniowane jako 1. Oznacza to, że 5! to wynik iloczynu 5 · 4 · 3 · 2 · 1, czyli 120. Silnię liczby całkowitej number (gdzie number 0) jesteśmy w stanie wyliczyć iteracyjnie (bez rekurencji) za pomocą instrukcji for w sposób następujący:
for (int counter = number; counter >= 1; counter--) {
factorial *= counter;
}
Deklarację rekurencyjną silni dla wartości większych od 1 jesteśmy w stanie zdefiniować, zauważając tę oto zależność:
Przykładowo 5! jest zdefiniowane jako 5 · 4!, co pokazuje następujący przykład:
5! = 5 · (4 · 3 · 2 · 1)
5! = 5 · (4!)
Wyliczenie 5! można przeprowadzić w sposób przedstawiony na rysunku 18.2. Rysunek 18.2a pokazuje wywołania rekurencyjne prowadzące aż do 1! (przypadek bazowy), które zwraca 1 i kończy rekurencję. Rysunek 18.2b pokazuje wartości zwracane z każdego wywołania rekurencyjnego do kodu wywołującego aż do uzyskania wyniku końcowego.
Rysunek 18.2. Rekurencyjne wyliczenie 5!
Na rysunku 18.3 używamy rekurencji do wyliczenia i wyświetlenia silni dla liczb całkowitych od 0 do 21. Metoda rekurencyjna factorial (wiersze od 6. do 13.) sprawdza najpierw warunek zakończenia (wiersz 7.). Jeśli number jest mniejsze lub równe 1 (przypadek bazowy), factorial zwraca 1, bo nie są konieczne żadne rekurencje. (Warunkiem wstępnym wywołania metody factorial jest przekazanie wartości nieujemnej). Jeśli number jest większe od 1, wiersz 11. wyraża problem jako iloczyn number i rekurencyjnego wywołania factorial z wartością number - 1, czyli nieco mniejszym problemem niż pierwotne factorial(number).
2 // Rekurencyjna metoda factorial
3
4 public class FactorialCalculator {
5 // Rekurencyjna metoda factorial (zakłada, że parametr jest >= 0)
6 public static long factorial(long number) {
7 if (number <= 1) { // Sprawdzenie przypadku bazowego
8 return 1; // Przypadki bazowe: 0! = 1 i 1! = 1
9 }
10 else { // Krok rekurencyjny
11 return number * factorial(number - 1);
12 }
13 }
14
15 public static void main(String[] args) {
16 // Obliczenie silni od 0 do 21
17 for (int counter = 0; counter <= 21; counter++) {
18 System.out.printf("%d! = %d%n", counter, factorial(counter));
19 }
20 }
21 }
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
...
12! = 479001600 // 12! powoduje przepełnienie dla zmiennych typu int
...
20! = 2432902008176640000
21! = -4249290049419214848 // 21! powoduje przepełnienie dla zmiennych typu long
Rysunek 18.3. Rekurencyjna metoda factorial
Typowy błąd programistyczny
Pominięcie przypadku bazowego lub niepoprawne zapisanie rekurencji w sposób, który nie będzie zbliżał jej do przypadku bazowego, spowoduje błąd logiczny nazywany rekurencją nieskończoną, czyli rekurencją działającą aż do wyczerpania się pamięci operacyjnej lub przepełnienia stosu wywołań metod. Błąd ten jest bardzo podobny do problemu pętli nieskończonej w rozwiązaniach iteracyjnych (czyli bez rekurencji).
Metoda main (wiersze od 15. do 20.) wyświetla silnie dla wartości od 0 do 211. Wywołanie metody factorial ma miejsce w wierszu 18. Metoda otrzymuje parametr typu long i zwraca wynik typu long. Wyniki programu wzrastają bardzo szybko. Użyliśmy typu long (który potrafi reprezentować stosunkowo duże liczby całkowite), więc program potrafi wyliczyć silnie większe niż 12!. Niestety metoda factorial bardzo szybko tworzy coraz to większe wartości, więc przekraczamy największą wartość long przy próbie wyliczenia 21!, co ilustruje ostatni wiersz wyników.
Z powodu ograniczeń typów liczb całkowitych do dalszego wyliczania silni niezbędne są typy float lub double. Prowadzi to do pewnych słabości niektórych języków programowania — nie można w nich łatwo wprowadzić nowych typów pozwalających obsłużyć unikatowe wymagania aplikacji. Wcześniej pokazaliśmy, że Java to język rozszerzalny, który potrafi obsłużyć dowolnie duże
liczby całkowite, jeśli zachodzi taka potrzeba. Pakiet java.math oferuje klasy BigInteger i BigDecimal pozwalające obsługiwać liczby o dowolnej precyzji i długości. Więcej informacji na temat tych klas znajdziesz na stronach:
http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html
http://docs.oracle.com/javase/8/docs/api/java/math/BigDecimal.html
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
