CKTIS / Java
Rekurzija i stog poziva
Rekurzija i stog poziva: Rekurzija nastaje kada metoda izravno ili neizravno poziva samu sebe; svaki poziv ima svoj okvir stoga pa su potrebni bazni slučaj i napredak.
Verzija: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Sintaksa
recursionRekurzija nastaje kada metoda izravno ili neizravno poziva samu sebe; svaki poziv ima svoj okvir stoga pa su potrebni bazni slučaj i napredak.
Koristi je za ograničena stabla i podijeli pa vladaj; dubok linearni obilazak zamijeni iteracijom s Deque.
Java ne jamči optimizaciju repnog poziva, stoga ispravna, ali duboka rekurzija može završiti sa StackOverflowError.
Prazan ulaz mora dosegnuti bazni slučaj, a ciklički graf zahtijeva skup posjećenih čvorova.
Dva bazna slučaja završavaju pozive: factorial(5) ispisuje 120, a rekurzivni Euklidov gcd(48,18) ispisuje 6.
Primjeri
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
Dva bazna slučaja završavaju pozive: factorial(5) ispisuje 120, a rekurzivni Euklidov gcd(48,18) ispisuje 6.