База знанияИзпитен център
BGБългарски
Избери език13

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.

Източници