Ricorsione

         

La ricorsione è il processo di definizione di un oggetto o di una operazione in termini di se stesso.
Un linguaggio di programmazione è ricorsivo se è possibile che una funzione invochi se stessa.
Un semplice esempio di funzione ricorsiva è quella per il calcolo del fattoriale che in matematica è definito come

ad esempio

Versione iterativa

#include<iostream>
using namespace std;
int fat(int n){
int f,j; f=1;
for(j=1;j<=n;j++)f=f*j;
return f;
}
main(){
   cout<<fat(4);
}

Versione ricorsiva

#include<iostream>
using namespace std;
int rfat(int n){
   int f; if(n==1) return 1;
   f=rfat(n-1)*n;
   return f;
}
main(){
   cout<<rfat(5);
}

Il funzionamento della funzione fat() non ricorsiva, dovrebbe essere evidente : usa un ciclo che inizia da 1 e finisce al valore di n di cui bisogna calcolare il fattoriale, moltiplicando ogni numero per il risultato parziale. La funzione rfat() ricorsiva, è più complessa.
Se rfat() viene chiamata con il valore 1, restituisce 1. Se viene chiamata con un valore diverso da 1, restituisce il prodotto rfat(n-1)*n.
Questa espressione è valutata calcolando ricorsivamente il valore di rfat(n-1).
Il processo prosegue fino a quando n raggiunge il valore 1, dopo di che iniziano i ritorni dalle funzioni chiamate.

Se calcoliamo il fattoriale di 2, la prima chiamata ad rfat() provoca una seconda chiamata con il valore 1. Il ritorno da questa seconda chiamata avviene con il valore 1 , che è poi moltiplicato per 2 (il precedente valore di n) che è anche il risultato.
Può essere interessante inserire all'interno del listato delle istruzioni di stampa all'interno della funzione rfat() che possono mostrare il livello di ricorsione raggiunto ed il valore dei risultati intermedi.
Quando una funzione chiama se stessa , l'elaboratore colloca nello stack le nuove variabili locali ed i parametri formali: l'esecuzione della funzione parte dall'inizio del codice ed utilizza queste nuove variabili. Non viene invece creata una nuova copia del codice della funzione. Al ritorno da ogni chiamata ricorsiva, i parametri e le variabili allocate al momento della chiamata corrispondente vengono rimossi l'esecuzione riprende dall'istruzione seguente alla chiamata della funzione.
Qui sotto il diagramma dello stack per la funzione rfat(3)

Generalmente le funzioni ricorsive non conducono a risparmi nelle dimensioni del codice o nel numero delle variabili necessarie. Può invece accadere che alcune funzioni ricorsive siano più lente delle loro equivalenti iterative (che usano i cicli) a causa del tempo aggiuntivo necessario per le chiamate.
Il problema maggiore delle funzioni ricorsive sta nello spazio richiesto allo stack ad ogni chiamata .
Se il livello di ricorsione diventa eccessivo , è possibile che lo stack vada a sconfinare in aree di memoria occupate dal codice o da variabili locali.
Tuttavia se le funzioni sono state scritte in modo corretto non ci si dovrebbe preoccupare di questo problema. Il vantaggio delle funzioni ricorsive risiede nella maggior naturalezza con cui è possibile scrivere alcuni algoritmi rispetto alle forme iterative; ad esempio uno dei più famosi algoritmi di ordinamento : il quicksort è di tipo ricorsivo anche se è possibile realizzarlo in forma iterativa che però è più complessa e macchinosa.

All'interno di una funzione ricorsiva deve esistere un if() che forza l'uscita dalla funzione senza ulteriori chiamate ricorsive, in caso contrario non sarà più possibile uscite dalla funzione una volta entrati.