Algoritmo ricorsivo

Triangolo di Sierpiński

In informatica viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati.

Tale tecnica risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di variabili in input. L'algoritmo richiama se stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione, che in genere si ha con particolari valori di input.

La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se non sempre le soluzioni ricorsive sono le più efficienti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le funzioni, e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficienti gli algoritmi iterativi.

In alcuni casi la ricorsione è altrettanto efficiente di un ciclo iterativo: linguaggi dei paradigmi funzionali o logici tipicamente non hanno il concetto di ciclo ed usano la ricorsione ottimizzando automaticamente (Tail call optimization).

Descrizione

Un esempio: il fattoriale di un numero

Per capire il concetto useremo un esempio di tipo matematico, il calcolo del fattoriale di un numero n. Un altro semplice esempio potrebbe essere stato quello della Successione di Fibonacci.

Chiameremo fattoriale di n e scriveremo n!, il prodotto dei primi n numeri naturali, ottenuto come segue:

         0! = 1; per definizione
         1!=1;
         n! = 1 * 2 * 3 * ...... * n-1 * n;       per n > 0.

Rielaborando la definizione, ci si accorge di come sia possibile darne una versione ricorsiva. Sia a tal proposito:

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

si ottiene,

         n! = (n-1)! * n;

da cui, iterando,

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

continuando ad iterare la definizione, arriveremo alle condizioni di terminazione, per cui il risultato cercato è noto:

         0! = 1! = 1.

Siamo adesso in grado di dare un algoritmo ricorsivo che chiameremo FATT, per il calcolo del fattoriale. Si osservi che la notazione utilizzata distingue tra il simbolo x == y, per indicare uguaglianza tra i due valori ed il simbolo x = y, per indicare che alla variabile x sarà assegnato il valore di y, così come per il Linguaggio C:

      int FATT (int n)
      {
         if (n <= 1) return 1;
         else return n * FATT (n-1);
      }
       

Quando l'algoritmo viene eseguito la prima volta, il valore di n viene confrontato con 0 e con 1, nel caso in cui il valore sia diverso, la procedura viene chiamata ricorsivamente su valori più piccoli sino a quando n non risulta uguale ad 1, nel qual caso il risultato è noto e può essere restituito dalla funzione attuale a quella che l'aveva in precedenza chiamata. I risultati restituiti da ognuna delle procedure ricorsive vengono di volta in volta moltiplicati. Il penultimo valore restituito sarà proprio uguale ad (n-1)!, quest'ultimo verrà moltiplicato per n e l'algoritmo potrà restituire il risultato cercato.

A scopo esplicativo e didattico, viene fornito di seguito un algoritmo per il calcolo del fattoriale che sfrutta un approccio di tipo iterativo:

      int FATTiterativo (int n)
      {
         int fatt = 1;
         while (1 <= n)
         {
            fatt = fatt * n;  
            n --;   
         }
         return fatt;
      }

Tipi di ricorsione

Esistono vari tipi di ricorsione. Si parla di mutua ricorsione quando nell'algoritmo una funzione ne richiama un'altra che a sua volta richiama la prima, altrimenti si parla di ricorsione diretta.

Altra distinzione è quella fra ricorsione lineare, che si ha quando vi è solo una chiamata ricorsiva all'interno della funzione, e non lineare nel caso in cui le chiamate ricorsive siano più di una.

La distinzione più importante ai fini pratici si ha fra ricorsione di coda (tail recursion) e ricorsione non di coda. Si parla di ricorsione di coda quando la chiamata ricorsiva è l'ultima istruzione eseguita nella funzione. Questo tipo di algoritmo ricorsivo è possibile trasformarlo semplicemente in una versione iterativa, che di solito è più efficiente, in quanto non occorre mantenere lo stato della funzione una volta calcolata come è stato fatto nell'esempio precedente. Se l'algoritmo non è ricorsivo di coda, per trasformarlo in una versione iterativa occorre utilizzare un meccanismo di mantenimento dello stato analogo a quello che è utilizzato implicitamente nelle chiamate di funzione.

Espressività della ricorsione

Ricorsione ed iterazione hanno la stessa espressività: la ricorsione può essere rimpiazzata dall'iterazione tramite l'utilizzo di uno stack esplicito, mentre l'iterazione può essere rimpiazzata con la ricorsione di coda. Quale approccio sia il migliore dipende dal problema da risolvere e dal linguaggio utilizzato. Nel caso dei linguaggi imperativi si preferisce l'uso dell'iterazione, particolarmente nel caso di ricorsione lineare, poiché evita l'overhead delle chiamate di funzione e della gestione dello stack, mentre nei linguaggi funzionali, al contrario si preferisce l'uso della ricorsione, in cui la versione di coda è sovente ottimizzata con prestazioni paragonabili all'iterazione.

Vantaggi e svantaggi

La ricorsione ha un vantaggio fondamentale: permette di scrivere poche linee di codice per risolvere un problema anche molto complesso. Tuttavia, essa ha anche un enorme svantaggio: le prestazioni.

Infatti, la ricorsione genera una quantità enorme di overhead, occupando lo stack per un numero di istanze pari alle chiamate della funzione che è necessario effettuare per risolvere il problema. Funzioni che occupano una grossa quantità di spazio in memoria, pur potendo essere implementate ricorsivamente, potrebbero dare problemi a tempo di esecuzione. Inoltre, la ricorsione impegna comunque il processore in maniera maggiore per popolare e distruggere gli stack.

Pertanto, se le prestazioni sono obiettivo principale del programma e non si dispone di sufficiente memoria, si consiglia di non utilizzare la ricorsione.

Applicazioni principali

• algoritmi su alberi
• valutazione di funzioni matematiche
• gestione di aggregati eterogenei di dati, in combinazione con il polimorfismo
• gestione di dati in formato XML. Grazie alle API fornite con tutti i linguaggi di programmazione moderni, è possibile formulare praticamente tutti gli algoritmi di lettura/creazione XML in maniera ricorsiva.
• algoritmi di ordinamento efficienti come Quicksort e Merge sort o algoritmi di ricerca come la ricerca binaria possono essere formulati in maniera ricorsiva, anche con tipi di dati come le liste a puntatori.
• stesura di algoritmi che lavorano con la tecnica di backtracking.
• descrizione di curve frattali.

Eliminazione della ricorsione

Sono stati fatti degli studi approfonditi su come ottimizzare il codice di alcune routine dove il carico della memoria di allocazione delle funzioni è troppo elevato. Si effettuano degli studi sulla natura della funzione e si ricava l'eliminazione della ricorsione per un'ottimizzazione della memoria.

Ricorsione in coda

La ricorsione in coda (tail recursion) si verifica quando, in una procedura e/o funzione ricorsiva (che richiama se stessa), la chiamata ricorsiva viene operata come ultimo passo. Ciò implica che al ritorno dalla chiamata ricorsiva la funzione non produce alcun altro passo. Srotolando la ricorsione si intuisce come si possa ottimizzare questa condizione sostituendo una funzione ricorsiva con una iterativa, che comporti minor complessità spaziale. Il passaggio da funzione ricorsiva a funzione iterativa può essere operato semplicemente riproducendo per passi successivi l'intero corpo, appunto, della funzione.

 void F(x)
 {
  if P(x) then {D;}
  else 
  {
    E; y=g(x); F(y);
  }
 }

Si noti come la chiamata ricorsiva sia l'ultima istruzione della funzione. Si può quindi facilmente eliminarla sostituendola con un costrutto iterativo

 void F_it(x)
 { 
   while (P(x)==0) then
     {E; x=g(x);}
   {D;}
 }

Si consideri la procedura di ricerca binaria (ricorsiva) in un vettore ordinato

 int binsearch(int a[], int sx, int dx, int el)
 { 
  int x;
  if (dx < sx) return -1;
  x = (dx + sx)/2;
  if (el < a[x]) return binsearch(a,sx,x-1,el);
  else if (el == a[x]) return x;
  else return binsearch(a,x+1,dx,el);
 }

Osserviamo che le chiamate ricorsive sono eseguite come ultime istruzioni della funzione. Sviluppiamo una versione iterativa per la ricerca binaria

 int binsearch_it(int a[], int dim, int el)
 { 
     int sx, dx, x;
     sx = 0; dx = dim - 1;
     while (dx >= sx)
     { 
        x = (dx + sx)/2;
        if (el == a[x]) return x;
        if (el < a[x]) dx = x - 1;
        else sx = x + 1;
     }
     return -1;
 }

Ricorsione non in coda

Quando invece la ricorsione non è l'ultima istruzione della procedura (ricorsione non in coda) si può optare per una soluzione che preveda l'utilizzo di uno stack di supporto che permette di salvare i valori delle chiamate ricorsive e tramite un ciclo while simulare in modo del tutto banale ciò che fa lo stack di sistema.

Curiosità

L'algoritmo ricorsivo è protagonista del libro Crypto dello scrittore Dan Brown.

La soluzione del gioco d'ingegno noto con il nome Torre di Hanoi è facilmente descrivibile tramite un algoritmo ricorsivo.

La ricorsione può essere intesa anche come una versione costruttiva del principio d'induzione, dove il termine "costruttiva" indica la capacità di costruire la soluzione di un problema.

Una famosa frase (riportata su Programming Recursion di L. Peter Deutsch, interamente dedicato alla ricorsione) dice che: To Iterate is Human, to Recurse, Divin ("iterare è umano, usare la ricorsione è divino").

Voci correlate

• Effetto Droste
• Funzione ricorsiva
• Funzione ricorsiva primitiva
• Master theorem
• Ricorsione
• Tesi di Church-Turing