« poprzedni punkt  następny punkt »

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.

Rozpatrzmy najprostsze przykłady.

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.

Zauważmy, że w pierwszym przypadku mieliśmy tak naprawdę do czynienia z takim samym wstrzymywaniem wykonania kodu metody show1 inicjowanego przez kolejne wywołania rekurencyjne, tyle, że nie mogliśmy tego dostrzec, ponieważ wstrzymywanie następowało na ostatniej instrukcji metody, już po wyprowadzeniu liczby.

Oczywiście metody rekurencyjne mogą zwracać wartości.
Zobaczmy, jak np. można rekurencyjnie zapisać zadanie sumowania dodatnich liczb całkowitych.
W istocie rekurencja oznacza "zdefiniowanie czegoś przez to samo coś".
Weźmy sumę 1 + 2 + 3 + 4 + 5.
Możemy powiedzieć tak:
suma(1..5) = 5 + suma(1..4)
suma(1..4) = 4 + suma(1..3)

Definiujemy sumę przez sumę!

Ogólnie, suma liczb od 1 do n  równa jest n + suma(1..n-1)
Zatem jeśli nasza metoda sumowania otrzymuje argument n (oznaczający, że mamy zsumować liczby od 1 do n), to moglibyśmy spróbować zapisać:

int sum(int n) {
 return n + sum(n-1);
}

Łatwo jednak zauważyć, że wpadamy tu w "nieskończoną" rekurencję. Metoda sum  będzie wywoływana teoretycznie bez końca ze swojego wnętrza (praktycznym ograniczeniem będzie pamięć komputera - program skończy działanie z komunkatem "Stack overflow").

Musimy zatem zapewnić jakiś warunek zakończenia wywołań rekurencyjnych,
Uwzględnić jakiś szczególny przypadek wartości przekazanego argumentu, który przerwie nieskończone rekurencyjne wywołania.
W przypadku sumowania liczb od 1 do n, takim szczególnym przypadkiem jest wartość n = 1 (zwracamy wtedy 1).

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!)

Proszę dokładnie przeanalizować działanie tej metody dla n = 5 , pamiętając, że kolejne zwroty wyników rekurencyjnego wywołania sum(...) są wstrzymywane dopóki n nie osiągnie wartości 1 i zauważając, że odtwarzanie tych wyników następuje w else, po kolei: 1, 2 + 1, 3 + (2 + 1), 4 + (3 + 2 + 1), 5 + (4 + 3 + 2 +1) i ta ostatnia wartość jest właśnie zwracana do punktu wywołania sum(..) w metodzie main.

Można się domyślić (choćby z przykładu sumowania), że rekurencyjne wywołania funkcji można zastąpić pętlami iteracyjnymi.

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.

Ciąg Fibonacciego dany jest za pomocą następującego równania, okreslającego wartości Fn kolejnych liczb ciagu (dla n = 0, 1, 2, ...):

F0   =  0,
F1   =  1,
Fn  =   Fn-2  + Fn-1, dla n > 1.

Czyli jest to ciąg liczb zaczynający się od liczb 0 i 1, przy czym każda następna liczba ciągu (poczynając od trzeciej) jest sumą dwóch poprzednich liczb ciągu:

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.

Jak widać. ciąg Fibonanciego jest ciagiem rekurencyjnym, zatem wyliczenie jego kolejnych wyrazów w naturalny sposob można zapisać w postaci rekurencyjnej.

  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.
Dzieje się tak dlatego, że katastrofalnie rośnie liczba rekurencyjnych wywołań metody fib.
Większą część czasu zajmuje obliczanie już policzonych wartości!
Zobaczmy.
Używając zmodyfikowanej postaci metody fib:

  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.

Proszę samodzielnie zbudować pełny program, który pozwala na taką analizę (wykorzystać podaną wyżej metodę oraz  przekierowanie standardowego wyjścia do pliku).


Możemy też automatycznie policzyć liczbę wywołań z różnymi argumentami za pomocą np. takiego programu:

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.
Uzyskamy następujące wyniki:

Dla n = 8
Dla n = 20
Liczba wywołań fib z argumentem 0 13
Liczba wywołań fib z argumentem 1 21
Liczba wywołań fib z argumentem 2 13
Liczba wywołań fib z argumentem 3 8
Liczba wywołań fib z argumentem 4 5
Liczba wywołań fib z argumentem 5 3
Liczba wywołań fib z argumentem 6 2
Liczba wywołań fib z argumentem 7 1
Liczba wywołań fib z argumentem 8 1

Liczba wywołań fib z argumentem 0 4181
Liczba wywołań fib z argumentem 1 6765
Liczba wywołań fib z argumentem 2 4181
Liczba wywołań fib z argumentem 3 2584
Liczba wywołań fib z argumentem 4 1597
Liczba wywołań fib z argumentem 5 987
Liczba wywołań fib z argumentem 6 610
Liczba wywołań fib z argumentem 7 377
Liczba wywołań fib z argumentem 8 233
Liczba wywołań fib z argumentem 9 144
Liczba wywołań fib z argumentem 10 89
Liczba wywołań fib z argumentem 11 55
Liczba wywołań fib z argumentem 12 34
Liczba wywołań fib z argumentem 13 21
Liczba wywołań fib z argumentem 14 13
Liczba wywołań fib z argumentem 15 8
Liczba wywołań fib z argumentem 16 5
Liczba wywołań fib z argumentem 17 3
Liczba wywołań fib z argumentem 18 2
Liczba wywołań fib z argumentem 19 1
Liczba wywołań fib z argumentem 20 1

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.

Zadanie do samodzielnego wykonania

Napisać iteracyjną wersję metody obliczającej wyrazy ciągu Fibonacciego. Za pomocą znanej nam już klasy QTimer porównać czas obliczeń wersji rekursywnej i iteracyjnej.
Po napisaniu programu porównać go z programem FibonTest.java znajdującym się w katalogu samples\Fibonacci14.


« poprzedni punkt  następny punkt »