Algoritmo ricorsivo

In informatica, si definisce algoritmo ricorsivo, o ricorsione, un algoritmo espresso in termini di se stesso, in cui l'esecuzione su un insieme di dati trae vantaggio dalla loro semplificazione o suddivisione e dall'applicazione dello stesso algoritmo alle partizioni così ottenute.

Risulta particolarmente utile per risolvere problemi complessi quando è possibile suddividerli in problemi più semplici dello stesso tipo. In tal caso, l'algoritmo richiama se stesso, generando una sequenza di chiamate che termina quando si verifica una particolare condizione, detta condizione di terminazione (o caso base), generalmente associata a specifici valori di input.

La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se le soluzioni ricorsive non sono sempre le più efficienti. Questo è dovuto al fatto che la ricorsione viene generalmente implementata attraverso le funzioni, la cui invocazione comporta un certo costo computazionale. Per questo motivo, in alcuni casi, gli algoritmi iterativi risultano più efficienti di quelli ricorsivi.

In base all'efficienza e all'utilizzo della memoria, è possibile distinguere due tipologie di ricorsione:

Ricorsione di coda: si verifica quando la chiamata ricorsiva è l'ultima operazione eseguita dall'algoritmo. Una volta effettuata la chiamata, non è necessario eseguire altre operazioni. La soluzione viene costruita passo dopo passo, attraverso una serie di risultati parziali. Al termine di ogni passo, una parte del problema è stata risolta e si passa a un problema più piccolo.

Ricorsione non di coda: si verifica quando, dopo una chiamata ricorsiva, è necessario eseguire altre operazioni per arrivare al risultato finale. In questo caso, l'algoritmo deve aspettare che terminino le chiamate ricorsive successive, perché ha bisogno dei loro risultati per completare il calcolo.

Esistono anche diverse categorie di ricorsione, classificate in base alla loro struttura e al modo in cui avvengono le chiamate ricorsive:

Ricorsione multipla (o ad albero): si verifica quando una funzione richiama se stessa più volte all'interno della stessa chiamata.
Ricorsione mutua (o indiretta): si verifica quando due o più funzioni si richiamano a vicenda.
Ricorsione annidata: si verifica quando una chiamata ricorsiva contiene, al suo interno, un'altra chiamata alla stessa funzione.

La distinzione tra ricorsione strutturale e ricorsione generativa riguarda il modo in cui cambiano i dati a ogni passo della ricorsione.

Ricorsione strutturale: si lavora sui componenti di una struttura dati che si riduce progressivamente. Ad esempio, si può lavorare su una lista, prendendo di volta in volta il resto della lista, oppure su un albero, passando da un nodo ai suoi nodi figli.

Ricorsione generativa: a ogni passo viene generato un nuovo dato, ottenuto dal precedente, sul quale viene applicata nuovamente la ricorsione.

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

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 esempio altrettanto semplice, costruito in modo analogo, è costituito dalla 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. È possibile trasformare una funzione che utilizza questo tipo di algoritmo ricorsivo in una funzione 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.

Voci correlate

Altri progetti

Wikibooks contiene testi o manuali sull'algoritmo ricorsivo
Wikizionario contiene il lemma di dizionario «ricorsione»

Collegamenti esterni

Mauro Cappelli, Ricorsione, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2008.

ricorsività, su sapere.it, De Agostini.

Ricorsione, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) Eric W. Weisstein, Recursion, su MathWorld, Wolfram Research.

(EN) Recursion, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
(EN) Denis Howe, recursion, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica

Portale Matematica