Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / Java

Rekurencja i stos wywołań

Rekurencja i stos wywołań: Rekurencja zachodzi, gdy metoda wywołuje siebie bezpośrednio lub pośrednio; każde wywołanie ma własną ramkę stosu, więc potrzebuje warunku bazowego i postępu.

Wersja: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime

Składnia

recursion

Rekurencja zachodzi, gdy metoda wywołuje siebie bezpośrednio lub pośrednio; każde wywołanie ma własną ramkę stosu, więc potrzebuje warunku bazowego i postępu.

Stosuj ją do ograniczonych drzew i algorytmów dziel i zwyciężaj; głębokie przejście liniowe przenieś na iterację z Deque.

Java nie gwarantuje optymalizacji wywołań ogonowych, dlatego poprawna, lecz głęboka rekurencja może zakończyć się StackOverflowError.

Puste wejście musi trafić w przypadek bazowy, a graf cykliczny wymaga zbioru odwiedzonych węzłów, inaczej rekurencja nie zakończy się.

Dwa warunki bazowe kończą wywołania: factorial(5) wypisuje 120, a rekurencyjny algorytm Euklidesa gcd(48,18) wypisuje 6.

Przykłady

public class Main {
    static int factorial(int n) {
        return n <= 1 ? 1 : n * factorial(n - 1);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(gcd(48, 18));
    }
}

Wynik

120
6

Dwa warunki bazowe kończą wywołania: factorial(5) wypisuje 120, a rekurencyjny algorytm Euklidesa gcd(48,18) wypisuje 6.

Źródła