Ricorsione in Java

La ricorsione si verifica quando un metodo chiama se stesso. È un modo naturale per esprimere problemi la cui struttura si ripete su scala più piccola — contare alla rovescia, percorrere un albero, calcolare un fattoriale, invertire una stringa.

Ogni metodo ricorsivo ha due parti: un caso base che restituisce direttamente senza ricorrere, e un caso ricorsivo che chiama il metodo su una parte più piccola del problema. Sbagliare una delle due parti fa sì che il programma dia una risposta errata o giri all'infinito (finché la JVM non esaurisce lo stack).

Un primo esempio: il fattoriale

Il fattoriale di n è n × (n-1) × (n-2) × … × 1. Per definizione, 0! = 1. Tale definizione è essa stessa ricorsiva: n! = n × (n-1)!.

La traduzione in Java corrisponde direttamente:

public static int factorial(int n) {
  if (n == 0) return 1;            // base case
  return n * factorial(n - 1);      // recursive case
}

Chiamare factorial(4) produce:

factorial(4)
  = 4 * factorial(3)
  = 4 * 3 * factorial(2)
  = 4 * 3 * 2 * factorial(1)
  = 4 * 3 * 2 * 1 * factorial(0)
  = 4 * 3 * 2 * 1 * 1
  = 24

Ogni chiamata rimane sullo stack in attesa che la successiva restituisca un valore. Quando factorial(0) restituisce infine 1, le risposte si propagano a ritroso lungo la catena.

Il caso base è imprescindibile

Senza un caso base, il metodo non ha nulla che fermi la ricorsione. L'errore classico:

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

Questo ricorre all'infinito — finché il call stack non si esaurisce e la JVM lancia StackOverflowError. Il caso base è ciò che termina la catena; il caso ricorsivo è ciò che avanza verso di essa.

L'altro errore classico è un caso base che la ricorsione non raggiunge mai:

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) qui proverebbe factorial(5), factorial(6), … e andrebbe in crash. La chiamata ricorsiva deve spostare l'argomento più vicino al caso base.

Ricorsione sugli interi: conto alla rovescia

Un secondo esempio elementare per chiarezza — stampare i numeri da n fino a 1:

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) stampa 3, 2, 1. Invertire l'ordine per stampare 1, 2, 3:

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

Stessa ricorsione, ordine di stampa diverso — perché la chiamata ricorsiva avviene prima della stampa. La lezione: ciò che si fa prima della chiamata ricorsiva viene eseguito durante la discesa, ciò che si fa dopo viene eseguito durante la risalita.

Ricorsione sulle stringhe: inversione

Invertire una stringa può essere pensato come "togli il primo carattere, inverti il resto, aggiungi il primo carattere alla fine":

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

Questo è elegante ma inefficiente — ogni chiamata ricorsiva alloca una nuova sottostringa. Un ciclo con StringBuilder sarebbe più veloce. La ricorsione è spesso l'espressione più chiara di un'idea; non è sempre l'implementazione più veloce.

Fibonacci e il costo della ricorsione

La sequenza di Fibonacci è 0, 1, 1, 2, 3, 5, 8, 13, …, definita come fib(n) = fib(n-1) + fib(n-2). La traduzione diretta:

public static long fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

Questo è corretto ma esponenzialmente lento — fib(40) è già percettibilmente lento, fib(50) è problematico. L'albero di ricorsione ricalcola gli stessi sottoproblemi miliardi di volte (fib(5) da solo chiama fib(2) tre volte). La soluzione nel codice reale è la memoizzazione oppure un semplice ciclo.

La memoizzazione mantiene la struttura ricorsiva ma memorizza nella cache ogni risultato la prima volta che viene calcolato, in modo che ogni sottoproblema venga eseguito una sola volta:

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

Un semplice ciclo elimina del tutto la ricorsione e usa memoria costante:

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Sapere quando la ricorsione è lo strumento sbagliato è importante quanto sapere quando è quello giusto.

Ricorsione vs iterazione

Qualsiasi metodo ricorsivo può essere riscritto come ciclo, e qualsiasi ciclo può essere riscritto come ricorsione — sono ugualmente potenti. La scelta riguarda chiarezza e costo:

• Usa la ricorsione quando i dati stessi sono ricorsivi (alberi, cartelle annidate, JSON) oppure quando la definizione ricorsiva è più chiara del ciclo, come con factorial o reverse.
• Usa un ciclo quando la ricorsione sarebbe abbastanza profonda da rischiare un StackOverflowError, o quando una versione iterativa è altrettanto leggibile ed evita il costo per ogni chiamata, come con fib.

Quando le due opzioni sono ugualmente chiare, preferire il ciclo in Java: non ha limiti di profondità dello stack e non ha il costo dei frame di chiamata.

StackOverflowError

Ogni chiamata in sospeso usa una porzione dello stack della JVM. Con la dimensione predefinita dello stack, di solito è possibile annidare qualche migliaio di chiamate prima che le cose si rompano:

factorial(100000);    // StackOverflowError

Java non esegue l'ottimizzazione delle chiamate in coda — anche una chiamata ricorsiva che è l'ultima cosa che il metodo fa consuma comunque un frame dello stack. Se il problema può richiedere una ricorsione molto profonda, passa a un ciclo oppure usa un Deque esplicito come stack personale.

Un esempio completo

Cosa c'è dopo

Hai definito metodi, passato parametri, sovraccaricato nomi e usato la ricorsione. Il prossimo concetto è lo scope — quali parti di un metodo possono vedere quali variabili e cosa succede quando un nome appare in più di un posto. Continua nel capitolo sullo scope delle variabili.

Esercizi