La ricorsione in Java

DOMANDA:

Che cos'è la ricorsione?

RISPOSTA:

La ricorsione è forse una delle prime cose che si studiano in programmazione e, diciamoci la verità, non è così intuitiva per chi è alle prime armi. A cosa serve la ricorsione? A creare dei cicli (o chiamate cicliche) in maniera alternativa al classico for. In questo post cerchiamo di semplificarne il concetto utilizzando Java, ma è praticamente uguale in tutti i linguaggi di programmazione.

Guardiamo subito un esempio a scopo puramente didattico:

package ricorsione;

public class RicorsioneTest {

 public static void main(String[] args) {

  int variabile = metodoRicorsivo(); 
  
 }
 
 public static int metodoRicorsivo(){
  return metodoRicorsivo();
 }
}

Cosa succede eseguendo questo frammento di codice? Innanzitutto sconsiglio di eseguirlo dato che sarà un'inconclusiva Exception a Runtime (java.lang.StackOverflowErrorloop)! In pratica l'unica riga di codice del main richiama un metodo che richiama se stesso che a sua volta richiama nuovamente se stesso e così via all'infinito (in questo caso)!

Anche se in modo errato, abbiamo già realizzato una ricorsione, in parole povere un "qualcosa" che richiama se stessa.

Come rendere utile (e soprattutto funzionante) questo concetto? Guardiamo subito l'esempio RicorsioneTest:

package ricorsione;

public class RicorsioneTest {

 public static void main(String[] args) {

  metodoRicorsivo(10); 
  
 }
 
 public static int metodoRicorsivo(int numero){
  System.out.println("Numero valutato: " +numero);
  numero--;  
  if(numero == 1)  
   return 1;  
    
  return metodoRicorsivo(numero);
 }
}

L'output in questo caso è finito e corretto:

Numero valutato: 10
Numero valutato: 9
Numero valutato: 8
Numero valutato: 7
Numero valutato: 6
Numero valutato: 5
Numero valutato: 4
Numero valutato: 3
Numero valutato: 2

Cosa è cambiato?

Abbiamo inserito una condizione base (numero == 1) che permette al metodo di terminare man mano che le chiamate si annidano l'una con l'altra e, soprattutto, abbiamo aggiunto una variante che modifica il valore della variabile ad ogni chiamata (numero--). Queste due condizioni garantiscono che arriveremo (prima o poi) ad una base in cui il metodo non richiamerà più se stesso e comincerà la risalita e la restituzione dei valori al chiamante.

Per chiarire i dubbi sulla ricorsione guardiamo un esempio leggermente più complesso. Il classico algoritmo di Fibonacci. L'algoritmo seguente calcola il numero della sequenza di fibonacci nella posizione i-esima:

package ricorsione; 

public class FibonacciRicorsivo {

  public static long fibonacci(long i) {
    if(i == 0) 
      return 0;
  
    else if(i == 1) 
      return 1;
  
    else 
      return fibonacci(i-1) + fibonacci(i-2);
  }

  public static void main(String[] args){
    long i = 4; //numero su cui calcolare la funzione di fibonacci
    System.out.println("INIZIO CALCOLO DELLA FUNZIONE DI FIBONACCI("+i+")");
    System.out.print("RISULTATO = " + fibonacci(i));
  }
}

L'output sarà banalmente il numero della sequenza di Fibonacci indicato dall'indice i (nell'esempio "4"):

INIZIO CALCOLO DELLA FUNZIONE DI FIBONACCI(4):
RISULTATO: 3

In questo caso (molto semplice) la sequenza di chiamate è questa:

Prima scomposizione di fib(4)

Seconda scomposizione di fib(3);
fib(1) termina le sottochiamate in quanto caso base

Terza scomposizione di fib(2), fib(1) e fib(0) sono casi base

Terminate le chiamate del ramo, comincia la risalita
e la restituzione dei risultati, qui a fib(2)

Restituzione a fib(3)

Terminata la restituzione del primo ramo,
cominciano le chiamate al secondo ramo

Come nel primo caso, terminate le chiamate, si restituiscono i risultati

Infine l'ultima somma restituisce il risultato finale (esatto)

Nell'utilizzare la ricorsione è necessario sapere che in genere è molto più pesante in termini di elaborazione rispetto alla normale iterazione. Infatti, in algoritmi come questo il numero di chiamate sale esponenzialmente: guardiamo lo schema finale delle chiamate se provassimo a calcolare il 5° numero della sequenza di fibonacci (nella sequenza precedente era fibonacci(4)):

In arancione ci sono i 2 casi base che restituiscono 0 o 1 
e tra parentesi la somma parziale fino a quel momento

Immaginiamo cosa accadrebbe per numeri più grandi.

In sintesi l'utilità della ricorsione è di consentire la scrittura di algoritmi di una certa complessità in maniera più semplice (per determinate categorie di problemi) ed elegante. Di contro, la sua dispendiosità in termini di risorse ne limita fortemente il campo di applicazione.