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