edutecnica

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.
Negli esercizi svolti si è fatto ampio uso dell'espressione condizionale in sostituzione del più classico costrutto if().
Come sempe i codici possono essere testati, copiandoli ed incollandoli nella shell di CPP.