Vogliamo ora mostrare come è possibile scorrere un vettore A, mediante una funzione ricorsiva.
Ad esempio: Assegnato un vettore A di interi, scrivere una funzione ricorsiva che ritorni true se ogni elemento del vettore A è diverso da K, false altrimenti.
Consideriamo un vettore A di interi composto da n elementi come illustrato in figura.
Dal punto di vista iterativo un possibile algoritmo è il seguente:
bool diversodaK(int s[ ], int n, int K);
while (i<n && s[i]!=K)
{
i++;
return (s[i]!=K)
Esso scorre il vettore per tutta la sua lunghezza controllando via via la parte rimanente.
Non appena trova K esce altrimenti ritorna false.
Dal punto di vista ricorsivo possiamo immaginare che il controllo parta dall’indice n finale andando poi a ritroso.
Dobbiamo ora determinare il caso in cui il processo termina, il caso base:
In definitiva si ha:
bool diversodaK(int s[ ], int n, int K) {
if ( n<0)
return true;
else if (s[n]==K)
return false;
else
return diversodaK(s,n-1);
}
Assegnato un vettore A di interi di dimensione N, calcolare in maniera ricorsiva la somma di tutti i suoi elementi. Per determinare tale somma osserviamo che
Dalle osservazioni precedenti scaturisce subito il codice:
Precondizioni: x=0;
double sommaelementi(int a[], int N,int x)
{
if (x>=N)
return 0;
else
{
return a[x]+(sommaelementi(a,N,x+1));
}
}
In questo algoritmo il caso base è determinato dal raggiungimento dell’indice x del valore N.
Quando si applica un processo ricorsivo tipo quello della 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.
Riscriviamo la funzione precedente con due variazioni:
– utilizziamo una procedura e non una funzione;
– scriviamo le somme parziali ogni 3 passi.
In questo caso dobbiamo inserire nella lista dei parametri formali una variabile che ci consenta di mostrare la somma ogni 3 passi.
// precondizioni: somma=0, i=0.
void Sommarray2(int vet[], int N, int &somma, int i)
{ // somma elementi vettore mostrando le somme parziali ogni 3
if (i>N)
somma=0;
else {
if (i%3==0) { cout<<"somma parziale "<<i<<" ="<<somma<<endl;}
somma=somma+vet[i];
Sommarray2(vet, N,somma,i+1);}
}
Fino ad ora abbiamo considerato solo casi in cui erano presenti un solo caso base.
È però possibile incontrare casi in cui ci sono due o più casi base.
Problema con due casi base.
Assegnare agli elementi dell’Array di interi Ints, dei numeri interi positivi compresi nell’intervallo 1..Total.
Ogni numero viene dato da tastiera. Il processo di lettura cessa o quando si introducono tutti i numeri previsti (Total) oppure quando si introduce un numero negativo. Subito dopo si effettua l’assegnazione.
I CASI BASE possibili sono due:
In entrambi i casi la lettura deve terminare e si esegue l’assegnazione.
Scriviamo l’algoritmo, tenendo presente che indichiamo con Left quanti numeri positivi è ancora possibile assegnare e con Temp il valore letto.
Ricorsione vettori, già presentato nella slide n. 6.
Sia dato un array A di caratteri di lunghezza L contenente alcune parole separate da un trattino. Scrivere una funzione che restituisca TRUE se la prima parola è formata dai caratteri iniziali delle restanti parole.
Esempio: L=24;
A= PANE-PERA-AGO-NERO-ELICA
L’output sarà TRUE
A= PANE-PERA-UGO-NERO-ELICA
L’output sarà FALSE
Di lato riportiamo la versione iterativa.
Si notino i due casi base e le due chiamate ricorsive.
Il 1° caso base controlla il termine della lettura della prima parola, (quella di riferimento);
Il 2° caso base interviene quando si è esplorato tutto il vettore senza trovare la parola che inizia con iI carattere previsto;
La 1a chiamata ricorsiva si applica quando si è trovato un “-” seguito dall’iniziale della parola che coincide con il carattere richiesto,
La 2a chiamata ricorsiva si applica quando non si è trovato il “-”.
Ricorsione VettoriCar
Per far girare il programma allegato è necessario mettere nella stessa cartella sia il programma che la libreria InsertArray.h mostrata di seguito e utilizzata anche negli esempi successivi.
Altri esempi.
InsertArray.h , contiene una utility per la lettura dei vettori e una per la scrittura riportate in figura.
Assegnata una matrice quadrata NxN, scrivere una funzione ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
Come controlliamo ogni elemento della matrice?
Partendo dalla riga=0 e colonna=0 possiamo procedere per linee orizzontali: quando la colonna arriva al valore N (nell’esempio N=3) allora scatta alla riga successiva e la colonna diventa 1:
Se j>N allora i=i+1 e j=0
Caso Base: se i>N allora siamo giunti alla fine della matrice senza incontrare errori: la matrice è unitaria; se durante il controllo trova che la condizione non è verificata deve ritornare il valore false.
Assegnata una matrice quadrata NxN, scrivere una funzione ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
Se la funzione ha il prototipo bool unitaria (int a[][10], int i, int j, int N) la sua definizione sarà:
bool unitaria (int a[][colmax], int i, int j, int N)
{if (i>N)
return true;
else
if (((i==j) && (a[i][j]!=1)) || ((i!=j) && (a[i][j]!=0)))
return false;
else
if (j>N)
return unitaria (a,i+1,0,N);
else
return unitaria(a,i,j+1,N);
}
Assegnata una matrice A di interi:
/* scrivere una funzione ricorsiva che restituisca true se è simmetrica, false altrimenti. */
bool simmetrica (int a[][colmax], int i, int j, int N)
{if (i>N)
return true;
else
if (j>N)
return simmetrica(a,i+1,0,N);
else
if (a[i][j]!=a[j][i])
return false;
else
return simmetrica(a,i,j+1,N); }
/* scrivere una funzione ricorsiva che restituisca il valore true se la matrice possiede due righe consecutive uguali, false altrimenti.*/
bool righeUguali (int a[][colmax],int i, int j, int N )
{
if (i>N-1)
return false;
else
if (j>N)
return true;
else
if (a[i][j]!=a[i+1][j])
return righeUguali(a,i+1,0,N);
else
return righeUguali(a,i,j+1,N); }
/*scrivere una procedura ricorsiva che calcoli la somma delle righe dispari e quelle delle righe pari*/
void pariDispari(int a[][colmax], int i, int j, int N, int &sommaP, int &sommaD)
{
if (i<=N)
{
if (j>N)
return pariDispari(a,i+1,0,N,sommaP,sommaD);
else
if ((i%2)==0)
sommaP=sommaP+a[i][j];
else
sommadS=sommadS+a[i][N-1-i];
return sommaDiag(a,i-1,N,sommadP,sommadS);
}
/*scrivere una procedura o funzione ricorsiva che controlli se la somma degli elementi della diagonale principale è uguale a quella della diagonale secondaria*/
bool sommaDiag(int a[][colmax], int i, int N, int &sommadP, int &sommadS)
{
if (i<0){
return (sommadP==sommadS);}
else
sommadP=sommadP+a[i][i];
sommadS=sommadS+a[i][N-1-i]; return sommaDiag(a,i-1,N,sommadP,sommadS);
}
/*scrivere una procedura o funzione ricorsiva che restituisca il valore true se ogni riga i-esima della matrice possiede un numero di i valori negativi, false altrimenti.*/
Esercizio 1
/* Assegnata una matrice MxM determinare, con una funzione ricorsiva,
se ci sono due righe uguali anche non consecutive. */
Esercizio 2
/* Assegnata una matrice MxM determinare, con una funzione ricorsiva,
il valore massimo tra i massimi delle diagonali principali. */
Assegnata una matrice A NxM scrivere una funzione booleana ricorsiva che verifichi che a partire dall’elemento A[0][0] ad ogni coppia di indici la cui somma è pari corrisponda un elemento della matrice pari e dispari in caso contrario. Verificare anche che leggendo la matrice per righe, i numeri pari siano disposti in maniera crescente e i dispari in maniera decrescente.