Twitter: @grzegg
Kategoria: java, Tagi: - - - .

Java [21] – Rekurencja

Z rekurencją mamy do czynienia wtedy, gdy metoda wywołuje samą siebie. Oczywiście, jeśli nie chcemy zawiesić programu, należy umieścić w kodzie jakiś warunek takiego wywołania tak, aby w pewnym momencie doszło do zakończenia ciągu wywołań. Działanie rekurencji pokażę na przykładzie programu obliczającego silnię.

Przykład

Aby pokazać sposób działania rekurencji napiszemy program, który pobierze od użytkownika liczbę całkowitą i obliczy dla niej silnię.
Tak naprawdę, aby obliczyć silnię nie trzeba odwoływać się do rekurencji, można to zrobić za pomocą zwykłej pętli, ale z powodów dydaktycznych nie pójdziemy na łatwiznę.

Przypominam, że silnia (oznaczana znakiem !) to iloczyn kolejnych liczb od 1 do liczby dla której oblicza się silnię, przy czym dla 0 silnia = 1. Na przykład:


5! = 1 * 2 * 3 * 4 * 5 = 120

Ponieważ mnożenie jest przemienne, równie dobrze można powyższe zapisać tak:


5! = 5 * 4 * 3 * 2 * 1 = 120

Mnożenie przez 1 nie zmienia wartości wyniku, więc można wzór nieco uprościć:


5! = 5 * 4 * 3 * 2 = 120

ale dla przejrzystości kodu zignorujemy tą możliwość.

Bardziej ogólnie obliczanie silni można przedstawić tak:


n! = n * n-1 * n-2 ... * 1

Teraz zastanówmy się jak powinien działać program, który przeprowadzi takie obliczenia.

Najpierw należy pobrać od użytkownika liczbę dla której będzie liczona silnia, powinna to być liczba całkowita mieszcząca się w zakresie od 0 do 13. Dolna granica wynika z definicji silni, można ją liczyć dla liczb naturalnych (nieujemnych, całkowitych). Górna z zakresu liczb, które można zapisać w zmiennych typu int. Możesz ten zakres zwiększyć zmieniając typ używanych w programie zmiennych na long lub BigInteger, w drugim przypadku będzie też trzeba dokonać dodatkowych zmian w kodzie odpowiedzialnym za przeprowadzanie obliczeń (zob. poprzedni wpis). Kod odpowiedzialny za pobranie liczby od użytkownika i sprawdzenie jej poprawności umieścimy w osobnej metodzie.

Osobna metoda będzie odpowiadać za obliczenia, przy czym pokażę dwa sposoby rekurencyjnego rozwiązania problemu, oba znajdują się w osobnych metodach (obliczSilnie1 i obliczSilnie2) w kodzie zamieszczonym poniżej. Dla porównania dołożyłem też przykładowe rozwiązanie za pomocą pętli (obliczSilniePetla) Zaznaczam, że można poniższy kod znacznie bardziej skondensować (spróbuj w ramach treningu) ale w tej formie, moim zdaniem, bardziej czytelnie pokazuje sposób działania rekurencji.

Rozwiązanie 1 – metoda obliczSilnie1(int liczba, int l)

W tym rozwiązaniu, metoda wywołuje sama siebie za każdym razem wykonując obliczenia, aż dojdzie do ostatniego mnożenia, wtedy wynik jest przekazywany „w górę”.

  • Jeśli przekazana liczba równa jest 0, zwracana jest wartość 1, jeśli nie to wykonywane są dalsze kroki:
  • Metoda mnoży „bieżący” wynik przez kolejną liczbę z szeregu. Przy pierwszym wywołaniu bieżący wynik jest równy liczbie podanej przez użytkownika a liczba przez którą będzie mnożony jest o jeden mniejsza. Obie liczby podajemy jako argumenty.
  • Metoda oblicza bieżący wynik mnożąc obie liczby przez siebie, po czym wywołuje samą siebie, podając tym razem jako argumenty bieżący wynik oraz liczbę, przez którą mnożyliśmy zmniejszoną o 1.
  • Wywołana metoda znów dokonuje opisane powyżej operacje i proces tego coraz bardziej zagnieżdżonego wywoływania samej siebie trwa dopóki liczba przez którą zamierzamy mnożyć bieżący wynik jest większa niż 1.
  • Kiedy ten próg zostaje osiągnięty, metoda zwraca bieżący wynik, który „wędruje w górę”, czyli do metody, która ją wywołała, ta z kolei znów zwraca ją „wyżej” aż wynik zostaje zwrócony przez pierwsze wywołanie metody w metodzie main.

Rozwiązanie 2 – metoda obliczSilnie2(int liczba)

Jest to sposób bardziej „klasyczny”. W tym przypadku najpierw argument za każdym wywołaniem metody zmniejszany jest o 1 aż do chwili, gdy osiągnie wartość 0, wtedy wynik jest zwracany. W metodzie, która otrzymała rezultat dokonywane są obliczenia, których wynik dalej wędruje „w górę”.

  • Metoda przyjmuje tylko jeden argument, przy pierwszym wywołaniu jest to podana przez użytkownika liczba
  • Jeśli przekazana liczba równa jest 0, zwracana jest wartość 1, jeśli nie to wykonywane są dalsze kroki:
  • Metoda wywołuje samą siebie, podając jako argument liczbę o 1 mniejszą niż liczba, która została jej przekazana.
  • Rekurencyjne wywoływanie metody kończy się, gdy argument osiągnie wartość 0, wtedy bieżący wynik, który w tym momencie wynosi 1, zostaje przekazany „w górę”
  • Zwracana liczba jest mnożona przez argument, który został przekazany do metody, wynik jest przekazany „w górę”
  • W końcu wynik końcowy zostaje zwrócony do metody main, która wypisuje go na ekranie.

W poniższym kodzie umieściłem też komendy wypisujące bieżące wartości obliczane przez metody a także przekazywane do nich argumenty. Prześledzenie ich wartości oraz kolejności w jakiej są drukowane ułatwia zrozumienie całego procesu.

Dla porównania podaję też rozwiązanie za pomocą pętli for.

Uwaga: Rekurencja łączy się niestety z dość dużym apetytem na pamięć komputera, nie należy zatem przesadzać z liczbą wywołań rekurencyjnych metody, ponieważ może to spowodować błąd przepełnienia stosu (błąd: java.lang.StackOverflowError).

8 komentarzy Java [21] – Rekurencja

  • Joanna

    Ja bym zaproponowała nieco łatwiejszy kod:

    static int Silnia1 (int liczba)
    {
    if (liczba==0) return 1;
    return liczba*Silnia1(liczba-1);
    }
    wydaje mi się być równie poprawny

  • Darek

    czesc, a gdzie w obliczSilnie1 jest sprawdzenie czy l =< 1
    ?

    • Grzegorz

      Kiedy wywołuje się metodę:
      obliczSilnie1(liczba, l – 1)
      przy wartości l=1, to wtedy w wywołanej metodzie liczba == 0, zatem
      if (liczba == 0) jest spełnione i zwracana jest jedynka.

      Oczywiście można by też wpisać warunek:
      if (l != 1) obliczSilnie1(liczba, l – 1);
      else return 1;

      Nieco dłuższy kod za to jedno niepotrzebne wywołanie metody mniej.

      Pozdrawiam
      Grzegorz

  • Darek

    nie moge sie zgodzic, moim zdaniem
    wartosc „liczba” jest zawsze wieksza niz wartosc „l”
    w wywolaniu obliczSilnie1(liczba, l – 1);

  • Darek

    : ) A material sam w sobie bardzo przydatny, Pozdrawiam!

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

  

  

  

Rozwiąż zadanie: * Time limit is exhausted. Please reload CAPTCHA.