Rekurencja
2017-06-29 / Krzysztof Kozłowski

Rekurencja to taki sposób programowania, w którym funkcja wywołuje samą siebie. W wielu sytuacjach takie podejście pozwala znacznie uprościć obliczenia, choć nie dzieje się to bez wpływu na wydajność. A to dlatego, że wiele razy powtarzać będziemy te same obliczenia mimo, że już je kiedyś wykonywaliśmy.

Silnia

Dobrym przykładem wykorzystywania rekurencji w programowaniu jest obliczanie tzw. silni. Silnia to w matematyce pewna dosyć prosta funkcja: to prostu iloczyn wszystkich liczb naturalnych nie większych niż dana liczba.

Na przykład silnia liczby 3 to iloczyn wszystkich liczb mniejszych lub równych 3 (czyli 1 * 2 * 3), silnia 4 to po prostu 1 * 2 * 3 * 4 i tak dalej.

Symbolem silni jest znak wykrzyknika (!). Np.:

  • 1! = 1
  • 2! = 1 * 2 = 2
  • 3! = 1 * 2 * 3 = 6
  • 4! = 1 * 2 * 3 * 4 = 24
  • 5! = 1 * 2 * 3 * 4 * 5 = 120
  • 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
  • i tak dalej…

I tu warto zauważyć jedną ciekawą rzecz: jeśli chcemy policzyć silnię np. 5 (1 * 2 * 3 * 4 * 5), to wcześniej musimy policzyć silnię 4 (1 * 2 * 3 * 4) i wynik pomnożyć przez 5. Czyli licząc silnię 5 skorzystamy z tego, że wcześniej już policzyliśmy silnię 4. Chcąc wyliczyć silnię 4 skorzystamy z tego, że wcześniej musieliśmy policzyć silnię 3 itp.

Czyli jeszcze raz:

  • 1! = 1
  • 2! = 1! * 2 = 2
  • 3! = 2! * 3 = 2 * 3 = 6
  • 4! = 3! * 4 = 6 * 4 = 24
  • 5! = 4! * 5 = 24 * 5 = 120
  • 6! = 5! * 6 = 120 * 6 = 720

Można więc napisać taki ogólny wzór, że żeby policzyć silnię danej liczby, to trzeba najpierw policzyć silnię liczby o jeden mniejszej i pomnożyć przez tę liczbę:

1
n! = (n - 1)! * n

Niektórzy w tym zapisie już widzą rekurencję: …żeby policzyć silnię danej liczby … to najpierw trzeba policzyć silnię liczby mniejszej o 1…

Skoro do obliczeń potrzebujemy cofać się o jeden i liczyć silnię dla liczb mniejszych o 1, to pytanie jak długo mamy tak się cofać w obliczeniach. Podpowiedzią będzie matematyczny wzór na silnię:

Dla n = 0 silnia wynosi 1. To jest moment, kiedy przestajemy liczyć silnię dla liczb mniejszych o 1.

Liczenie silni

Czas, aby teorię zastosować w praktyce. Spróbujemy więc napisać funkcję do liczenia silni. Jak napisałem na wstępie, funkcje używające rekurencji z reguły są dosyć proste, dlatego najpierw zaprezentujemy działający program, a potem omówimy, co i jak on liczy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {

    public static void main(String[] args) {

        Long wynik = silnia(50);

        System.out.println(wynik);
    }

    public static long silnia(long n) {
        if (n == 0) { return 1; }
        return silnia(n - 1) * n;
    }
}

Uruchom powyższy przykład w Repl.it.

Funkcja silnia() jak widać, jest bardzo prosta. Jeśli podano liczbę 0, to zwraca ona po prostu wartość 1 (to wynika wprost z wzoru podanego wyżej). A jeśli podano inną liczbę, funkcja wywołuje samą siebie, liczy silnię dla liczby mniejszej o jeden i wynik mnoży przez daną liczbę.

Funkcja jest prosta, jednak należy pamiętać, że rekurencja wpływa czasami niestety na szybkość obliczeń. Zauważcie, że jeśli będzie chcieli policzyć silnię np. dla liczby 15, to kilkanaście razy zmuszeni będziecie liczyć silnię dla np. liczby 5. To powoduje, że im większa liczba, tym więcej obliczeń musimy wykonać i to obliczeń często tych samych. To powoduje, że obliczenia trwają coraz dłużej.

PermaLink: https://java.kozlowski.photos/2017/06/rekurencja/