1

2

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.

3

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

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] …. 3 22 11

Indici 0 1 2 3 ….. i ......

n-2 n-1 n 

Dal punto di vista iterativo un possibile algoritmo è il seguente:

4

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.

Dal punto di vista ricorsivo possiamo immaginare che il controllo parta dall’indice n finale andando poi a ritroso.

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);}

5

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:

6

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

Precondizioni: x=0;

7

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.

8

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

9

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 ).

10

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.

11

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. abbiamo letto il massimo numero possibile di valori2. abbiamo letto un numero negativo

In entrambi i casi la lettura deve terminare e si esegue l’assegnazione.

12

// La ricorsione non lineare#include <iostream>#include "InsertArray.h"using namespace std;

// PROTOTIPIvoid riempi(int, int &, int []);

// MAINint 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"); }

Scriviamo l’algoritmo, tenendo presente che indichiamo con Left quanti numeri positivi è ancora possibile assegnare e con Temp il valore letto.

// DEFINIZIONIvoid riempi(int nelementi, int &rimasti,

int Ints[])int Temp;if ((nelementi == 0)) return; else { cin>>Temp; if (Temp<=0) return; else { Ints[rimasti]=Temp; rimasti=rimasti+1; riempi(nelementi-1,rimasti,Ints); } }}

//1° caso base

//2° caso base

//chiamata ricorsiva

Allegato: ricorsione vettori

13

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

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; }

Di lato riportiamo la versione iterativa

14

//precondizioni i=0, j=1bool 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); } } }

ricorsVettoriCar

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 “-”

15

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; }}

16

RICORSIONE SULLE MATRICI

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.

100

010

001

100

00-1

001

17

RICORSIONE SULLE MATRICI

if i>N

return true

else

if condizione NON vera

return false

else if j>N

return unitaria (a,i+1,0,N)

else

return unitaria(a,i,j+1,N)

Assegnata una matrice quadrata NxN, scrivere una funzione ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.

100

010

001

100

00-1

001

Caso base: i>N

Matrice unitaria

Else è unitaria se

altrimenti

NON unitaria

A[i,j]=1 se i=j

A[i,j]=0 se i<>j

18

if i>N

return true

else

if condizione NON vera

return false

else if j>N

return unitaria (a,i+1,0,N)

else

return unitaria(a,i,j+1,N)

100

010

001

100

00-1

001

Caso base: i>N

Matrice unitaria

Else è unitaria se

altrimenti

NON unitaria

A[i,j]=1 se i=j

A[i,j]=0 se i<>j

19

RICORSIONE SULLE MATRICI

Se la funzione ha il prototipobool 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);}

20

Esercizi sulle matrici

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.

Assegnata una matrice A di interi

Allegato: ricorsione matrici.cpp

21

/* 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); }

ESEMPIO

22

/* 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); }

ESEMPIO

23

/*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); } }

ESEMPIO

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]; return pariDispari(a,i,j+1,N,sommaP,sommaD); } }

24

/*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); }

ESEMPIO

25

/*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

ESEMPIO

26

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. */

27

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. TRUE

A= 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)

Esercizio

2 15 6 13

11 8 9 12

14 7 18 3