Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / Java

Ricorsione e stack delle chiamate

Ricorsione e stack delle chiamate: La ricorsione avviene quando un metodo chiama sé stesso direttamente o indirettamente; ogni invocazione ha un frame dello stack, quindi servono caso base e progresso.

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

Sintassi

recursion

La ricorsione avviene quando un metodo chiama sé stesso direttamente o indirettamente; ogni invocazione ha un frame dello stack, quindi servono caso base e progresso.

Usala per alberi limitati e divide et impera; sostituisci un percorso lineare profondo con iterazione e Deque.

Java non garantisce la tail-call optimization, quindi una ricorsione corretta ma profonda può terminare con StackOverflowError.

L’input vuoto deve raggiungere il caso base e un grafo ciclico richiede un insieme visited per terminare.

Due casi base terminano le chiamate: factorial(5) stampa 120 e l’algoritmo euclideo ricorsivo gcd(48,18) stampa 6.

Esempi

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

Risultato

120
6

Due casi base terminano le chiamate: factorial(5) stampa 120 e l’algoritmo euclideo ricorsivo gcd(48,18) stampa 6.

Fonti