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