La Ricorsione

La ricorsione (recursion) è una tecnica di programmazione molto potente, che sfrutta l'idea di suddividere un problema da risolvere in sottoproblemi simili a quello originale, ma più semplici.

Un algoritmo ricorsivo per la risoluzione di un dato problema deve essere definito nel modo seguente:

• prima si definisce come risolvere dei problemi analoghi a quello di partenza, ma che hanno "dimensione piccola" e possono essere risolti in maniera estremamente semplice (detti casi base);
• poi si definisce come ottenere la soluzione del problema di partenza combinando la soluzione di uno o più problemi analoghi, ma di "dimensione inferiore".

Un classico esempio di descrizione ricorsiva è la definizione del fattoriale di un numero intero. Immaginiamo di dover calcolare il fattoriale di un numero n:

          n! = n * (n - 1)* ... * 3 * 2 * 1

Per convenzione  0! = 1. Inoltre, il fattoriale non è definito per i numeri negativi. 

Come possiamo scrivere un metodo che calcoli la funzione fattoriale? Osserviamo che:

   n! = n * (n-1) * ... * 2 * 1 =
      = n * (n-1)!

Quindi la versione "ricorsiva" della definizione di fattoriale è:

     0! = 1              (caso base)
     n! = n * (n-1)!     (se  n > 0).

Ricorsione Diretta

Un metodo (procedura/funzione) si dice ricorsivo quando all'interno della propria definizione compare una chiamata direttamente al metodo stesso.

Questa forma di ricorsione si chiama ricorsione diretta.

Un esempio di ricorsione diretta è la seguente realizzazione del fattoriale di un numero intero:

public class MyRecursiveMethods {
 
 // altri metodi
 
 public static int factorial(int n) {
 int result;     
 if (n < 0)    
            result = -1;  // situazione anomala
 
 else if (n == 0)
            result = 1;   // caso base
 
 else
            result = n * factorial(n - 1); // ricorsione
 
 return result;
 
 }
 
 // altri metodi

Condizioni come (n == 0) si chiamano clausole di chiusura o casi base perché garantiscono che la ricorsione termini.

Notare che, nell'esempio sopra, il metodo restituisce -1 quando l'argomento è un numero negativo (lasciando al chiamante la responsabilità di controllare che il parametro attuale della chiamata a fattoriale sia maggiore o uguale a zero).

In Java le situazioni anomale dovrebbero invece essere gestite mediante la gestione delle eccezioni, che vedremo nel secondo modulo di LIP.

Come funziona la Ricorsione?

Supponiamo di eseguire il metodo

 public static void main (String [] args) {
 
 ...
 
 int i = MyRecursiveMethods.factorial(3);
 
        ...
 
    }

Per l'invocazione di factorial(3), il record di attivazione è aggiunto in cima alla pila (con una operazione di push), e i record relativi alle successive invocazioni di factorial vengono "impilati" su di esso (mediante operazioni di push successive).

---

---

Come funziona la Ricorsione? (2)

---

Arrivati al caso base i record iniziano ad essere "scaricati" dalla pila restituendo mano a mano i valori ottenuti e passando il controllo al corrispondente indirizzo di ritorno.

Quando una chiamata di factorial termina, il corrispondente record di attivazione è eliminato (operazione di pop).

Alla fine, il flusso continua dall'indirizzo di ritorno nel main da dove il metodo è stato chiamato per la prima volta.

---

---

Ricorsione Indiretta

---

Si parla di ricorsione indiretta quando nella definizione di un metodo compare la chiamata ad un altro metodo il quale direttamente o indirettamente chiama il metodo iniziale.

Un esempio di ricorsione indiretta:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 // notare che si restituisce direttamente il risultato,
 // evitando l'uso della variabile locale result
 public static int ping(int n) {
 if (n < 1)
 return 1;
 else 
 return pong(n - 1); // chiamata di pong   
    }
 
 public static int pong(int n) {
 if (n < 0)
 return 0;
 else 
 return ping(n/2); // chiamata di ping   
 }
 
    ... // altri metodi
 
}

Notare che, nell'esempio sopra, i metodi sono cooperanti nel senso che si  invocano ripetutamente a vicenda (indirettamente), dando luogo ad un caso particolare di ricorsione indiretta, detto ricorsione mutua.

---

---

Ricorsione Multipla

---

Un metodo implementa una ricorsione multipla quando all'interno della propria definizione compare la chiamata direttamente al metodo stesso almeno due volte.

Un classico esempio di ricorsione multipla è l'implementazione dei numeri di Fibonacci, la cui definizione è riportata sotto:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1)  +  fib(n - 2)       (se  n > 1)

Notare che, come per il fattoriale, la funzione è definita solo su interi non negativi.

In Java il metodo per la implementazione dei numeri di Fibonacci può essere definito come:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int fib(int n) {
 
 if (n < 0)
 return -1;                  // anomalie
 
 else if ( n==0 || n==1 )
 return n;                   // casi base
 
 else
 return fib(n-1) + fib(n-2); // ricorsione
 
       }
 
    ... // altri metodi
 
}

---

---

Problemi con la Ricorsione

---

La ricorsione è una tecnica molto potente per decomporre problemi complessi, ma quando si scrivono programmi ricorsivi si incontrano tre problemi comuni:

• ricorsione infinita: è un grave errore di programmazione che tipicamente si verifica perché manca la clausola di chiusura per terminare (errata gestione di anomalie e casi base) o perché i valori del parametro non si semplificano (errata gestione delle chiamate ricorsive).
• spazio sprecato: si scrivono metodi che contengono variabili locali non necessarie, oppure non usate, e così la memoria del sistema non è utilizzata in modo efficiente.
• complessità alta: per certi problemi le soluzioni ricorsive hanno intrinsecamente complessità non lineare.

Adesso, per ognuna delle categorie di problemi elencate sopra, vediamo dei semplici esempi che mostrano il fulcro del problema.

---

---

Ricorsione Infinita

---

In una ricorsione infinita un metodo chiama se stesso infinite volte.  Come abbiamo già detto, ciò si verifica perché i valori del parametro non si semplificano, o perché manca la clausola di chiusura per terminare.

Per esempio, vediamo cosa succede nell'implementazione del fattoriale quando omettiamo la gestione dei casi base:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int badFactorial(int n) {
 
 return (n * badFactorial(n-1));
 
    }
 
    ... // altri metodi
 
}

Dopo un certo numero di chiamate la memoria disponibile per questo scopo si esaurisce e il programma termina automaticamente segnalando un errore di trabocco della pila (stack overflow error).

---

---

Spazio Sprecato

---

Spesso, quando si sviluppano soluzioni ricorsive si scrivono metodi che contengono variabili locali non necessarie, oppure non usate. Per esempio:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int stackGreedyFactorial(int input) {
 int result, n;
 double nonUsato;
        n = input;
 
 if (n == 0)
            result = 1;
 else
            result = n * stackGreedyFactorial(n-1);
 
 return result;
    }
 
    ... // altri metodi
 
}

Conviene sempre eliminare le variabili locali che non sono necessarie oppure non usate perché, come abbiamo visto nelle figure della pila di attivazione, con ogni chiamata del metodo l'ambiente di programma alloca spazio per TUTTE le variabili locali.

Da notare che esistono versioni piu semplici del fattoriale di un numero che non hanno nessuna variabile locale. Per esempio:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int simplerFactorial(int n) {
 if (n < 0)
 return -1;
 if (n == 0)
 return 1;
 else
 return (n * simplerFactorial(n-1));
 }
 
    ... // altri metodi
 
}

---

---

Complessità Alta

---

La tecnica di ricorsione non è sempre il modo migliore di risolvere  problemi. Un esempio di questa situazione è evidenziato dall'albero delle chiamate per il metodo ricorsivo fib che abbiamo definito per il calcolo dei numeri di Fibonacci:

La complessità del metodo fib(n) è esponenziale perché la ricorsione è multipla. Da un'analisi dell'algoritmo, i casi base (fib(0) o fib(1)) sono calcolati complessivamente fib(n+1) volte durante la computazione di fib(n).

• Ad esempio, per calcolare fib(29) i metodi fib(0) e fib(1) sono chiamati fib(30) = 832040 volte.

Una banale implementazione con un ciclo che calcola una ed una sola volta tutti i valori dei numeri di Fibonacci da 0 a n ha invece una complessità lineare (ovviamente).

---

---

Metodi Ricorsivi vs. Metodi Iterativi (1)

---

Per ovviare alla alta complessità dei metodi ricorsivi possiamo sempre transformare i loro algoritmi in algoritmi iterativi. Per esempio una versione iterativa del metodo factorial è:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int iterativeFactorial(int n) {
 
 int result;
 
 if (n < 0)
            result = -1;
 
 else {
            result = 1;
 
 for (int i = 1; i <= n; i++)
                result = result * i;
        }
 
 return result;  
 }
 
    ... // altri metodi
 
}

Si noti che la versione iterativa del fattoriale è tanto leggibile quanto la versione ricorsiva.

Cosa si risparmia con la versione iterativa?

• memoria;
• efficienza.

---

---

Metodi Ricorsivi vs Metodi Iterativi (2)

---

In modo analogo si può scrivere una versione iterativa del metodo per calcolare i numeri di Fibonacci:

public class MyRecursiveMethods {
 
    ... // altri metodi
 
 public static int iterativeFib(int n) {
 
 int fibN = -1; // gestione casi anomali
 
 if ( n==0 || n==1 )
            fibN = n;
 
 else {
 // ad ogni iterazione bisogna ricordare gli ultimi
 // due valori calcolati nelle iterazioni precedenti
 int fibNminus2 = 0; // penultimo valore
 int fibNminus1 = 1; // ultimo valore
 
 for (int i = 2; i <= n; i++) {
                fibN = fibNminus1 + fibNminus2;
                fibNminus2 = fibNminus1;
 fibNminus1 = fibN;
            }
        }
 
 return fibN;
    }
 
    ... // altri metodi
 
}

La definizione iterativa per i numeri di Fibonacci ha complessità lineare ma è meno leggibile.

Per avere un'idea della differenza di prestazioni tra la versione iterativa e quella ricorsiva proviamo a confrontare i tempi di esecuzione per alcuni valori (es. 10, 20, 30, 40 e 45): FibonacciTest .

---

---

Sommario sulla Ricorsione

---

• Un'elaborazione ricorsiva risolve un problema riconducendolo a problemi dello stesso tipo ma su dati di ingresso più semplici.
• Affinché la ricorsione termini devono esistere casi speciali che gestiscono i dati di ingresso più semplici (casi base).
• A volte è più facile trovare una soluzione ricorsiva se si modifica leggermente il problema originario.
• A volte una soluzione ricorsiva viene eseguita molto più lentamente di una corrispondente soluzione iterativa, ma nella maggior parte dei casi la soluzione ricorsiva è soltanto un poco più lenta (specialmente se la ricorsione non è multipla).
• In molti casi una soluzione ricorsiva è più facile da capire e da realizzare correttamente rispetto ad una soluzione iterativa.

---