Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / Java

Rekurzija in sklad klicev

Rekurzija in sklad klicev: Rekurzija nastane, ko metoda neposredno ali posredno pokliče samo sebe; vsak klic ima svoj skladovni okvir, zato potrebuje osnovni primer in napredovanje.

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

Sintaksa

recursion

Rekurzija nastane, ko metoda neposredno ali posredno pokliče samo sebe; vsak klic ima svoj skladovni okvir, zato potrebuje osnovni primer in napredovanje.

Uporabi jo za omejena drevesa in deli in vladaj; globok linearni prehod nadomesti z iteracijo in Deque.

Java ne zagotavlja optimizacije repnega klica, zato se pravilna, a globoka rekurzija lahko konča s StackOverflowError.

Prazen vhod mora doseči osnovni primer, ciklični graf pa potrebuje množico obiskanih vozlišč.

Osnovna primera končata klice: factorial(5) izpiše 120, rekurzivni Evklidov gcd(48,18) pa izpiše 6.

Primeri

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));
    }
}

Rezultat

120
6

Osnovna primera končata klice: factorial(5) izpiše 120, rekurzivni Evklidov gcd(48,18) pa izpiše 6.

Viri