1
RICORSIONE SU VETTORI
Vogliamo ora mostrare come è possibile scorre 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.
2
RICORSIONE SU VETTORI
Consideriamo un vettore A di interi composto da n elementi come
illustrato di seguito:
Array di interi
3
6
12
-4
….. A[i] ….
Indici
0
1
2
3
…..
i
3
22
..... n-2 n-1
.
11
n
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
3
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:
se la chiamata ricorsiva raggiunge 0 senza trovare il valore K,
allora la funzione deve ritornare true;
se durante la chiamata ricorsiva si ritrova il valore K deve
ritornare false altrimenti deve scendere di livello richiamando se
stessa.
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);
}
4
Variazioni sul tema della ricorsione
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
 se non ci sono elementi la somma vale 0;
la somma dei primi N elementi è uguale alla somma di quelli
precedenti più il valore attuale A[N].
Dalle osservazioni precedenti scaturisce subito il codice:
5
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
6
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.
7
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);}
}
Allegato: Ricorsione vettori
8
ESERCIZI.
1) Scrivere una funzione ricorsiva che, assegnati due interi N1 ed N2,
restituisca la somma di tutti gli interi compresi tra N1 ed N2.
2) Sia assegnato un vettore A di interi di dimensione N. Scrivere una
funzione ricorsiva che calcoli il massimo valore tra gli elementi di A.
3) Assegnato un vettore di caratteri S ed un carattere c, scrivere una
funzione ricorsiva che calcoli le occorrenze di c in S.
4) Assegnato un vettore D di dimensione N, scrivere una funzione
ricorsiva che calcoli il minimo valore tra la differenza di ogni
elemento con il precedente ( escluso il primo ).
5) Assegnato un vettore F di dimensione N, scrivere una funzione
ricorsiva che calcoli il massimo valore tra la somma di ogni elemento
con il successivo ( escluso l’ultimo ).
9
Fino ad ora abbiamo considerato solo casi in cui erano
presenti un solo caso base.
E’ però possibile incontrare casi in cui ci sono due o più
casi base.
Mostreremo di seguito alcuni esempi.
10
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:
1.
2.
abbiamo letto il massimo numero possibile di valori
abbiamo letto un numero negativo
In entrambi i casi la lettura deve terminare e si esegue
l’assegnazione.
11
Scriviamo l’algoritmo, tenendo presente che indichiamo con Left quanti
numeri positivi è ancora possibile assegnare e con Temp il valore letto.
// La ricorsione non lineare
#include <iostream>
#include "InsertArray.h"
using namespace std;
// PROTOTIPI
void riempi(int, int &, int []);
// MAIN
int main()
{
int a[100],j,N,x,rimasti,nelementi;
cout<<"Numeri di elementi ";
cin>>nelementi;
rimasti=0;
riempi(nelementi, rimasti, a);
stampa(a,rimasti);
system("pause");
}
// DEFINIZIONI
void riempi(int nelementi, int &rimasti,
int Ints[])
int Temp;
if ((nelementi == 0)) //1° caso base
return;
else
{
cin>>Temp;
//2° caso base
if (Temp<=0)
return;
else
{
Ints[rimasti]=Temp;
rimasti=rimasti+1;
riempi(nelementi-1,rimasti,Ints);
}
//chiamata ricorsiva
}
}
12
Allegato: ricorsione vettori
ESERCIZIO
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
bool elaboraIter(char a1[], int N1)
{
int i=0,j;
bool trovato;
while (a1[i]!='-')
{
j=i;
trovato=false;
while ((j<N1)&&!trovato)
{
if ((a1[j-1]=='-')&&(a1[j]==a1[i]))
trovato=true;
else
j++;
}
if (!trovato)
return false;
else
i++;
}
return true;
}
13
Questa è la versione ricorsiva.
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 “-”
//precondizioni i=0, j=1
bool elaboraRic(char a1[], int N1, int i,
int j)
{
if (a1[i]=='-')
return true;
else
{
if (j>N1)
return false;
else
{
if ((a1[j-1]=='-')&&(a1[j]==a1[i]))
return elaboraRic(a1, N1, i+1,i);
else
return elaboraRic(a1, N1, i,j+1);
}
}
}
14
ricorsVettoriCar
Altri esempi sono riportati nell’Allegato ricorsve3.cpp.
Si noti che è allegata anche la libreria InsertArray.h che contiene una utility
per la lettura dei vettori e una per la scrittura riportate di seguito.
void LeggeVettore (int vet[],const int n, char nome, int nr, bool Acaso) {
int i;
if (Acaso){
//genera valori casuali
for (i=0; i<n; i++) {
vet[i]=fabs(rand()%10) ;//nr - nr/2;
cout<<nome<<"["<<i<<"]="<<vet[i]<<" ";
}
cout<<endl;}
else {
cout<<"Assegna "<<n<<" valori"<<endl; //dati da tastiera
for (i=0; i<n; i++) {
cout<<nome<<"["<<i<<"]=";
cin>>vet[i];
}
}
}
void StampaVettore (const int a[], const int n, char nome) {
int i;
for (i=0; i<n; i++) {
cout<<nome<<"["<<i<<"]="<<a[i]<<endl;
}
}
15
RICORSIONE SULLE MATRICI
Assegnata una matrice quadrata NxN, scrivere una funzione
ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
1 0 0
0 1 0
0 0 1
1 0 0
-1 0 0
0 0 1
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
16
RICORSIONE SULLE MATRICI
Assegnata una matrice quadrata NxN, scrivere una funzione
ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
if i>N
1 0 0 Caso base: i>N
return true
0 1 0 Matrice unitaria
else
0 0 1 Else è unitaria se
if condizione NON vera
1 0 0
-1 0 0
0 0 1
return false
A[i,j]=1 se i=j
A[i,j]=0 se i<>j
else if j>N
return unitaria (a,i+1,0,N)
altrimenti
NON unitaria
else
return unitaria(a,i,j+1,N)
17
1 0 0
0 1 0
0 0 1
Caso base: i>N
if i>N
return true
Matrice unitaria
Else è unitaria se
else
if condizione NON vera
1 0 0
-1 0 0
0 0 1
return false
A[i,j]=1 se i=j
A[i,j]=0 se i<>j
else if j>N
return unitaria (a,i+1,0,N)
altrimenti
NON unitaria
else
return unitaria(a,i,j+1,N)
18
RICORSIONE SULLE MATRICI
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);
}
19
Esercizi sulle matrici
Assegnata una matrice A di interi
1) scrivere una funzione ricorsiva che restituisca true se è simmetrica, false
altrimenti.
2) scrivere una procedura o funzione ricorsiva che restituisca il valore true se la
matrice possiede due righe consecutive uguali, false altrimenti.
3) scrivere una procedura ricorsiva che calcoli la somma delle righe dispari e
quelle delle righe pari
4) scrivere una funzione ricorsiva che restituisca true se tutti gli elementi della
diagonale principale sono positivi
5) scrivere una procedura o funzione ricorsiva che controlli se la somma degli
elementi della diagonale principale è uguale a quella della diagonale secondaria
6) 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.
Allegato: ricorsione matrici.cpp
20
ESEMPIO
/* 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); }
21
ESEMPIO
/* 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); }
22
ESEMPIO
/*scrivere una procedura ricorsiva che calcoli la somma delle righe
dispari e quelle delle righe pari*/
void pariDispari(int a[][cmax], 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
sommaD=sommaD+a[i][j];
return pariDispari(a,i,j+1,N,sommaP,sommaD); }
}
void pariDispari(int a[][cmax], int i, int j, int N, int &sommaP, int &sommaD)
{ if (i<=N)
{ if (j>N)
return pariDispari(a,i+2,0,N,sommaP,sommaD);
else
sommaP=sommaP+a[i][j];
sommaD=sommaD+a[i][j];
23
return pariDispari(a,i,j+1,N,sommaP,sommaD); }
}
ESEMPIO
/*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);
}
24
ESEMPIO
/*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.*/
bool iesimo(int a[][colmax], int i, int j,int N, int &sommaneg)
{
if (i<0)
return true;
else
if (j<0)
{ if (sommaneg!=i) return false;
sommaneg=0;
return iesimo(a,i-1,N,N,sommaneg); }
else {
if (a[i][j]<0 )
{
sommaneg=sommaneg+1;
if (sommaneg>i)
return false;
else
return iesimo(a,i,j-1,N,sommaneg);}
else
return iesimo(a,i,j-1,N,sommaneg);
ricorsione matrici
25
}
}
ESERCIZIO
/* Assegnata una matrice MxM determinare, con una funzione ricorsiva,
se ci sono due righe uguali anche non consecutive. */
ESERCIZIO
/* Assegnata una matrice MxM determinare, con una funzione ricorsiva,
il valore massimo tra i massimi delle diagonali principali. */
26
Esercizio
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.
Es.
A=
2
15
6
13
11
8
9
12
14
7
18
3
TRUE
perché A[0][0]=pari, … ,A[0][3]=dispari,
la sequenza dei pari cresc (2, 6, 8, 12,14,18)
mentre quella dei dispari
decresce (15, 13, 11, 9, 7,3)
27