CKTIS / Java
Рекурсия и стек на извикванията
Рекурсия и стек на извикванията: Рекурсия има, когато метод извиква пряко или косвено себе си; всяко извикване има собствен stack frame, затова са нужни базов случай и напредък.
Версия: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Синтаксис
recursionРекурсия има, когато метод извиква пряко или косвено себе си; всяко извикване има собствен stack frame, затова са нужни базов случай и напредък.
Използвай я за ограничени дървета и „разделяй и владей“; замени дълбоко линейно обхождане с итерация и Deque.
Java не гарантира оптимизация на опашково извикване, затова правилна, но дълбока рекурсия може да завърши със StackOverflowError.
Празният вход трябва да стигне базовия случай, а цикличен граф изисква множество от посетени върхове.
Двата базови случая прекратяват извикванията: factorial(5) извежда 120, а рекурсивният Евклидов gcd(48,18) извежда 6.
Примери
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));
}
}
Резултат
120 6
Двата базови случая прекратяват извикванията: factorial(5) извежда 120, а рекурсивният Евклидов gcd(48,18) извежда 6.