3. Kilka słów o rekurencji
Z ciała (kodu) metody możemy wywołać ją samą. Takie wywołanie nazywa się wywołaniem rekurencyjnym. Rekurencyjne wywołanie metody polega na wywołaniu tej metody z jej własnego ciała
Pojęcie rekurencji będzie bardziej obszernie, szczegółowo i w ciekawszych zastosowaniach omawiane w trakcie zajęć z przedmiotu
"Algorytmy i struktury danych". Tutaj ograniczymy się tylko kilkoma uwagami,
tak by można było czasem, na intuicyjnym poziomie, zastosowac odwołania rekurencyjne. public class Recurs { public static void show1(int i) { System.out.println("show1 " + i); if (i > 10) return; show1(i+1); } public static void main(String[] args) { show1(1); } } show1 1
show1 2 show1 3 show1 4 show1 5 show1 6 show1 7 show1 8 show1 9 show1 10 show1 11 Tutaj sprawa jest dość prosta i do przewidzenia. Wywołanie show1(1) z metody main uruchamia łańcuch wywołań rekurencyjnych. Każde wywołanie wyprowadza przekazany argument, po czym sprawdzany jest warunek (i>10), i dopóki jest on nieprawdziwy ponownie wywoływana jest metoda show1 z powiększoną o 1 wartością argumentu. Np. po wypisaniu 1 (pierwsze wywołanie) wywoływana jest metoda show1 z argumentem 2 = 1+1, ten argument jest wypisywany, wywoływana jest metoda show1 z argumenten 3 (= 2+1), ten jest wypisywany itd. aż w "wewnętrznym wywołaniu" show1 argument nie osiągnie wartości 11. Wtedy - po jej wypisaniu - warunek okaże się prawdziwy i dopiero teraz sterowanie zwrócone zostanie do metody main. Przy wywołaniach rekurencyjnych należy zapewnić warunek, którego spełnienie
zakończy łańcuch rekurencji i spowoduje zwrócenie sterowania do miejsca,
w którym po raz pierwszy wywołano metodę rekurencyjną
Zobaczmy drugi fragment kodu. Tym razem wywołamy z metody main - za pomocą odwołania show2(1) - następującą metodę. public static void show2(int i) { if (i > 10) return; show2(i+1); System.out.println("show2 " + i); }
show2 10
show2 9 show2 8 show2 7 show2 6 show2 5 show2 4 show2 3 show2 2 show2 1 Wynik działania tej metody może wydać się nieco zaskakujący.
Co się dzieje? Wywołanie show2(1) przekazuje jako argument 1, i z wnętrza
show2 następuje wywołanie show2 z argumentem 2 (1+1). W tym momecie wykonanie
dalszego kodu metody zostaje wstrzymane. Wykonanie zaczyna się od początku!
Zaczyna działać jakby "nowy egzemplatrza" metody show2. Tym razem z nowym
argumentem (2). I tak dalej. Gdy parametr i osiągnie wartość
11 powinna zadziałać instrukcja return. Ale najpierw muszą być "dokończone"
wszystkie poprzednie, "wstrzymane", wykonania metody show2. Ostatnie było
z argumentem 10. Zatem wyprowadzona zostanie liczba 10 i wykonanie "tego
egzemplarza" metody zostanie zakończone. Poprzedzało go wywołanie show2 z
argumentem 9 - zostanie więc dokończone itd., aż dojdziemy do pierwszego
wywołania show2 (z argumentem 1). Po zakończeniu wykonania metody z tym argumentem
zostanie wykonana instrukcja return i sterowanie wróci do main. public class Recurs { public static int sum(int n) { if (n == 1) return 1; else return n + sum(n-1); } public static void main(String[] args) { System.out.println(sum(100)); } }
Wyprowadzi: 5050 (Gauss policzył to szybciej!) Bardzo często rekurencja będzie jednak prostsza do oprogramowania, bowiem
odzwierciedla ona bezpośrednio pewien sposób rozumowania: nie wiemy jak rozwiązać
cały problem, na którego rozwiązanie składa się powiedzmy n kroków, ale
wiemy jak wykonać jeden krok, gdy już n-1 poprzednich zostało wykonane. I
to właśnie możemy (dość prosto) zapisać w postaci rekurencyjnej.
Trzeba jednak też wiedzieć o tym, że nie zawsze podejście rekurencyjne prowadzi
do efektywnych algorytmów; czasami iteracyjne wersje rozwiązania jakichś
problemów są wielokrotnie szybsze od rekurencyjnych, a nawet - przy ograniczeniach
na pamięć operacyjną i moc procesora - jedynie możliwe. Sztandarowym przykładem
jest tu rekursywne oprogramowanie wyliczenia liczb ciągu Fibonacciego. 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ... Liczby Fibonacciego mają niezwykle ciekawe właściwości. Nader często ciągi
takich liczb obserwowane są w zjawiskach naturalnych, mają też intrygujące
właściwości matematyczne. Więcej na ten temat zobacz na stronie Rona Knotta z Uniwersytetu w Surrey. int fib(int n) { if (n < 2) return n; else return fib(n-1) + fib(n-2); }
Jednak wraz ze zwiększaniem wartości n czas obliczeń za pomocą tej metody rośnie katastrofalnie. int fib(int n) { System.out.println("Wywołanie fib z argumentem " + n); int wynik = 0; if (n < 2) wynik = n; else wynik = fib(n-1) + fib(n-2); System.out.println("Zwrot wyniku: " + wynik); return wynik; }
i analizując wydruk po wywołaniu tej metody z jakimś argumentem (np. 8) -
zobaczymy, że wielokrotnie powtarzają się rekurencyjne wywołania metody fib
z tymi samymi argumentami i wielokrotnie powtarzają się zwroty tych samych wyników. public class ShowFibRec { int[] calls; ShowFibRec(int n) { calls = new int[n+1]; fib(n); for(int i=0; i <= n; i++) System.out.println("Liczba wywołań fib z argumentem " + i + " " + calls[i]); } int fib(int n) { calls[n]++; if (n < 2) return n; else return fib(n-1) + fib(n-2); } public static void main(String[] args) { int n = Integer.parseInt(args[0]); new ShowFibRec(n); } }
Po kompilacji, możemy porównać liczbę "powtórnych" wywołań dla różnych n podawanych jako argument wywołania, np. 8 i 20.
Ze względu na konstrukcję metody rekurencyjnej, liczba wielokrotnych wywołań metody z tym samym argumentem i , dla i =1,2...n, jest liczbą Fibonacciego: F(n-i+1) ! Zatem przy dużych n bardzo dużo czasu tracone jest na powtarzanie tych samych wywołań i zwracanie tych samych wyników.
|