Rekurencja w Javie

Aby zrozumieć, czym jest rekurencja, musisz zrozumieć, czym jest rekurencja. Tak naprawdę nie ma nic trudnego w zrozumieniu takich funkcji, wystarczy je dobrze zrozumieć raz. I poćwicz, jeśli chodzi o programowanie. Rekurencja w Javie - 1

Rekurencja występuje nie tylko w programowaniu, ale także w prawdziwym życiu. Weź lustro w dłonie i stań przed innym lustrem. Odbicie odbicia będzie odzwierciedlone w odbiciu i tak dalej. Zobaczysz nieskończoną liczbę odbić zmierzających w nieskończoność. Więcej o „prawdziwej” rekurencji przeczytacie w artykule „ Poświęcony Dniu Świstaka… ”. Powróćmy z realnego świata do codzienności programisty. Prosta definicja: Funkcje rekurencyjne w Javie to funkcje, które wywołują same siebie. Podam bardzo prosty i bardzo szkodliwy przykład:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Dlaczego jest to szkodliwe? Proponuję sprawdzić to samodzielnie! Jeśli zdecydujesz się na tę przygodę (a najprawdopodobniej tak się stanie, programiście!), napisz w komentarzach, jaki błąd wyrzuci JVM =) Ten przykład i wiele innych pokazuje, że do stosowania rekurencji w Javie należy podchodzić ostrożnie . Musisz zrozumieć, gdzie, kiedy i dlaczego takie podejście do rozwiązania problemu jest uzasadnione i zadbać o to, aby Twoja funkcja nie zamieniła realizacji programu w „Dzień Świstaka”. Istnieją jeszcze dwie ważne definicje pozwalające zrozumieć rekurencję:

Baza rekurencji - warunek wyjścia z bloku wywołań rekurencyjnych - podstawowe rozwiązanie problemu, w warunkach, gdy nie ma potrzeby wywoływania rekurencji.
Krok rekurencji ma miejsce, gdy funkcja wywołuje samą siebie podczas zmiany parametrów.

Klasycznym przykładem użycia funkcji rekurencyjnej jest obliczenie silni liczby. Jeśli zapomniałeś, przypomnę: silnia dodatniej liczby całkowitej N(oznaczonej jako N!) jest iloczynem liczb z 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Nawiasem mówiąc, silnia zera z definicji jest równa 1. Silnię można więc znaleźć dla dowolnej dodatniej liczby całkowitej i zera (w języku matematyki - dla zbioru nieujemnych liczb całkowitych lub dla zbioru liczb naturalnych i zero). Myślę, że rozumiesz, że można programować silnię za pomocą pętli. Właściwie, oto nierekurencyjna metoda rozwiązania tego problemu:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Dodajmy sprawdzenie, czy liczba jest dodatnia i jest liczbą całkowitą, oraz osobne sprawdzenie zera.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Teraz podam kod metody rekurencyjnego rozwiązania tego problemu:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Przyjrzyjmy się wynikom wyjściowym wywołań:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Otrzymujemy oczekiwane wartości:

Dodajmy ładne wyjście i obliczmy silnię dla większej liczby:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Otrzymujemy: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! W tym przypadku użycie funkcji rekurencyjnej jest uzasadnione i bezpieczne. Jasno zdefiniowaliśmy warunek wyjścia z bloku rekurencyjnego i mamy pewność, że jest to wykonalne: wpisujemy nieujemną liczbę całkowitą, jeśli liczba jest równa zero lub jeden, zwracamy wynik, jeśli liczba jest większa , wynik mnożymy przez funkcję liczby n-1. Używając silni trójki jako przykładu:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Jeśli chodzi o ostrożność w użyciu: jaka jest luka w tej funkcji? Jeśli podasz metodzie liczbę ujemną jako parametr, nastąpi sprawdzenie

if (n == 1 || n == 0) {
    return result;
}

nie ma sensu i skończymy w niekończącym się cyklu wzywania siebie. Warto dodać sprawdzenie nieujemności:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

I wszystko będzie dobrze.

Jaka jest przewaga jednej metody nad drugą? Nie wydaje się, żeby była to duża różnica, ale w rzeczywistości wiele wywołań rekurencyjnych będzie miało negatywny wpływ na wydajność i zużycie pamięci: stos wywołań jest zasobem prawie niekontrolowanym i w różnych warunkach wywołuje tę samą funkcję rekurencyjną, możemy, ale nie musimy, napotkać problemy związane z tym zasobem. Prawie wszystkie problemy rozwiązane za pomocą iteracji (takich jak cykle for-each) można również rozwiązać rekurencyjnie. Zaletą rekurencji jest czytelność i łatwość pisania, o wadach mówiliśmy powyżej: możliwość „strzelenia sobie w stopę” nie jest iluzoryczna. Jeszcze większą ostrożność należy zachować przy stosowaniu tak zwanej „rekurencji złożonej”: funkcja A()wywoła funkcję B(), która wywołuje funkcję A(). Rozwiązanie takich problemów wymaga pełnego zrozumienia działania rekurencji. Przykład takiego zadania: obliczenie wartości x^n/(n!). Silnia, jak omówiliśmy powyżej, jest zdefiniowana na zbiorze nieujemnych liczb całkowitych. Na koniec podam kod rozwiązania. Złożona rekurencja będzie składać się z dwóch metod:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Aby wejść w rekurencję, używana jest metoda calculate, która wywołuje metodę power, która z kolei wywołuje metodę calculate. Zdefiniowaliśmy bazę rekurencji w metodzie potęgowej:

if (n == 1) return x;

Zdefiniowano tam również krok rekurencji:

return x * calculate(x, n - 1);

Pozostaje tylko dodać kontrolę ważności danych wejściowych:

Każda liczba różna od zera jest równa potędze zera 1. Jeśli n = 0następnie n! = 1. Trzeba to zwrócić 1.
Zero do dowolnej potęgi jest równe zero.
Nie będziemy brać pod uwagę niepewności typu 0^0i uznamy takie dane wejściowe za nieprawidłowe.

Po wszystkich kontrolach metody będą wyglądać następująco:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Cóż, wywołując funkcję trzeba pamiętać o wyłapaniu błędu:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Komentarze

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION