Motivazioni

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.

Esempio: Supponiamo di voler calcolare l'area di una forma triangolare di dimensione n come quella riportata sotto, nell'ipotesi che ciascun quadrato [] abbia area unitaria. Il valore dell'area corrispondente viene a volte chiamato numero triangolare n-esimo.
Ad esempio, per n=4 il triangolo è fatto come segue:

 []
 [][]
 [][][]
 [][][][]

Osservando questo schema possiamo affermare che il quarto numero triangolare è 10.

Supponiamo di voler scrivere un metodo che dato n, calcola il numero triangolare n-esimo.

    public static int numeroTriangolare(int n) {
        int result;     
                          
        .....
                          
        return result;
    }

Ragioniamo per approssimazioni successive.

Se l'ampiezza del triangolo è 1, il triangolo consiste di un unico quadrato [] e la sua area è uguale a 1.

    public static int numeroTriangolare(int n) {
        int result;     
        if (n == 1)
            result = 1;   // caso base
                          
         ......
                          
        return result;
        }

Per trattare il caso più generale, consideriamo questa figura:

 
 []
 [][]
 [][][] 
 [][][][]

Supponiamo adesso di conoscere l'area del triangolo più piccolo, formato dalle prime tre righe: il terzo numero triangolare. In questo caso possiamo calcolare facilmente l'area del triangolo grande: il quarto numero triangolare:

risultato = n + numero_triangolare_di_n-1;

Come possiamo calcolare il valore di numero_triangolare_di_n-1?
Facciamolo calcolare a( una diversa istanza de)lla funzione numeroTriangolare() che stiamo definendo.

risultato = n + numeroTriangolare(n-1);

    public static int numeroTriangolare(int n) {
        int result;     
        if (n == 1)
            result = 1;   // caso base
        else
            result = n + numeroTriangolare(n - 1); // ricorsione
                          
        return result;

    }



Ricorsione

La soluzione appena trovata presenta un aspetto interessante: per risolvere il problema di calcolare l'area del triangolo di ampiezza assegnata abbiamo usato il fatto di poter risolvere lo stesso problema per un'ampiezza minore.

Questa viene chiamata soluzione ricorsiva.

Nel nostro caso, per risolvere il problema di calcolare l'n-esimo numero triangolare (l'area del triangolo di ampiezza n) abbiamo usato il seguente metodo:

  • siamo partiti dal saper calcolare l'area del triangolo di ampiezza 1,
  • abbiamo calcolato l'area del triangolo di ampiezza n supponendo di saper calcolare l'area del triangolo di ampiezza n-1.

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




Ricorsione Diretta

Un metodo 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 è il metodo che abbiamo realizzato precedentemente:

    public static int numeroTriangolare(int n) {
        int result;     
        if (n == 1)
            result = 1;   // caso base
        else
            result = n + numeroTriangolare(n - 1); // ricorsione
                          
        return result;

    }

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

Esistono due requisiti che sono basilari per essere sicuri che la ricorsione funzioni:

  • ogni invocazione ricorsiva deve semplificare in qualche modo l'elaborazione,
  • devono esistere casi speciali che gestiscano in modo diretto le elaborazioni più semplici.

Il medodo numeroTriangolare chiama se stesso con valori di ampiezza sempre più piccoli; l'ampiezza prima o poi diventa uguale a 1 che è il caso speciale che vale 1.

Occorre però fare molta attenzione: cosa succede se chiedete l'area del triangolo di ampiezza -1?
Per evitare ciò il metodo numeroTriangolare dovrebbe restituire 0 se l'ampezza è minore di 0.

In questo modo il metodo numeroTriangolare riuscirebbe sempre a concludere la propria elaborazione.

public class MyRecursiveMethods {

    // altri metodi

    public static int numeroTriangolare(int n) {
        int result;     
        if (n < 0)    
            result = 0;  // situazione anomala

        else if (n == 1)
            result = 1;   // caso base

        else
            result = n + numeroTriangolare(n - 1); // ricorsione
                          
        return result;

    }

    // altri metodi
}



Fattoriale Ricorsivo

La ricorsione non era veramente necessaria per calcolare l' n-esimo numero triangolare che poteva essere calcolato semplicemente usando la nota equivalenza per la somma dei primi n numeri positivi:

1 + 2 + 3 +...+ n = n * (n+1)/2

Vediamo adesso l'esempio di una formula simile ma non calcolabile direttamente: la funzione fattoriale.

          n! = n * (n - 1)* ... * 3 * 2 * 1
Per convenzione  0! = 1. Inoltre, il fattoriale non è definito per i numeri negativi. 

Nella lezione sui cicli abbiamo visto come calcolare il fattoriale in modo iterativo. Come possiamo invece scrivere un metodo ricorsivo che calcoli la funzione fattoriale? Osserviamo che:

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

Quindi la definizione induttiva del fattoriale è:

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

Seguendo tale descrizione possiamo agiungere il metodo ricorsivo fattoriale alla classe dei nostri metodi.

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
}


Come funziona la Ricorsione? (1)

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

Sequenza di chiamate ricorsive




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.

Sequenza di ritorno




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 l'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:

  • 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 (lo spazio sprecato si moltiplica per il numero di invocazioni ricorsive effettuate!).

  • 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).

  • complessità alta: per certi problemi le soluzioni ricorsive hanno intrinsecamente complessità non lineare.

Gli ultimi due problemi possono risultare particolarmente gravosi e quindi li esaminiamo più in dettaglio.



Ricorsione Infinita

In una ricorsione infinita vengono attivate infinite istanze di un metodo. 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).



Complessità Alta

La tecnica della 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:
FibTree.gif
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).

Per ovviare alla alta complessità dei metodi ricorsivi possiamo sempre transformare i loro algoritmi in algoritmi iterativi. Per esempio possiamo definire una versione iterativa iterativeFactorial del metodo factorial: tale versione è tanto leggibile quanto la versione ricorsiva.

In modo analogo si può scrivere una versione iterativa iterativeFib del metodo per calcolare i numeri di Fibonacci: tale definizione ha complessità lineare ma è meno leggibile.

public class MyIterativeMethods {

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

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 .