warunki wyjścia. błąd przepełnienia stosu

Przykład kodu rekurencji bez warunku wyjścia

Przyjrzyjmy się jeszcze raz problemowi rekurencyjnemu. Jako przykład rozważmy wyszukiwanie liczb Fibonacciego. Kto nie pamięta, ciąg Fibonacciego to elementy ciągu liczbowego, w którym pierwsze dwie liczby to 0 i 1, a każda kolejna liczba jest równa sumie dwóch poprzednich liczb.

Napiszmy kod, aby znaleźć i wyświetlić takie liczby:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}
    

Przed pierwszym wywołaniem metody rekurencyjnej printFibonacci wypisz dwie pierwsze liczby z sekwencji, zero i jedynkę. Jest to konieczne, ponieważ w metodzie rekurencyjnej wyświetlamy tylko sumę otrzymanych parametrów, a nie same parametry.

Wygląda OK: otrzymujemy dwie liczby, obliczamy ich sumę, wypisujemy na konsolę i ponownie wywołujemy metodę rekurencyjną printFibonacci . Jako parametry przekazujemy numer poprzedni (poprzedni) i numer bieżący (bieżący).

Właściwie w tym kodzie są 2 błędy. Możesz je zobaczyć, jeśli uruchomisz kod.

Pierwszym błędem jest przepełnienie typu long . 104. liczba w naszym ciągu jest już ujemna, co oznacza, że ​​nastąpiło długie przepełnienie .

Drugi błąd jest inny. Po znalezieniu 12 tysięcy kopiejek na ekranie pojawia się:

W tym miejscu należy przypomnieć, czym jest stos wywołań metod w Javie. Maszyna Java przechowuje zapis wszystkich wywołań funkcji. Ma do tego specjalną kolekcję - stos (stos). Kiedy jedna funkcja wywołuje inną, maszyna Java umieszcza nowy element StackTraceElement na stosie. Po zakończeniu funkcji element ten jest usuwany ze stosu. Stos ten przechowuje więc zawsze aktualne informacje o aktualnym stanie „stosu wywołań funkcji”. Dosłowne tłumaczenie StackOverflowError– „stos pełny”. Javadoc mówi „Zgłaszany, gdy stos wywołań jest zbyt głęboki”. Działająca JVM ma specjalny obszar pamięci do przechowywania stosu wywołań metod. Rozmiar tego obszaru pamięci zależy od ustawień systemu operacyjnego i JVM. Oprócz samego stosu wywołań metod, w tym obszarze pamięci przechowywane są zmienne pierwotne (określone wartości parametrów wywołań metod) oraz adresy zmiennych referencyjnych (w obszarze pamięci HEAP). Model dostępu do stosu to LIFO.

Poprawiony przykład warunku wyjścia

Zacznijmy naprawiać nasz kod od drugiego problemu.

Spróbujmy rozwiązać problem bezpośrednio: jeśli rozmiar stosu jest mały, zwiększmy go. Aby to zrobić, musisz uruchomić JVM ze specjalną flagą „-Xss” i określić, ile pamięci przydzielić dla stosu. Spróbujmy przydzielić 5 megabajtów. W IDEA będzie wyglądać tak:

Tak, długość wyjściowa wzrosła i teraz nie jest to ponad 12 tysięcy znalezionych liczb sekwencji, ale ponad 49 tysięcy. Ale po pewnym numerze nadal otrzymujemy StackOverflowError .

Możesz spróbować zwiększyć obszar pamięci stosu, ale zasadniczo nic się nie zmienia. Będziemy więc szukać problemu w logice. Rekurencja musi mieć punkt przerwania. Oznacza to, że musi istnieć jakiś warunek, po spełnieniu którego metoda rekurencyjna nie zostanie wywołana, a stos wywołań zostanie zwrócony. Aby zdefiniować taki warunek, określmy zadanie - wyświetlić szeregi liczb Fibonacciego, o ile są one mniejsze niż Integer.MAX_VALUE .

Napiszmy nową metodę printFibonacciWithCondition , w której uwzględnimy ten warunek. A w głównej metodzie wywołamy nową poprawioną metodę.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}
    

Po uruchomieniu kodu naprawdę widzimy, że wyjście zakończyło się liczbą 1836311903. Wcześniej ta liczba wynosiła 1134903170. Ich suma to 2_971_215_073, czyli naprawdę więcej niż Integer.MAX_VALUE (2_147_483_647) .

Wraz z tą poprawką automatycznie naprawiliśmy błąd długiego przepełnienia . Jeśli potrzebujesz dłuższej serii liczb, musisz użyć innych typów danych, takich jak BigInteger .

Rekurencyjna metoda zejścia i powrotu

Spróbujmy krok po kroku przeanalizować sposób wykonania naszego kodu. Aby to zrobić, dodaj metodę echo i wywołaj ją przed i po rekurencyjnym wywołaniu metody printFibonacciWithCondition .

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}
    

W wyniku działania programu otrzymujemy wynik:

Zilustrujmy graficznie, jak to się dzieje.

Powiedzmy to jeszcze raz: metoda printFibonacciWithCondition nazywa się . Oblicza aktualną liczbę. Jeśli nam to odpowiada, to ją wyświetlamy i ponownie wywołujemy metodę printFibonacciWithCondition z nowymi parametrami.

Podczas wywoływania metody rekurencyjnej nazywa się to „zejściem rekurencyjnym”. Gdy na stosie wywołań występuje zwrot - „Zwrot rekurencyjny”.

Rekurencja to ciekawy temat w programowaniu. Dla lepszego przyswojenia materiału zmienimy nieco nasze zadanie. Musisz wypisać serię liczb Fibonacciego nieprzekraczających Integer.MAX_VALUE w porządku malejącym. Aby rozwiązać ten problem, napisaliśmy już cały kod. Pozostaje tylko zamienić wyjście bieżącej liczby i wywołać metodę rekurencyjną. Oznacza to, że w pierwszym przykładzie wyjście znalezionej liczby nastąpiło „na etapie zejścia”, a teraz musimy „zejść na sam dół” i wyświetlić liczby na etapie „powrotu”. I oczywiście w metodzie main wyjście dwóch początkowych liczb sekwencji (zero i jedynka) jest zamieniane i wyprowadzane po wywołaniu metody rekurencyjnej. Dla czytelności usuniemy metodę echo .

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}
    

Wyjście będzie: