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
recursionRekurzija 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.