Per illustrare il concetto di ricorsione ricordiamo un metodo matematico per fare dimostrazioni: l’induzione. Mostreremo di seguito alcune dimostrazioni per induzione e i corrispondenti algoritmi ricorsivi.
La dimostrazione per induzione è una tecnica per provare che un asserto S(n) vale per tutti gli interi n maggiori di un certo limite inferiore.
Supposto vero l’asserto la dimostrazione consiste in:
Diremo che un algoritmo è ricorsivo se risolve un problema a cui è riferito utilizzando la soluzione dello stesso problema ottenuta ad un livello inferiore cioè in un caso più semplice.
Una funzione ricorsiva per risolvere un problema per prima cosa deve essere, quindi, in grado di risolvere i casi più semplici, detti casi-base: in queste situazioni la funzione ricorsiva termina e restituisce una soluzione.
Nelle altre situazioni, la funzione ricorsiva, deve poter dividere il problema in sotto problemi simili a quello di partenza e da esso differenti solo per le dimensioni.
In tal caso la funzione ricorsiva, richiama una copia di se stessa e riprende la computazione.
Questa operazione è detta chiamata ricorsiva della funzione.
Ecco come opera una funzione ricorsiva in presenza di un problema di cui si conosca la soluzione per almeno un caso semplice (caso base) e la sua trasformazione da una rappresentazione semplice ad un'altra di dimensioni maggiori.
In pseudo codice potremmo dire che:
if
i parametri fanno riferimento a un caso base
risolvi il problema
else
usa i valori dei parametri per un problema ridotto
CHIAMA LA FUNCTION PER RISOLVERE IL PROBLEMA RIDOTTO
Possiamo dire che in questo modo viene applicato il metodo del
DIVIDE ET IMPERA.
Un algoritmo iterativo consiste in un unico processo che ripete le stesse identiche operazioni molte volte.
Un algoritmo ricorsivo consiste in un numero finito di processi aperti uno dopo l’altro e posti in uno stack. Non appena si chiude un processo subito si scende nello stack e si chiude il processo immediatemente seguente e così via di seguito.
Per scrivere un algoritmo ricorsivo bisogna soddisfare le seguenti condizioni:
Riportiamo di seguito una serie di esempi che illustrano l’uso della ricorsività in maniera adeguata.
Iniziamo con una funzione che calcola la somma dei primi N numeri interi positivi.
A tal fine si ricordi la dimostrazione per induzione introdotta precedentemente.
int Sum(int N)
{
if N=0
Sum =0;
else
Sum =N+ Sum(N-1);
};
Un processo come quello qui descritto si dice per accumulazione.
La rappresentazione nello stack del processo ricorsivo è illustrata di seguito.
Come si può osservare vengo aperti tanti processi fino a quando non si raggiunge il caso base.
A questo punto ogni processo viene chiuso inviando il risultato raggiunto al processo che lo precede nello stack.
int Sum(int N)
{
if N=0
Sum =0;
else
Sum =N+ Sum(N-1);
};
Codice della funzione che calcola la somma dei primi N numeri interi positivi.
// Somma ricorsiva
#include
using namespace std;
// PROTOTIPI
int somma(int ,int);
// MAIN
int main ()
{
int N;
cout<<" A partire da 0 fino a che numero vuoi fare la somma? "; cin>>N;
cout<<"\n La somma dei primi "<<N<<" e' pari a "<<somma(N)<<endl;
system("pause");
}
Un altra versione del calcolo dei primi N interi con stampa dei risultati ogni M passi è mostrato dallo pseudo codice seguente:
Esempio:
Fare la somma dei primi N interi positivi e mostrare le somme parziali ogni M passi.
Pseudo-codice
if N=0
S ← 0
else
Somma(N-1, M, S)
S ← S +N
if N MOD M=0
scrivi N e S
Quando si applica un processo ricorsivo, del tipo di quello per accumulazione, bisogna assicurarsi che i valori accumulati nelle relative variabili siano correttamente passati da un processo all’altro.
Inoltre il valore assunto da una variabile in un processo ricorsivo non deve essere distrutto dal lancio di un altro processo ricorsivo.
Di qui la necessità di passare le variabili utilizzando la chiamata per riferimento.
Nel caso si voglia mostrare il risultato del calcolo della somma parziale dei primi N interi positivi diciamo ogni M passi è necessario introdurre una variabile che tenga conto delle varie somme parziali e che va chiamata per valore.
In figura è mostrato il codice.
Un altro esempio di algoritmo ricorsivo è quello che valuta la somma delle potenze di 2 da 0 a N.
Di seguito mostriamo prima la dimostrazione per induzione del calcolo e quindi l’algoritmo ricorsivo che ad esso si ispira.
Vogliamo dimostrare che (fig. 1).
caso base (fig. 2)
Poniamo n=0, è quindi dimostrato vero.
Algoritmo ricorsivo per calcolare la somma delle potenze di 2 tra 0 e N.
double SumPot(int N)
{
if (N==0)
return 1;
else
return pow(2,N)+SumPot(N-1);
}
Algoritmo ricorsivo: Fare la somma delle potenze di 2 tra 0 e N. In fig. è mostrato lo stack dei processi aperti nel caso di N=5
In allegato è mostrato un codice che calcola:
La somma dei numeri interi tra 1 e N
Il valore di 2N
La somma delle potenze di 2i con 0<=i<=N
Il valore del MCD tra un preassegnato s (nell’esempio s=5) e N.